非反復乱数列生成アルゴリズム

この記事では、ハッシュテーブルを使用して重複を排除する通常の方法よりもはるかに高速な、繰り返しのない乱数シーケンスを生成する効率的なアルゴリズムについて説明します。

まず、提案を見てみましょう。

正の整数 n が与えられた場合、長さ n の配列を出力する必要があります。配列の要素は 0 ～ n-1 の範囲の乱数であり、要素を繰り返すことはできません。たとえば、n = 3 の場合、要素の範囲が 0 から 2 までの長さ 3 の配列を取得する必要があります。

たとえば、0、2、1。

この問題の通常の解決方法は、ハッシュテーブルを設計し、ループしてランダムな数字を取得し、ハッシュテーブル内でその数字を探すことです。ハッシュテーブルに数字が存在しない場合は、それを出力します。このアルゴリズムのコードは以下の通りである。

公共 静的  int [] GetRandomSequence0( int合計)
 { 
     int [] ハッシュテーブル =新規  int [合計]; 
     int [] 出力 =新規  int [合計]; 
 
    ランダム random = new Random(); 
     ( int i = 0 ; i < 合計; i++)の場合
    { 
         int num = random.Next( 0 , 合計); 
         while (ハッシュテーブル[num] > 0 )
        {
            num = ランダム.Next( 0 , 合計);
        } 
 
        出力[i] = 数値;
        ハッシュテーブル[num] = 1 ;
    } 
 
    出力を返します。
 }

コードは非常にシンプルです。0 から total - 1 までループしてランダムな数字を取得し、ハッシュテーブル内でそれらの数字を一致させようとします。ハッシュテーブルに数字が存在しない場合は、それを出力し、ハッシュテーブルでその数字を 1 に設定します。それ以外の場合は、ハッシュテーブルにない数字が見つかるまでループしてランダムな数字を取得しようとします。このアルゴリズムの問題点は、乱数を取得するために試行し続ける必要があることです。ハッシュテーブルがいっぱいに近づくと、この試行が失敗する確率がどんどん高くなります。

繰り返し試行する必要のないアルゴリズムはありますか?答えはイエスです。

上の図に示すように、n = 4と仮定して順次配列を設計します。

最初のラウンドでは、0から3までの乱数を2として取ります。このとき、配列の2番目の数字を取り出して出力し、この数字を配列から削除します。このとき、配列は次のようになります。

2 回目のラウンドでは、0 から 2 までの乱数を 1 と仮定して、その位置の数字を出力し、配列からこの数字を削除します。これを配列の長さが 0 になるまで繰り返します。すると、ランダムな非繰り返しシーケンスが得られます。

このアルゴリズムの利点は、取得した数値を保存するためのハッシュテーブルを必要とせず、繰り返し試行する必要がないことです。アルゴリズムコードは次のとおりです。

公共 静的  int [] GetRandomSequence1( int合計)
 {
    リスト< int >入力 =新しいリスト< int >(); 
     ( int i = 0 ; i < 合計; i++)の場合
    {
        入力.Add(i);
    } 
 
    リスト< int >出力 =新しいリスト< int >(); 
 
    ランダム random = new Random(); 
     int終了 = 合計; 
     ( int i = 0 ; i < 合計; i++)の場合
    { 
         int num = random.Next( 0 , end);
        output.Add(入力[num]);
        入力.RemoveAt(数値);
        終わり - ;
    } 
 
     output.ToArray()を返します。
 }

このアルゴリズムは 2 つのループを 1 つのループに変更し、アルゴリズムの複雑さを大幅に軽減します。理論上は、速度は最初のアルゴリズムよりも速くなるはずです。しかし、現実はしばしば私たちの想像を超えています。total = 100000 の場合、テスト後、最初のアルゴリズムは 44 ミリ秒かかり、2 番目のアルゴリズムは 1038 ミリ秒かかり、これははるかに遅いです。これはなぜでしょうか?問題の鍵は input.RemoveAt にあります。配列要素を削除する場合、この配列要素の後のすべての要素を 1 つ前に移動する必要があることはわかっています。この移動操作には非常に時間がかかるため、アルゴリズムが遅くなります。この時点で、配列ではなくリンクリストを使用すれば削除が非常に高速になるのでは、と言う人がいるかもしれません。はい、リンクリストは要素の削除の効率性の問題を解決できますが、検索速度が大幅に低下し、配列のように配列要素の添え字に従って要素を直接見つけることはできません。したがって、リンクリストを使用しても機能しません。ここで行き詰まってしまったようです。ハッシュテーブルを使用して繰り返し試すことは可能でしょうか?以下の内容を読む前に、5分間考えてください。

#p#

...5分考えてみましょう

[[20734]]

#p#

アルゴリズムは窓紙の層のようなものです。窓紙を通しては、中に何が入っているかはわかりませんが、一度突き抜けてしまえば、とても単純なもののように見えます。

n = 4 と仮定して、上記と同じ例を使用しましょう。

最初のラウンドでランダムに 2 を取得した場合、配列から 2 を削除するのではなく、配列の最後の要素を 2 の位置に移動します。

配列は

2 回目のラウンドでは、0 から 2 までの乱数を選択します。この時点で、配列内の最後の使用可能な要素の位置は 3 ではなく 2 になっています。このとき得られた乱数が1であると仮定する。

次に、インデックス2の要素をインデックス1に移動し、配列は次のようになります。

n 個の要素が取り出されるまでこれを繰り返します。

このアルゴリズムの利点は、取得した数値を保存するためのハッシュテーブルが不要で、繰り返し試行する必要がなく、前のアルゴリズムのように配列要素を削除する必要がないことです。配列の有効な位置にある最後の要素を毎回現在の位置に移動するだけで済みます。これにより、アルゴリズムの複雑さが O(n) に軽減され、速度が大幅に向上します。

テストの結果、n=100000 の場合、このアルゴリズムには 7 ミリ秒しかかかりません。

以下はこのアルゴリズムの実装コードである。

 /// <要約>  
 /// イーグルトによるデザイン 
 /// </要約>  
 /// <param name="合計"></param>  
 /// <戻り値></戻り値>  
公共 静的  int [] GetRandomSequence2( int合計)
 { 
 
     int [] シーケンス =新規  int [合計]; 
     int [] 出力 =新規  int [合計]; 
 
     ( int i = 0 ; i < 合計; i++)の場合
    {
        シーケンス[i] = i;
    } 
 
    ランダム random = new Random(); 
 
     int終了 = 合計 - 1 ; 
 
     ( int i = 0 ; i < 合計; i++)の場合
    { 
         int num = random.Next( 0 , end + 1 );
        出力[i] = シーケンス[num];
        シーケンス[num] = シーケンス[end];
        終わり - ;
    } 
 
    出力を返します。
 }