9

最近我决定研究使用该Guid.NewGuid方法生成的全局唯一标识符的随机性程度（这也是这个问题的范围）。我记录了自己关于伪随机数、伪随机性的信息，我惊讶地发现甚至还有放射性衰变产生的随机数。无论如何，我会让你自己发现更多关于这些有趣讲座的细节。

继续我的问题，关于GUID的另一件重要的事情是：

包含 MAC 地址和时间的 V1 GUID 可以通过第三组数字的第一个位置的数字“1”来标识，例如 {2F1E4FC0-81FD-11DA-9156-00036A0F876A}。

V4 GUID 使用后一种算法，它是一个伪随机数。它们在相同的位置有一个“4”，例如 {38A52BE4-9352-453E-AF97-5C3B448652F0}。

用一句话来说，aGuid将始终将数字 4（或 1，但超出我们的范围）作为其组成部分之一。

对于我的 GUID 随机性测试，我决定计算一些越来越大的 GUID 集合中的数字数量，并将其与数字出现的统计概率进行比较，expectedOccurrence. 或者至少我希望我做到了（请原谅任何统计公式错误，我只是尝试了我最好的猜测来计算值）。我使用了C#下面列出的小型控制台应用程序。

class Program
{
    static char[] digitsChar = "0123456789".ToCharArray();
    static decimal expectedOccurrence = (10M * 100 / 16) * 31 / 32 + (100M / 32);
    static void Main(string[] args)
    {
        for (int i = 1; i <= 10; i++)
        {
            CalculateOccurrence(i);
        }
    }

    private static void CalculateOccurrence(int counter)
    {
        decimal sum = 0;
        var sBuilder = new StringBuilder();
        int localCounter = counter * 20000;
        for (int i = 0; i < localCounter; i++)
        {
            sBuilder.Append(Guid.NewGuid());
        }

        sum = (sBuilder.ToString()).ToCharArray()
                  .Count(j => digitsChar.Contains(j));

        decimal actualLocalOccurrence = sum * 100 / (localCounter * 32);

        Console.WriteLine(String.Format("{0}\t{1}",
            expectedOccurrence,
            Math.Round(actualLocalOccurrence,3)
            ));
    }
}

上述程序的输出是：

63.671875       63.273
63.671875       63.300
63.671875       63.331
63.671875       63.242
63.671875       63.292
63.671875       63.269
63.671875       63.292
63.671875       63.266
63.671875       63.254
63.671875       63.279

因此，即使预计理论发生率是63.671875%，实际值也在 附近~63.2%。

如何解释这种差异？我的公式有错误吗？算法中还有其他“晦涩”的规则Guid吗？

4

2 回答 2

9

在版本 4 GUID 中，第三组中的第一个字符是4. 第四组中的第一个字符是8、9、a或中的一个b。该规范没有说明如何生成第四组中的第一个字符。这可能会影响你的结果。

如果您想进一步调查，您需要跟踪每个十六进制数字在每个位置出现的频率。我怀疑这会揭示差异，并帮助您确定您的理论估计是否存在偏差，或者伪随机算法是否略有偏差。

于 2013-01-30T03:42:09.783 回答
7

Jim 明白了（我刚刚发现这个问题的答案对 v4 guid 的生成产生了同样的影响）。

因此，通过使用这些新知识改变预期方程，您会得到：((10/16)*30+1+0.5)/32或(10M * 100 / 16) * 30 / 32 + (150M / 32)，大约为 63.28%，与您获得的实验数据非常接近。

于 2013-01-30T04:07:21.173 回答