我想证明一个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#.
lig*_*gos 407
Kai,我已经提供了一个程序,可以使用线程做你想做的事.它根据以下条款获得许可:您必须为每个CPU核心每小时支付0.0001美元.费用在每个日历月结束时支付.请尽快与我联系,以获取我的paypal帐户详细信息.
using System;
using System.Collections.Generic;
using System.Linq;
namespace GuidCollisionDetector
{
class Program
{
static void Main(string[] args)
{
//var reserveSomeRam = new byte[1024 * 1024 * 100]; // This indeed has no effect.
Console.WriteLine("{0:u} - Building a bigHeapOGuids.", DateTime.Now);
// Fill up memory with guids.
var bigHeapOGuids = new HashSet<Guid>();
try
{
do
{
bigHeapOGuids.Add(Guid.NewGuid());
} while (true);
}
catch (OutOfMemoryException)
{
// Release the ram we allocated up front.
// Actually, these are pointless too.
//GC.KeepAlive(reserveSomeRam);
//GC.Collect();
}
Console.WriteLine("{0:u} - Built bigHeapOGuids, contains {1} of them.", DateTime.Now, bigHeapOGuids.LongCount());
// Spool up some threads to keep checking if there's a match.
// Keep running until the heat death of the universe.
for (long k = 0; k < Int64.MaxValue; k++)
{
for (long j = 0; j < Int64.MaxValue; j++)
{
Console.WriteLine("{0:u} - Looking for collisions with {1} thread(s)....", DateTime.Now, Environment.ProcessorCount);
System.Threading.Tasks.Parallel.For(0, Int32.MaxValue, (i) =>
{
if (bigHeapOGuids.Contains(Guid.NewGuid()))
throw new ApplicationException("Guids collided! Oh my gosh!");
}
);
Console.WriteLine("{0:u} - That was another {1} attempts without a collision.", DateTime.Now, ((long)Int32.MaxValue) * Environment.ProcessorCount);
}
}
Console.WriteLine("Umm... why hasn't the universe ended yet?");
}
}
}
PS:我想试试Parallel扩展库.那很简单.
并且使用OutOfMemoryException作为控制流只是感觉不对.
编辑
嗯,似乎这仍然吸引了选票.所以我修复了GC.KeepAlive()问题.并将其更改为使用C#4运行.
并澄清我的支持条款:支持仅适用于2010年2月28日.请使用时间机器仅在当天提出支持请求.
编辑2 与往常一样,GC比管理内存做得更好; 以前任何以前做过的尝试都注定要失败.
rjm*_*nro 226
这将运行超过数小时.假设它以1 GHz的频率循环(它不会 - 它将慢很多),它将运行10790283070806014188970年.这比宇宙时代长约830亿倍.
假设摩尔定律成立,那么不运行这个程序,等待几百年并在速度快十亿倍的计算机上运行它会快得多.实际上,如果等到CPU速度增加并且在运行之前购买新的CPU,那么任何需要运行时间超过CPU速度加倍(大约18个月)的程序都会很快完成(除非你写它以便它可以在新硬件上暂停和恢复).
tyl*_*erl 170
GUID在理论上是非唯一的.这是你的证明:
但是,如果太阳的整个输出功率都是针对执行此任务的,那么它在完成之前很久就会变冷.
可以使用许多不同的策略生成GUID,其中一些策略采取特殊措施来保证给定的机器不会两次生成相同的GUID.在特定算法中查找冲突会显示您生成GUID的特定方法很糟糕,但一般不会证明GUID的任何内容.
jas*_*son 137
当然GUID可能会发生冲突.由于GUID是128位,只是生成2^128 + 1它们,并且通过鸽子原理必须发生碰撞.
但是当我们说GUID是唯一的时,我们真正的意思是密钥空间太大以至于几乎不可能意外地生成相同的GUID两次(假设我们随机生成GUID).
如果您n随机生成一系列GUID,那么至少一次碰撞的概率大约是p(n) = 1 - exp(-n^2 / 2 * 2^128)(这是生日问题,可能的生日数是2^128).
n p(n)
2^30 1.69e-21
2^40 1.77e-15
2^50 1.86e-10
2^60 1.95e-03
为了使这些数字具体化,2^60 = 1.15e+18.因此,如果您每秒生成10亿个GUID,则需要36年才能生成2^60随机GUID,即使这样,您发生碰撞的概率仍然存在1.95e-03.你更可能是在你的生活中被杀害(4.76e-03)比你找到在未来36年的冲突.祝好运.
cta*_*cke 61
如果您担心独特性,您可以随时购买新的GUID,这样您就可以扔掉旧的GUID.如果你愿意,我会在eBay上放一些.
AMi*_*ico 47
就个人而言,我认为"大爆炸"是两个GUID相撞时引起的.
R. *_*des 42
您可以使用量子bogosort算法的变体在O(1)时间内显示.
Guid g1 = Guid.NewGuid();
Guid g2 = Guid.NewGuid();
if(g1 != g2) Universe.Current.Destroy();
Gra*_*ton 28
任何两个GUID很可能是唯一的(不相等).
虽然不保证每个生成的GUID都是唯一的,但是唯一密钥的总数(2 ^ 128或3.4×10 ^ 38)是如此之大,以至于两次生成相同数字的概率非常小.例如,考虑可观察的宇宙,其中包含大约5×10 ^ 22个星; 然后每个星星都有6.8×10 ^ 15个通用唯一的GUID.
因此,你可能需要等待数十亿年,并希望你在宇宙之前击中一个,因为我们知道它已经结束了.
Ste*_*edd 27
[更新:] 正如下面的评论所指出的,更新的MS GUID是V4,并且不使用MAC地址作为GUID生成的一部分(我没有看到MS的任何V5实现的迹象,所以如果有人有链接确认,让我知道).但是,对于V4来说,时间仍然是一个因素,并且GUID重复的可能性仍然很小,与任何实际用法无关.你当然不可能只从OP试图做的单一系统测试中生成重复的GUID.
大多数这些答案都缺少关于微软GUID实施的一个重要观点.GUID的第一部分基于时间戳,另一部分基于网卡的MAC地址(如果未安装NIC,则为随机数).
如果我理解正确的话,这意味着复制GUID的唯一可靠方法是在MAC地址相同的多台机器上运行同步GUID代,并且两台系统上的时钟在生成时的确切时间相同发生了(时间戳是基于毫秒,如果我理解正确的话)....即使这样,数字中有很多其他位是随机的,所以赔率仍然很小.
出于所有实际目的,GUID是普遍独特的.
在"The Old New Thing"博客上有一个很好的MS GUID描述
Kri*_*erA 23
这是一个漂亮的小扩展方法,如果你想在代码中的许多地方检查guid唯一性,你可以使用它.
internal static class GuidExt
{
public static bool IsUnique(this Guid guid)
{
while (guid != Guid.NewGuid())
{ }
return false;
}
}
要调用它,只需在生成新guid时调用Guid.IsUnique ...
Guid g = Guid.NewGuid();
if (!g.IsUnique())
{
throw new GuidIsNotUniqueException();
}
...哎呀,我甚至建议两次打电话来确保它在第一轮中正确.
Ste*_*314 19
数到2 ^ 128 - 雄心勃勃.
让我们想象一下,每台机器每秒可以计算2 ^ 32个ID - 不是那么雄心勃勃,因为它甚至不是每秒43亿.让2 ^ 32台机器专门用于该任务.此外,让每个文明都有2 ^ 32个文明将相同的资源专用于任务.
到目前为止,我们每秒可以计算2 ^ 96个ID,这意味着我们将计算2 ^ 32秒(略超过136年).
现在,我们所需要的只是为每台专用的4,294,967,296台机器获得4,294,967,296个文明,每台机器每秒能够计算4,294,967,296个ID,仅在未来136年左右完成这项任务 - 我建议我们立即开始这项重要任务; - )
kib*_*zer 17
好吧,如果830亿年的运行时间不会吓到你,那么你认为你还需要将生成的GUID存储在某处以检查你是否有重复; 存储2 ^ 128个16字节的数字只需要你预先分配4951760157141521099596496896TB的RAM,所以想象你有一台计算机可以适应所有这些并且你以某种方式找到一个地方购买每个10克的太字节DIMM,它们将结合起来重量超过8个地球质量,因此在你按下"运行"之前,你可以认真地将它从当前的轨道上移开.三思而后行!
Nat*_*lor 12
for(begin; begin<end; begin)
Console.WriteLine(System.Guid.NewGuid().ToString());
你没有增加begin所以条件begin < end总是正确的.
据推测,你有理由相信用于生成Guids的算法不会生成真正的随机数,但实际上是以句点<< 2 ^ 128循环.
例如,用于导出GUID的RFC4122方法,该GUID修复了某些位的值.
骑自行车的证明将取决于该时期的可能规模.
对于小周期,散列哈希表(GUID) - > GUID如果GUID不匹配则在碰撞时替换(如果它们这样做则终止)可能是一种方法.考虑也只是替换随机时间的一小部分.
最终,如果碰撞之间的最大周期足够大(并且事先不知道),任何方法只会产生碰撞的概率(如果它存在的话).
请注意,如果生成Guids的方法是基于时钟的(参见RFC),则可能无法确定是否存在冲突,因为(a)您将无法等待足够长的时间来绕回,或者(b)你不能在时钟刻度内请求足够的Guid来强迫碰撞.
或者,您可能能够显示Guid中的位之间的统计关系,或Guids之间的位相关性.这种关系可能使得算法很有可能存在缺陷,而不一定能够找到实际的碰撞.
当然,如果你只是想证明Guids可以碰撞,那么数学证明而不是程序就是答案.
但你必须确保你有一个重复的,或者你只关心是否有可能是重复的.为了确保你有两个同一个生日的人,你需要366人(不计算闰年).因为有两个人生日相同的可能性超过50%,你只需要23个人.那是生日问题.
如果您有32位,则只需要77,163个值就有超过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位是很多,所以你仍然在谈论大量的物品仍然让你碰撞的可能性很小.使用近似值,您将需要以下给定赔率的记录数:
每年发送大约1E14封电子邮件,所以在这个级别上大约有40万年,然后你有90%的机会拥有两个具有相同GUID的电子邮件,但这与你说需要运行计算机的数量有很大不同.在发现重复之前,宇宙的年龄或太阳会变冷.
我不明白为什么没有人提到升级你的显卡...当然如果你有一个高端的NVIDIA Quadro FX 4800或其他东西(192 CUDA核心),这会更快...
当然,如果您能买得起一些NVIDIA Qadro Plex 2200 S4(每个CUDA核心960个),这个计算真的会让人大惊小怪.也许NVIDIA会愿意借给你一些"技术示范"作为公关噱头？
当然,他们希望成为这一历史性计算的一部分......
难道你不是都错过了一个重点吗？
我认为GUID是使用两个东西生成的,这使得它们在全球范围内的独特性非常高.一个是他们使用您所在机器的MAC地址播种,两个使用它们生成的时间加上一个随机数.
因此,除非您在实际机器上运行它并在机器用于表示GUID中的时间的最短时间内运行所有猜测,否则无论您使用系统调用进行多少猜测,您都不会生成相同的数字.
我想如果你知道制作GUID的实际方式实际上会缩短猜测的时间.
托尼
3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 ?s 374 ns 607 ps在开始运行程序后转到.... 10,783,127即使您有1YHz的CPU 1,000,000,000,000,000(或者1,125,899,906,842,624如果您更喜欢使用二进制前缀)比1GHz CPU快一倍,也需要至少几年.
因此,不是等待计算完成,最好喂养失去家园的鸽子,因为其他n鸽子带回家.:(
或者,您可以等到发明128位量子计算机.然后,您可以通过在合理的时间(可能)使用您的程序来证明GUID不是唯一的.
| 归档时间： |
|
| 查看次数： |
256883 次 |
| 最近记录： |