Array.sort() は配列をシャッフルできますか? シャッフルできる場合、どの程度ランダムですか?

Array.sort() を使用して配列をシャッフルできますか?

最初は懐疑的でしたが、Array.sort() メソッドは確かにシャッフルできます。配列のシャッフルに使用されます。その仕組みは次のとおりです:

シャッフルに Array.sort() を使用することの長所と短所

利点:

• シンプルさ: 実装は簡単です。 JavaScript の組み込みソート機能を利用します。
• 有効性: ほとんどの実用的な目的では、適切にランダム化された結果が生成されます。
• パフォーマンスへの影響は限定的です:並べ替えアルゴリズムの時間計算量は通常 O(n log n) ですが、使用されるランダム化関数 (Math.random()) は O(1) です。これにより、カスタム シャッフル アルゴリズムを使用する場合と比較して、パフォーマンスがわずかに向上する可能性があります。

欠点:

• 不均一な分散: 並べ替えアルゴリズムの実装は結果の分布に影響を与える可能性があり、不均一な結果が生じる可能性があります。
• 並べ替えアルゴリズムへの依存: シャッフルの有効性は、Array.sort() メソッドで使用される並べ替えアルゴリズムによって異なります。
• Infiniteループ: 一部の並べ替えアルゴリズムは、特定の入力が次の場合に無限ループに入る可能性があります。

結果のランダム性の測定

シャッフル手法のランダム性を定量化するには、経験的テストを実行し、結果を期待値と比較できます。 。たとえば、考えられる各置換の確率を計算し、それを一様分布と比較できます。

代替シャッフリング アルゴリズム (Fisher–Yates)

配列を使用します。 sort() は便利ですが、より最適でよく知られているシャッフル アルゴリズムは Fisher-Yates です。 shuffle:

function shuffle(array) {
  var tmp, current, top = array.length;

  if (top) while (--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

このアルゴリズムは効率的 (O(n)) であり、結果の均一な分散を保証します。

以上がArray.sort() は配列をシャッフルできますか? シャッフルできる場合、どの程度ランダムですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。