少人数学校での試験。みなさんこんにちは。 正統的な見地からすれば、今日は本当の金曜日ではなく、明日が休みの日です。 したがって、私の従来のセクションの記事も完全に現実的なものではなく、狂気の程度を減らし、実用性を高めています。 しかし、かなり序文、ポイントに行きましょう。
-ここを見て。 これは親指、これは人差し指、これは中指、これは薬指、これは小指です。 私たちは干渉し、干渉し、干渉します（彼の指を動かします）...今はどこですか？
私の生徒は、アレイをランダムにミキシングするタスクを定期的に取得します。 彼女の決定のために、彼らは通常Googleに登ります。 そして、Googleは彼らに次のように伝えます：
var shuffledArr = arr.sort(function(){ return Math.random() - 0.5; });
以下、このメソッドをランダムソートと呼びます。 今日、私はこのアプローチの長所と短所について書くことにしました。
それはどのように機能しますか？
javascript配列のsortメソッドは、引数としてコンパレータ関数を受け入れます。 この関数は、配列の2つの要素を取り、数値を返す必要があります。 数値が正の場合、ソートアルゴリズムは最初の要素が大きいと見なします。 負の場合、最初の要素は小さくなります。 コンパレータがゼロを返す場合、このソートのフレームワークでは、要素は等しいかのようになります。 比較器を装って、正または負の数をランダムに返す関数を渡すと、配列は「ランダム」な順序でソートされます。
メリット
このようなミキシングは非常に迅速に記述されます。 私は正直に他の利点を考え出そうとしましたが、失敗しました。
短所
この段落は少し長くなるので、サブパラグラフに分けます。
仕様の不一致
EcmaScript仕様 （私は意図的にバージョンに名前を付けません。すべてのバージョンでこのアイテムがほぼ同じままであるため）は、次のことを示しています。
comparefnが未定義でなく、この配列の要素の一貫した比較関数ではない場合（以下を参照）、ソート順は実装定義です。
技術的な英語からロシア語の口語に翻訳すると、これは、コンパレーターがいくつかの明白な要件を満たしていない場合（特に、同じ引数に対して常に同じ値を返す必要があることを仕様がさらに説明している場合）、特定のJavaScriptエンジンの実装に依存します。 つまり、実際には定義されていません。 たとえば、ブラウザ開発者には、コンパレータが「偽物」であることを検出したときに、順列なしで元の配列が返されるようにするためのすべての権利があります。 そして、仕様に完全に準拠します。 既存のすべてのブラウザーで、指定されたメソッドがランダムミキシングに似たものを提供するという事実は、幸運な偶然にすぎません。
時間の複雑さ
正しいミキシングアルゴリズム（以下を参照）の時間計算量はO（n）です。 簡単に言えば、これは次のようなことを意味します。配列の長さが10倍になると、その混合時間も10倍になります。
最速のソートアルゴリズムの時間の複雑さはO（n * log（n））です。 これは、アレイの長さが10倍長くなると、その混合時間は10倍以上長くなることを意味します。
要するに、これら2つの事実はこれを意味します。十分に大きい配列の場合、ランダムなソートは「正しい」ミキシングよりも遅くなります（たとえ小さい配列の場合はそうではありませんが）。 また、配列が大きいほど、実行時の差が大きくなります。
なぜ括弧で予約したのですか？ Array＃sortはネイティブコードによって実行されるため、これにより、小さな配列では潜在的に高速になる可能性があります。 O表記に精通している人は、定数係数が小さい場合があると言うでしょう。
偽のチャンス
少なくとも表面的に確率論に精通している人は、ランダム性がランダムであることを知っています。 コインは頭または尾で落とすことができ、立方体は6個または6個ではなく落とすことができます。 そこにはランダムなイベントがありますが、最初のケースではイベントが同様に発生する可能性があり、2番目のケースでは発生しません。
配列のシャッフルは、その要素の可能なすべての順列が同じ確率を持つ場合、真にランダムと呼ばれます。 ランダムソートにはこのプロパティはありません。実際に示します。
次のページをスケッチしました。 2つの図があり、1つはランダムミキシングに対応し、2つ目はランダムソートに対応しています。 ただし、図ではなく正方形がさまざまな灰色のセルに分割されています。 図になるには、凡例、つまりこれらのセルとその色の意味の説明が必要です。 すべてが非常に簡単です。 数回（この場合は数= 10000）を取り、0からn（この場合はn = 32）の数値の配列を取り、ランダムに1つまたは別のアルゴリズムと混合します。 次に、ある場所または別の場所で1つまたは別の番号が使用される頻度を計算します。 したがって、行番号iおよび列番号jのセルの色は、jの代わりに番号iが表示される頻度を示します。 黒はそこに表示されないことを意味し、白は必要以上に2回以上表示されることを意味します。 数値が理論的に予測された1 / nの頻度で示された場所に落ちた場合、セルの色はhsl（0、0％、50％）になります-黒と白のちょうど中間に位置する灰色の陰影。
Chromeブラウザの最新バージョンを使用している場合、右側の四角には、特定のパターンに従って配置された白いセルまたはほぼ白いセルが多数あることがわかります。 つまり、ランダムソートでは、特定の要素が特定の場所に表示される傾向があります。 悪いですか？ 攪拌の目的に依存します。 化粧品の効果については、おそらく、大丈夫です。 ユーザーがどの要素がどの場所に現れるかを予測できないことが重要な場合、またはミキシングのパターンが何らかの形で視覚的に目立つ場合、それは悪いことです。 また、エルメスは、暗号化に関連する何かにこのようなミキシングを使用することを禁止しています。
驚くべきことは、Firefoxを使用している場合、両方の正方形がほぼ等しく灰色になっていることです。 これは、異なるブラウザーが異なるソートアルゴリズムを使用しているためです（興味がある場合は、このトピックに関する私の記事を参照してください ）。 この場合、再び驚きたい場合は、アドレスバーにサイズ= 8を追加します（レイジーの完成したリンクがあります）。 Firefoxは、大きな配列と小さな配列を異なる方法でソートします。
更新：同志mk2 は 、Firefoxの正方形が2の累乗に等しいサイズでのみ均一に灰色になることに気付きました。 もっと注意深い同志、同志がもっと必要です！
Upd2：仲間のStalker_REDとyaZvaは、 （私とは違って）さまざまなブラウザーでスクリーンショット を作成するの が面倒ではありませんでした。
結論として、これら50個のグレーチャートは、基準ではなく、サインであると付け加えます。 正方形は灰色ではないことが判明したため、並べ替えは均一ではありませんが、逆は当てはまりません。 反例は、ランダム変数による循環シフトです。 所定の位置に収まる要素の周波数はまったく同じになりますが、もちろん、混合の真のランダム性について話すことはできません。
Upd3： このスレッドでは、Firefoxでランダムソートが均一なランダム性を与えない理由について説明しています（図が表示されている場合でも）。
どうですか？
True Jediは、Fisher-Yatesアルゴリズムのバリエーションの1つを使用します 。 デモでは、次のように実装しました。
function shuffle(arr){ var j, temp; for(var i = arr.length - 1; i > 0; i--){ j = Math.floor(Math.random()*(i + 1)); temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } return arr; }
アルゴリズムの本質は、JSからロシア語に翻訳された場合、次のとおりです。最後の要素を取得し、その要素を右側にないランダムに選択された要素と交換します（おそらく自分で）。 次に、最後から2番目の要素に対して同じ操作を繰り返し、最後から2番目の要素に対して同様の操作を繰り返します。 出来上がり！ （この単語は「return arr;」をJSからロシア語に翻訳します）。
狂気の時だ
一部の読者はこの記事全体を待っていましたが、残りは原則としてこの段落を読んでいない可能性があります。 私は疑問に思いました：arr.sort（compare）が本当にランダムな順列を与えるような比較関数を書くことは可能ですか？ 回答：可能ですが、特定の予約が必要です。 まず、各ソートの前に関数を再作成する必要があります。 2番目-配列は同じ要素を持つべきではありません。 だから、見よ：
// function putToCache(elem, cache){ if(cache.indexOf(elem) != -1){ return; } var i = Math.floor(Math.random()*(cache.length + 1)); cache.splice(i, 0, elem); } //, , function madness(){ var cache = []; return function(a, b){ putToCache(a, cache); putToCache(b, cache); return cache.indexOf(b) - cache.indexOf(a); } } // function shuffle(arr){ var compare = madness(); return arr.sort(compare); }
これは次のように機能します。作成時に、クロージャを介したコンパレータがキャッシュ配列にアクセスします。 引数が彼に渡されるたびに、彼はそれらをランダムな場所のキャッシュに入れます（まだ存在しない場合）。次に、右側のキャッシュにある要素が大きくなると考えます。 つまり、実際には、キャッシュ配列では、要素が置かれるべきランダムな順序が徐々に構築され、ソート方法はこの順序に従って元の配列を徐々にもたらします。 等しい要素が含まれている場合（===演算子の観点から等しい、オブジェクトをソートする場合は、同じ内容であってもすべてが正常です。{A：1}！== {a：1}）、残念ながら、彼らは連続して行きます。
それだけです 読んでくれてありがとう、私はあなたが有益であったことを望みます、そして、私はあなたがほとんど決して決してランダムな分類を使わないように確信させたことを特に望みます。 良い夜を。