JavaScript ランダム シャッフル アルゴリズムの詳細な分析_JavaScript スキル

シャッフルアルゴリズムは、ゲームやランダムソートをプレイするときによく遭遇する一般的なランダム問題です。これは次のように抽象化できます: M 内のすべての自然数のランダムなシーケンス配列を取得します。

Baidu で「シャッフリング アルゴリズム」を検索すると、最初の結果は「Baidu Library-Shuffling Algorithm」です。コンテンツをスキャンすると、多くのコンテンツは、最終的に配列の代わりにリンクされたリストを使用するなど、他の人を簡単に誤解させる可能性があります。また、これは限定的な最適化にすぎません (リンクされたリストでは読み取り効率も低下します)。

この記事の最初の方法は、次のように簡単に説明できます。カードをランダムに引いて、空のカードを引いた場合は、再度カードを引きます。
「空のカードを引いたら、もう一度引きます。」これは、後で空のカードを引く可能性が高くなりますが、これは明らかに不合理です。
ワンステップで最適化できます。カードが削除された後、元のカードが減ります。 (空のカードを残す代わりに)
コードは次のとおりです:

コードをコピーしますコードは次のとおりです:

function shuffle_pick_1(m) //シャッフル//カード描画メソッド
{
//m 枚のカードを生成
var arr = new Array(m);
for (var i=0 ; i arr[i] = i;
}

//毎回カードを 1 枚引き、別の山に置きます。配列から要素を抽出し、後続の要素をすべて 1 つずつ進める必要があるため、非常に時間がかかります。
var arr2 = new Array();
for (var i=m; i>0; i--) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}

これも明らかに問題です。配列が非常に大きい場合、途中の要素を削除すると後続のキューが前に進むことになり、非常に時間がかかるアクションとなるからです。
「なぜその要素を削除するのか?」を思い出してください。その目的は空のカードを作成することではありません。
その要素を削除する以外に、空のカードを削除する方法はありますか?
----はい、まだ引かれていない最後のカードを引いた位置に置いただけです。
したがって、このアイデアを次のように最適化できます:

コードをコピー コードは次のとおりです。

function shuffle_pick(m) //shuffle/ /pump カード最適化カード
{
// m 枚のカードを生成
var arr = new Array(m);
for (var i=0; i arr [i] = i;
}

//毎回カードを 1 枚引き、別の山に置きます。引いていない最後のカードを空いた席に置きます。
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2 .push(arr[rnd]);
arr[rnd] = arr[--i];
}
return arr2;
}

描画を除くカードのアイデアとしては、カードを変更するというアイデアも使用できます。
「Baidu Wenku - Shuffle Algorithm」では、カードを変更するアイデアについて言及しています。「2 つの位置をランダムに合計 n 回交換します。n が大きいほど、ランダムに近づきます。」
このアプローチは間違っています。n が非常に大きい場合 (たとえば、10 枚のカード、10 回のスワップ)、「一部のカードの位置がまったく変更されていない」可能性が依然として高くなります。
このアイデアに従って、少し調整するだけです。i 番目のカードの位置を他のカードに変更して、ラウンドを終了します。
コードは次のとおりです:

コードをコピー コードは次のとおりです。

function shuffle_swap(m) //shuffle/ /swap Card メソッド
{
// m 枚のカードを生成
var arr = new Array(m);
for (var i=0; i arr[ i ] = i;
}

//1 ラウンド後に i 番目のカードを任意のカードと交換します
for (var i=0; i var rnd = Math.floor( Math.random()* (i 1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}

カードを引いて交換するというアイデアに加えて、カードを挿入するというアイデアも使用できます。最初に 1 枚のカードがあり、2 番目のカードにはランダムに挿入できる 2 つの位置があります (カードの前後)。 1 番目のカード)、3 番目のカードをランダムに挿入する位置は 3 つあります (最後尾、最初の位置、または 2 番目の位置) など
コードは次のとおりです:

コードをコピーします コードは次のとおりです。

function shuffle_insert_1(m) //shuffle/ /insert Card メソッド
{
//毎回最大のカードを生成し、ランダムなカードの前に挿入します。要素を配列に挿入し、後続の要素をすべて 1 つの位置に戻す必要があるため、非常に時間がかかります。
var arr = [0];
for (var i=1; i arr.splice(Math.floor(Math.random()*(i 1)), 0,i);
}
return arr;
}

上記のコードにはいくつかの問題もあります。カードの数が増えると、カードを挿入することがますます難しくなります。カードを挿入すると、後続の多くのカードが押し戻されるからです。
もちろん、これを適切に最適化することもできます。最初に n-1 枚のカードがあり、n 番目のカードが最後に配置され、その後任意のカードと位置を交換します。
コードは次のとおりです:

コードをコピー コードは次のとおりです。

function shuffle_insert(m) //shuffle/ /insert カード メソッドの最適化されたバージョンは、この種のシャッフルが均一であることを数学的帰納法によって証明できます。
{
//毎回最高のカードを生成し、ランダムなカードと場所を交換します
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i var rnd = Math.floor(Math.random()*(i 1));
arr[i] = arr[rnd] ;
arr [rnd] = i;
}
return arr;
}

コード全体は次のとおりです。興味のある学生は自分のマシンで試して、それぞれの実行効率と最終結果が理論的にランダムかどうかを確認してください。

コードをコピー コードは次のとおりです:

< title>JK：JavaScript シャッフル アルゴリズム