[解決済み] JavaScriptのArray.sort()メソッドでシャッフルするのは正しいのか？

質問

ある人のJavaScriptのコードを手伝っていたとき、私の目はそのようなセクションに釘付けになりました。

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

最初に考えたのは おい、こんなのうまくいくわけがない しかし、その後、私はいくつかの実験を行い、少なくともきれいにランダムな結果を提供するようであることを発見しました。

それから私はいくつかのウェブ検索を行い、ほとんど一番上にある の記事 を見つけ、そこからこのコードが最も確実にコピーされていることを知りました。かなり立派なサイトと著者のように見えたのですが...。

しかし、私の直感は、これは間違っているに違いないと告げています。特に、ソート アルゴリズムが ECMA 標準によって指定されていないためです。異なるソート アルゴリズムは、異なる非一様なシャッフルをもたらすと思います。いくつかのソートアルゴリズムは、おそらく無限にループするかもしれません...。

しかし、あなたはどう思いますか？

そしてもう1つの質問として...このシャッフル技法の結果がどれだけランダムであるかを、これからどのように計測すればよいのでしょうか？

を更新しました。 計測を行い、その結果を回答の一つとして以下に掲載しました。

どのように解決するのですか？

この方法は、私の好きなシャッフル方法ではなかったのですが、その理由のひとつは は 実装に依存するためです。特に、Java または .NET (どちらかわからない) からの標準ライブラリのソートは、いくつかの要素間で一貫性のない比較で終わる場合、しばしば検出できることを覚えているようです (たとえば、最初に主張した A < B と B < C が、その後 C < A ).

また、本当に必要以上に複雑な（実行時間の点で）シャッフルとして終わります。

私は、コレクションを効果的に "shuffled" (コレクションの開始時、最初は空) と "unshuffled" (コレクションの残りの部分) に分割するシャッフル アルゴリズムを好みます。アルゴリズムの各ステップで、ランダムにシャッフルされていない要素 (最初の要素でもよい) を選び、それを最初のシャッフルされていない要素と交換します - その後、それをシャッフルされたものとして扱います (つまり、それを含むように精神的にパーティションを移動します)。

これは O(n) であり、乱数生成器への n-1 回の呼び出しを必要とするだけであり、素晴らしいことです。どの要素も、元の位置に関係なく、各スペースで終了する 1/n のチャンスがあります (妥当な RNG を仮定しています)。ソートされたバージョン に近似しています。 に近似しますが (乱数発生器が同じ値を 2 回選ばないと仮定します。乱数倍を返す場合は、その可能性は非常に低いです)、シャッフル バージョンについて推論する方が簡単だと思います :)。

このアプローチは Fisher-Yates シャッフル .

私は、このシャッフルを一度コード化し、アイテムをシャッフルする必要のあるあらゆる場所で再利用することがベストプラクティスであると考えています。そうすれば、信頼性や複雑さの点で、ソートの実装について心配する必要はありません。それはわずか数行のコードです (私は JavaScript で試みるつもりはありません!)。

は シャッフリングに関する Wikipedia の記事 (特にシャッフルアルゴリズムのセクション) はランダムな射影のソートについて述べています。一般的なシャッフルの貧弱な実装に関するセクションを読む価値があり、何を避けるべきかを知ることができます。