32 ビットのランダムな int を生成する必要がありますが、いくつかの引数によって異なります。アイデアは、独自の P2P ネットワークを介して送信するメッセージごとに一意の ID を生成することです。それを生成するには、引数として、私の IP とタイム スタンプが必要です。私の質問は、これらの引数からこの 32 ビットのランダムな int をどのように生成できますか?
再度、感謝します！
2968 次
3 に答える
3
関連する問題を含むオプションのリストを次に示します。
乱数を使用します。約半分のビットで衝突 (一意でない値) が発生します (これが「誕生日衝突」です)。したがって、32 ビットの場合、2*16 メッセージの後に衝突が発生します。65,000 未満のメッセージを送信する場合、これは問題ではありませんが、65,000 はそれほど大きな数ではありません。
一部のサービスからの順次カウンターを使用します。これがtwitterのsnowflakeの機能です（別の回答はこちらを参照）。問題は、これらをネット経由で提供することです。通常、分散システムでは、各エージェントに一連の数字を与え (A は 0 ～ 9、B は 10 ～ 19 など)、それらの数字を使用して新しいブロックを要求します。これにより、ネットワーク トラフィックとサービス提供番号の負荷が軽減されます。しかし、これは複雑です。
一意になるいくつかの値からハッシュを生成します。これは便利に聞こえますが、ハッシュが衝突するため、(1) よりも優れているわけではありません (理由は以下で説明します)。したがって、IP アドレスとタイムスタンプをハッシュすることはできますが、実際には 32 ビットの乱数を生成するだけです (違いは、これらの値を再現できることですが、とにかくその機能は必要ないようです)。そのため、65,000 件程度のメッセージの後で衝突が発生しますが、これはそれほど多くはありません。
一意性を保証するためにIDを生成することについてより賢くしてください。(3) の問題は、32 ビットを超えるハッシュを行っているため、情報が圧縮され、オーバーラップが発生していることです。代わりに、衝突を避けるためにビットを明示的に管理できます。たとえば、各クライアントに 16 ビットの番号を付け (最大 65,000 クライアントを許可)、各クライアント ユーザーに 16 ビット カウンターを割り当てます (クライアントごとに最大 65,000 メッセージを許可します。これは (3) の大幅な改善です)。それぞれが一意であることが保証されているため、これらは衝突しませんが、システムには多くの制限があり、複雑になり始めています (クライアントに番号を付け、クライアントごとにカウンター状態を保存する必要があります)。
より大きなフィールドを使用します。64 ビット ID を使用した場合、衝突は 2**32 メッセージごとに 1 回発生するため、乱数を使用できます。または、IP アドレス (32 ビット) と 32 ビットのタイムスタンプを結合することもできます (ただし、クライアントからのメッセージは 1 秒あたり 1 件以下であることを意味するので注意してください)。唯一の欠点は帯域幅がわずかに大きいことですが、ほとんどの場合、id はペイロードよりもはるかに小さいです。
個人的には、より大きなフィールドと乱数を使用します。これはシンプルで機能します (ただし、組み込みシステムでは適切な乱数が問題になります)。
最後に、値を「本当に」ランダムにする必要がある場合 (たとえば、id を使用して優先順位を決定し、物事を公平にしたい場合)、上記の解決策のいずれかを決定論的な値で使用して、ビットを疑似ランダムにします。たとえば、カウンタのビットを逆にするだけで十分な場合があります (最初に lsb を比較します)。
于 2013-10-25T12:12:04.960 に答える