ホームページ > 記事 > ウェブフロントエンド > JavaScript ランダム シャッフル アルゴリズムの詳細な分析_JavaScript スキル
シャッフルアルゴリズムは、ゲームやランダムソートをプレイするときによく遭遇する一般的なランダム問題です。これは次のように抽象化できます: M 内のすべての自然数のランダムなシーケンス配列を取得します。
Baidu で「シャッフリング アルゴリズム」を検索すると、最初の結果は「Baidu Library-Shuffling Algorithm」です。コンテンツをスキャンすると、多くのコンテンツは、最終的に配列の代わりにリンクされたリストを使用するなど、他の人を簡単に誤解させる可能性があります。また、これは限定的な最適化にすぎません (リンクされたリストでは読み取り効率も低下します)。
この記事の最初の方法は、次のように簡単に説明できます。カードをランダムに引いて、空のカードを引いた場合は、再度カードを引きます。
「空のカードを引いたら、もう一度引きます。」これは、後で空のカードを引く可能性が高くなりますが、これは明らかに不合理です。
ワンステップで最適化できます。カードが削除された後、元のカードが減ります。 (空のカードを残す代わりに)
コードは次のとおりです:
//毎回カードを 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;
}
これも明らかに問題です。配列が非常に大きい場合、途中の要素を削除すると後続のキューが前に進むことになり、非常に時間がかかるアクションとなるからです。
「なぜその要素を削除するのか?」を思い出してください。その目的は空のカードを作成することではありません。
その要素を削除する以外に、空のカードを削除する方法はありますか?
----はい、まだ引かれていない最後のカードを引いた位置に置いただけです。
したがって、このアイデアを次のように最適化できます:
//毎回カードを 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;
}
//1 ラウンド後に i 番目のカードを任意のカードと交換します
for (var i=0; i
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}
カードを引いて交換するというアイデアに加えて、カードを挿入するというアイデアも使用できます。最初に 1 枚のカードがあり、2 番目のカードにはランダムに挿入できる 2 つの位置があります (カードの前後)。 1 番目のカード)、3 番目のカードをランダムに挿入する位置は 3 つあります (最後尾、最初の位置、または 2 番目の位置) など
コードは次のとおりです:
上記のコードにはいくつかの問題もあります。カードの数が増えると、カードを挿入することがますます難しくなります。カードを挿入すると、後続の多くのカードが押し戻されるからです。
もちろん、これを適切に最適化することもできます。最初に n-1 枚のカードがあり、n 番目のカードが最後に配置され、その後任意のカードと位置を交換します。
コードは次のとおりです:
コード全体は次のとおりです。興味のある学生は自分のマシンで試して、それぞれの実行効率と最終結果が理論的にランダムかどうかを確認してください。