9

Guid.NewGuid最近、このメソッドで生成されたグローバルに一意の識別子のランダム性の程度を調査することにしました(これもこの質問の範囲です)。私は疑似乱数、疑似乱数性について自分自身を文書化しましたが、放射性崩壊によって生成された乱数さえあることを知って目がくらみました。いずれにせよ、このような興味深い講義の詳細については、ご自身でご確認ください。

私の質問を続けるには、 GUIDについて知っておくべきもう1つの重要なことは次のとおりです。

MAC アドレスと時間を含む V1 GUID は、3 番目のグループの数字の最初の位置にある数字「1」によって識別できます (例: {2F1E4FC0-81FD-11DA-9156-00036A0F876A})。

V4 GUID は、疑似乱数である後者のアルゴリズムを使用します。{38A52BE4-9352-453E-AF97-5C3B448652F0} のように、同じ位置に「4」があります。

一言で言えば、 aGuidは常に数字の 4 (または 1 ですが、ここでは範囲外です) を構成要素の 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 では、3 番目のグループの最初の文字は です4。4 番目のグループの最初の文字は、、、、8またはのいずれか9です。仕様は、4 番目のグループの最初の文字がどのように生成されるかについて何も述べていません。それはあなたの結果を台無しにする可能性があります。ab

さらに調査する場合は、各 16 進数が各位置に出現する頻度を追跡する必要があります。これで違いが明らかになり、理論上の推定値がずれているのか、疑似乱数アルゴリズムがわずかに偏っているのかを判断するのに役立つと思います。

于 2013-01-30T03:42:09.783 に答える
7

ジムはそれを理解しました（私はちょうどこの質問を見つけました。その答えはv4 guid生成に同じ刺激を与えました）。

したがって、この新しい知識で期待される方程式を変更することにより、次のようになります。((10/16)*30+1+0.5)/32または(10M * 100 / 16) * 30 / 32 + (150M / 32)、これは約63.28％であり、取得した実験データにかなり近いものです。

于 2013-01-30T04:07:21.173 に答える