長くて繰り返しのない乱数列を効率的に生成するにはどうすればよいでしょうか?

繰り返しのない乱数列の生成

コンピューター プログラミングでは、繰り返しのない乱数列を生成するのが一般的なタスクです。この問題は、生成する数値の範囲が大きくなり、範囲全体をシャッフルしたり重複をチェックしたりすることが非効率になる場合に発生します。

この問題に対する 1 つのアプローチは、線形フィードバック シフト レジスタ (LFSR) を使用することです。 LFSR は、一部のビットが XOR 演算されて入力にフィードバックされるシフト レジスタです。タップ (フィードバックされるビットの位置) を慎重に選択することにより、LFSR は、繰り返しのない、レジスタ サイズと同じ長さのシーケンスを生成できます。

たとえば、16 ビット LFSR は、繰り返しなしで長さ 65535 のシーケンスを生成します。これは統計的にランダムなシーケンスですが、非常に反復性が高いため、一部のアプリケーションでは望ましくない場合があります。

多数の非反復的なランダム シーケンスが必要な場合は、別のアプローチが必要です。 1 つのオプションは、ハッシュ関数を使用して入力範囲をより小さい出力範囲にマップすることです。より小さい範囲内で乱数を生成し、ハッシュ化することで、一意の出力番号を取得できます。このプロセスは、必要な長さのシーケンスが生成されるまで繰り返すことができます。

もう 1 つのアプローチは、擬似乱数発生器 (PRNG) を使用して乱数シーケンスを生成し、重複をフィルターで除外することです。これは、ハッシュ テーブルやセットなどのデータ構造を使用して効率的に実行できます。このアプローチの欠点は、生成された数値をメモリに保存する必要があり、大規模なシーケンスの場合は制限となる可能性があることです。

以上が長くて繰り返しのない乱数列を効率的に生成するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。