他のシャッフルアルゴリズムとの比較
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/27 02:05 UTC 版)
「フィッシャー–イェーツのシャッフル」の記事における「他のシャッフルアルゴリズムとの比較」の解説
フィッシャー–イェーツのシャッフルは極めて効率的であり、時間的空間的な計算量は最適である。偏りのない良質な乱数をもとにするならば、生成結果も偏りがないことが保証される。他のアルゴリズムと比較してもその長所は変わらない。もしも結果の順列の一部のみが必要であれば、必要な数の順列が生成された時点で処理を中断すればよい。 異なるシャッフルの手法としては、集合のそれぞれの要素にランダムな番号を付与し、その後にそれらをソートする方法がある。ソートによる手法は、フィッシャー–イェーツのシャッフルとは時間的計算量は同一である。ただし、一般的なソート法の計算量は O(n log n) であり、効果的に処理するためには時間的計算量が O(n) の基数ソートを用いる必要がある。ソートによる手法も、フィッシャー–イェーツのシャッフルと同じく偏りのない結果を生成するが、ランダムな番号を付与する際に重複しないように注意しなければならない。なぜならソートのアルゴリズムは同じ値の要素を並べる際はランダムにならないからである。さらにこの手法では、付与する番号のために空間的計算量 O(n) となる追加領域を必要とする。対してフィッシャー–イェーツのシャッフルでは O(1) である。ソートによる手法は番号を付与するため、フィッシャー–イェーツのシャッフルとは異なり、並列的な動作を行う。 シャッフルによる手法の派生として、プログラミング言語がサポートしている、ユーザ独自拡張の比較機能を使用して、比較時にランダムな値を返すようにしてシャッフルを行う方法がある。しかし、これは「きわめて悪い方法」であり、この方法は結果がまったく均等に分布せず、ソートのアルゴリズムもきわめて重い。ソートのアルゴリズムにクイックソートを実装されている場合を考える。このとき、はじめに選択されるピボット（英語版）は固有の要素とする。このアルゴリズムはピボットとその他の要素すべてを比較し、大小を分割し、大小それぞれのグループのサイズによりピボット要素の最終位置が決められる。乱数列が均一に分布されるためには、ピボット要素の最終位置はどの位置にも等しく配置される可能性がなければならない。しかし、はじめの比較において、「より小さい」「より大きい」の判定を等しく行ってしまうため、ピボット要素位置の確率は p = 1/2 の二項分布をとる。つまり、両端よりも中央に近い方に配置されてしまう可能性が高い。マージソートのような違ったソート法でランダムな比較を使用した場合、より均一な結果を取得できることもある。しかしそれも完全ではない。マージソートの場合、二つの数列の中からどちらかの数値を同確率で選択していくことで、その数列を結合する。この「コイントス」のような、2通りからランダムに取得する手法を繰り返す場合、(数列が2よりも大きい場合は)均一な分布となることはない。なぜなら、この方法による、ある順列が生成される確率は2の階乗を分母とする値であるはずであり、求められている確率は 1/n! となるからである。 そしてこのシャッフル方法は、原理的に無限ループやアクセス違反などのプログラム実行時のエラーを引き起こすことさえある。なぜなら、ソートアルゴリズムがランダムに動作する場合は順序関係（例えば推移関係)が正しく提供されないためである。以前の比較結果に依存するような、確実に結果が予測されうるような比較を行うような振る舞いはソートの手順の中で行われるべきではないが、意図的にこのような比較を行う明確な理由がある場合は別である。例えば、効率化のために、番兵として自分自身との比較を行うような場合は、ランダムな比較関数はこのソートのアルゴリズムを破壊するだろう。
※この「他のシャッフルアルゴリズムとの比較」の解説は、「フィッシャー–イェーツのシャッフル」の解説の一部です。
「他のシャッフルアルゴリズムとの比較」を含む「フィッシャー–イェーツのシャッフル」の記事については、「フィッシャー–イェーツのシャッフル」の概要を参照ください。
- 他のシャッフルアルゴリズムとの比較のページへのリンク
