random - 繰り返さない乱数

Question

ゼロから生成された数値の量まで、約 900 万から 100 万の非反復乱数を生成する必要があり、それらを非常に迅速に生成する必要があります。同様の質問に対するいくつかの回答は、乱数を取得するために配列を単純にシャッフルすることを提案し、他の回答はブルーム フィルターを使用することを提案しました。問題は、どちらがより効率的かということです。ブルーム フィルターの場合、どのように使用すればよいでしょうか。

Answer 1

乱数はまったく必要ありません。ランダムな順序で、正確に 0 から N-1 までの数字が必要です。

配列を埋めてシャッフルするだけで、非常に高速になります。適切なフィッシャー・イェーツ シャッフルは O(n) であるため、1 億の配列は C や Java でさえ 1 秒をはるかに下回る必要があり、Python のような高レベル言語ではわずかに遅くなります。

シャッフルを行うには N-1 個の乱数を生成するだけで済みます (完全な均一性を得るために拒否サンプリングを使用する場合は最大 1.3N になる可能性があります)。そのため、速度は RNG の速度に大きく依存します。

数値が既に生成されているかどうかを調べる必要はありません。特に実行の終わりに向かって、使用するアルゴリズムに関係なく、致命的に遅くなります。

必要な合計数が N よりもわずかに少ない場合は、配列を 0 から N-1 まで埋めてから、シャッフルを早期に中止して部分的な結果を取得します。必要な数値の量がその範囲に比べて非常に少ない場合にのみ、重複を生成してチェックするアプローチを検討する必要があります。その場合、Bob Floyd のアルゴリズムが良いかもしれません。

Answer 2

代わりに、適切なサイズのブロック暗号を使用できます。ブロック暗号を使用して数字 0、1、2、... を暗号化すると、一連の繰り返さない乱数が得られます。どのシリーズが正確に使用するキーによって異なります。ブロック暗号は可逆順列であるため、繰り返さないことが保証されています。

64 ビットの数値の場合はDESを使用し、32 ビットの場合はHasty Pudding (広範囲のブロック サイズを使用できます) を使用するか、独自の単純なFeistel cypherを記述します。セキュリティがこれにとって大きな問題ではないと仮定すると、独自に作成することが可能です。