我想证明一个GUID在一个简单的测试程序中不是唯一的。 我原以为下面的代码会运行几个小时,但它不起作用。我该怎么做呢?

BigInteger begin = new BigInteger((long)0);
BigInteger end = new BigInteger("340282366920938463463374607431768211456",10);  //2^128
for(begin; begin<end; begin++)
  Console.WriteLine(System.Guid.NewGuid().ToString());

我用的是c#。


当前回答

数到2^128,雄心勃勃。

让我们想象一下,每台机器每秒可以计算2^32个id——不是那么雄心勃勃,因为它甚至不到每秒43亿个。让我们用2^32台机器来完成这个任务。此外,让2^32个文明各自投入相同的资源来完成任务。

到目前为止,我们每秒可以计数2^96个id,这意味着我们将计数2^32秒(136年多一点)。

现在,我们所需要的是获得4294967296个文明,每个文明都有4294967296台机器,每台机器每秒能计算4294967296个id,在未来136年左右的时间里,纯粹是为了这项任务——我建议我们现在就开始这项基本任务;-)

其他回答

Go to the cryogenics lab in the New York City. Freeze yourself for (roughly) 1990 years. Get a job at Planet Express. Buy a brand-new CPU. Build a computer, run the program, and place it in the safe place with an pseudo-perpetual motion machine like the doomsday machine. Wait until the time machine is invented. Jump to the future using the time machine. If you bought 1YHz 128bit CPU, go to 3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps after when you started to run the program. ...? PROFIT!!!

... 即使你的1YHz CPU是1GHz CPU的1,000,000,000,000,000倍(如果你更喜欢使用二进制前缀,则为1,125,899,906,842,624倍),也至少需要10,783,127年。

因此,与其等着计算结束,不如去喂那些因为其他n只鸽子夺走了它们的家而失去家园的鸽子。:(

或者,你可以等到128位量子计算机被发明出来。然后,您可以通过在合理的时间内(可能)使用您的程序来证明GUID不是唯一的。

任何两个guid都很可能是唯一的(不相等)。

看看这个SO条目,来自维基百科

而每个生成的GUID不是 保证是唯一的,总数 唯一键数(2^128或 3.4×10^38)是如此之大,以至于相同数字的概率为 生成两次是非常小的。为 例子,考虑可观测 宇宙,其中包含约5×10^22 星星;每颗恒星都有可能 6.8×10^15个通用唯一的guid。

所以你可能还要再等几十亿年,希望在我们所知道的宇宙结束之前,你能击中一个。

如果生成的UUID的数量遵循摩尔定律,那么在可预见的未来永远用不完GUID的印象是错误的。

对于2^128个uuid,只需要18个月* Log2(2^128) ~= 192年,我们就会用完所有uuid。

而且我相信(虽然没有任何统计证据),自从UUID被大规模采用以来,在过去的几年里,我们生成UUID的速度比摩尔定律所规定的要快得多。换句话说,我们可能只有不到192年的时间来处理UUID危机,这比宇宙末日要快得多。

但由于我们肯定不会在2012年底之前将它们耗尽,我们将把这个问题留给其他物种来担心。

但你必须确保你有一个副本,还是你只关心是否有一个副本。为了确保有两个人生日相同,你需要366个人(不包括闰年)。如果有超过50%的概率有两个人同一天生日,你只需要23个人。这就是生日问题。

如果你有32位,你只需要77163个值就有超过50%的重复几率。试试吧:

Random baseRandom = new Random(0);

int DuplicateIntegerTest(int interations)
{
    Random r = new Random(baseRandom.Next());
    int[] ints = new int[interations];
    for (int i = 0; i < ints.Length; i++)
    {
        ints[i] = r.Next();
    }
    Array.Sort(ints);
    for (int i = 1; i < ints.Length; i++)
    {
        if (ints[i] == ints[i - 1])
            return 1;
    }
    return 0;
}

void DoTest()
{
    baseRandom = new Random(0);
    int count = 0;
    int duplicates = 0;
    for (int i = 0; i < 1000; i++)
    {
        count++;
        duplicates += DuplicateIntegerTest(77163);
    }
    Console.WriteLine("{0} iterations had {1} with duplicates", count, duplicates);
}

1000 iterations had 737 with duplicates

现在128位已经很多了,所以你仍然在谈论大量的物品,但碰撞的几率很低。对于给定的概率,您需要使用近似值获得以下记录数:

碰撞发生的概率是1/1000 217亿亿亿,50%的几率发生碰撞 396亿亿,90%的碰撞概率

每年大约发送1E14封电子邮件,所以在这个水平上大约需要40万年,你才能有90%的机会拥有两个具有相同GUID的电子邮件,但这与说你需要运行宇宙年龄830亿倍的计算机或太阳变冷才能找到副本有很大不同。

Well if the running time of 83 billion years does not scare you, think that you will also need to store the generated GUIDs somewhere to check if you have a duplicate; storing 2^128 16-byte numbers would only require you to allocate 4951760157141521099596496896 terabytes of RAM upfront, so imagining you have a computer which could fit all that and that you somehow find a place to buy terabyte DIMMs at 10 grams each, combined they will weigh more than 8 Earth masses, so you can seriously shift it off the current orbit, before you even press "Run". Think twice!