配列をシャッフルする次のアルゴリズムに違いはありますか？

Question

私のJavaの教科書を使用すると、ランダムに任意の配列をシャッフルするには、次のコードを使用することができることを言う：

for(int i = myList.length-1; i >=0; i--) 
{ 

    int j = (int)(Math.random() * (i+1)); 
    double temp = myList[i]; 
    myList[i] = myList[j]; 
    myList[j] = temp; 

} 

でしょう私が書いた次のコードは、同じように効率的で有効なのでしょうか？

for(int i = 0; i < myList.length; i++) 
{ 

    int j = (int)(Math.random() * (myList.length)); 
    double temp = myList[i]; 
    myList[i] = myList[j]; 
    myList[j] = temp; 

} 

私のコードをテストして、要素を適切にシャッフルします。これ以上のテキストブックのアルゴリズムを使用する理由はありますか？

Answer 1

これ以上のテキストブックのアルゴリズムを使用する理由はありますか？

号あなたのコードとテキストブックの両方が乗数の値に基づいたロケット科学を持っていません。コア部分はMath.random()関数です。あなたの本の乗数はjの値を繰り返し得る確率が数学的に低いi+1ですが、コードはちょうど繰り返しjの値を返す可能性が少し高いですが、率直に言っても問題ありません。

あなたのコードは、実際にはほんのわずかですが、実際には加算操作が実行されないたびに無視できるほど速くなります。

Answer 2

第1の例は、要素がランダムに配置される方法の公平性を保証するために好ましい。 2番目の例では、要素はランダムですが、等しくランダムではありません。

最初の例は、Math.randomを使用しない最適化バージョンに基づいています。同じものであるCollections.shuffle

 for (int i=size; i>1; i--) 
      swap(list, i-1, rnd.nextInt(i)); 

から

Random rand = ... 
for(int i = myList.length-1; i > 0; i--) { 
    int j = rand.nextInt(i+1); 
    double temp = myList[i]; 
    myList[i] = myList[j]; 
    myList[j] = temp; 
} 

。

これは計算が少なくて済むような「ランダム性」を生成する必要がないため、かなり高速になる可能性があります。 doubleを生成するのは、0から9のような小数よりはるかに高価です。

ただし、最初の例ではこれを利用せず、Math.random（）を呼び出しています。 nextInt(n)

Answer 3

いいえ、本のアルゴリズムの代わりにアルゴリズムを使用することはできません。

---

説明：あなたの本のアルゴリズムは、最後の1から始めて、現在の要素から始まり、その後、[0, current]内のすべての要素から別の要素をピックアップし、それらを交換。この方法では、高いインデックスの要素は決して再び触れることはできません。しかし、それはまだそれ自身とスワップすることになります（通常です）。

ただし、アルゴリズムでは、0とi - 1の間のすべての可能なインデックスからスワップするランダムインデックスを生成しています。したがって、より高いインデックス要素は、シャッフル中に元の位置に戻すことができます。

---

次のコードは、書籍のアルゴリズムと同じではありません。これは、あなたの本のアルゴリズムの場合に可能な要素をそのまま残しません。

for (int i = myList.length - 1; i > 0; i--) { 
    int j = (int)(Math.random() * i); 
    swap(myList, i, j); 
} 

private void swap(double[] myList, int i, int j) { 
    double temp = myList[i]; 
    myList[i] = myList[j]; 
    myList[j] = temp; 
} 

Answer 4

はい、実際は異なっています。

最初のアルゴリズムは古典的なKnuth Shuffleの変形です。 このアルゴリズムでは、私たちの乱数生成器（Math.random()）が理想的なものであれば、n！ （n階乗）の可能性のある置換を等確率で使用する。

---

第2のアルゴリズムにはこのプロパティはありません。 たとえば、n = 3の場合、3つの結果があり、3で均等に割り切れません。3 = 27です。 = 6、可能な順列の数。 が実際に、ここでの結果（：12プログラム統計を生成する）の確率である

[0, 1, 2] 4/27 
[0, 2, 1] 5/27 
[1, 0, 2] 5/27 
[1, 2, 0] 5/27 
[2, 0, 1] 4/27 
[2, 1, 0] 4/27 

N = 4の場合、結果はさらに不均一である（例えば、プログラムは、統計を生成する：34）：

[1, 0, 3, 2] has probability 15/256 
[3, 0, 1, 2] has probability 8/256 

あなたの順列が一様にランダムであると思われる場合、これは望ましくない性質です。

---

最後に、真のランダムソースではなく擬似乱数ジェネレータを通常使用するという事実は、上記のいずれかを無効にしません。 私たちの乱数ジェネレータの欠陥は、もしあれば、明らかに後のステップでダメージを修復することができません。