「取り出し」アルゴリズム

ウィキペディア小見出し辞書

「取り出し」アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/27 02:05 UTC 版)

「フィッシャー–イェーツのシャッフル」の記事における「「取り出し」アルゴリズム」の解説

ダステンフェルドによって実装されたフィッシャー–イェーツのシャッフルは「内部でのシャッフル」である。これは、与えられた初期化済みの配列の要素を、その配列内でシャッフルする。シャッフルされた配列を別に生成することはない。配列が1本あればアルゴリズムを実行できるため、シャッフルされる配列のサイズが大きく、省メモリの要求がある場合は「内部でのシャッフル」の方が優れているだろう。 配列の初期化とシャッフルを併せて行う場合には、「取り出し」版のシャッフルを使うことで、メモリの使用量は2倍に増えるが、少しだけ計算速度を速めることができる。このやり方では、配列を元配列と生成配列の2本を用意し、配列の添字 i を増やしながら処理を行う。まず生成配列の i 番目に、配列の初めから i までの中でのランダムな場所 j 番目の値を移動し、その後に元配列の i 番目の値を、生成配列の j 番目に代入する。i と j は同じになることもあり、この場合、初期化されていない値を「(同じ場所に)移動する」ことが起こりうるが、その値はすぐに上書きされるため問題はない。生成配列を個別に初期化する必要はなく、交換処理も必要ない。「元配列」の値が、例えば0から n - 1 までの整数のような、シンプルに求められる場合であれば、「元配列」を変更することがないため、関数などに置き換えることもできる。計算速度の改善を計算量理論的に言えば、オーダーを変えず、係数を改善するだけであるので、計算方法を極限まで最適化する必要がある場合に意味を成すと言える。 要素数が n の配列 a を、配列 source をランダムにシャッフルしたコピーで初期化する (配列の添字はともに0から始まる): i を 0 から n - 1 まで増加させながら、以下を実行する j に 0 以上 i 以下のランダムな整数を代入する もしも j と i が等しくないならば a[i] に a[j] を代入する a[j] に source[i] を代入する 「取り出し」版のシャッフルが正しいことは以下のように帰納的に確認できる。完全にランダムな数値を生成できるとするならば、n! の異なった乱数を全て一つずつ取得することができる。そうであればすべて異なった順列を生成することができ、それらは完全に一通りずつの順列となる。「j と i が等しくない場合」の処理は、初期化されていない配列の要素に対するアクセスが許容されているプログラミング言語であれば省略することができ、比較してよりコストのかからないアルゴリズムを実行できる。 「取り出し」版のもう一つの利点は、元配列のデータから完全に独立したランダムな要素が取得できるのであれば、元配列の総要素数 n が未知の場合でも使用できる点である。下記の例では配列 a が空の状態でスタートし順番に追加されていく。配列 a の長さは見つけられた要素数をあらわす。 空の配列 a を、要素数が未知の配列 source をランダムにシャッフルしたコピーで初期化する: source に取得できる値が存在する間、下記を実行する j に 0 以上「a の要素数」以下のランダムな整数を代入する もしも j が「a の要素数」と同じならば a に source から取得した値を追加する そうでなければ a に a[j] を追加する a[j] に source から取得した値を代入する