最近、とあるカードゲームの対戦をコンピューター上で再現できるツールが公開された。
使ってみると……やけに最初の手札に同じカードがたくさん来て、偏りが大きい気がした。
そりゃあ確率的にあり得なくはないけど……これちゃんとシャッフルしてる……？
というわけで見てみると、シャッフルとしてランダムな結果を返す比較回数を用いたソートが用いられていた。
なんだか強力なヤバそうな匂いがするぞ……
というわけで、シャッフルとしてよく書かれそうな気がするアルゴリズムをいくつか比較してみた。
今回比較するアルゴリズム
今回のアルゴリズムは、
- 第1引数に、シャッフルを行う配列
- 第2引数に、0以上指定した整数未満のランダムな整数を返す関数
をとる関数で表す。
第2引数に渡す関数としては、まずは以下の単純な実装を用いる。
function rngMath(max) {
return Math.floor(Math.random() * max);
}
ランダム選択
「配列のまだ決めていない部分の中からランダムな要素を選び、次に決める要素と交換する」操作を順に行っていく。
$O(n)$ と効率が良く、ランダム性も高そうだ。
function randomSelect(array, rng) {
if (array.length <= 0) return;
for (let i = 0; i < array.length; i++) {
const pos = rng(array.length - i);
const temp = array[i];
array[i] = array[i + pos];
array[i + pos] = temp;
}
}
ランダム交換 (要素数回)
「配列の中のランダムな2要素を選び、交換する」操作を適当な回数繰り返す。
とりあえず、「適当な回数」として配列の要素数を採用した。
$O(n)$ なので、効率はいいはず。
function randomSwapLinear(array, rng) {
if (array.length <= 1) return;
for (let i = 0; i < array.length; i++) {
const pos1 = rng(array.length);
const pos2raw = rng(array.length - 1);
const pos2 = pos2raw + (pos2raw >= pos1 ? 1 : 0);
const temp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = temp;
}
}
ランダム交換 (要素数の2乗回)
上の方法で、「適当な回数」を配列の要素数の2乗に増やした。
当然 $O(n^2)$ となり、効率が悪い。
これで結果の質も悪ければ最悪だなあ……
function randomSwapSquare(array, rng) {
if (array.length <= 1) return;
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
const pos1 = rng(array.length);
const pos2raw = rng(array.length - 1);
const pos2 = pos2raw + (pos2raw >= pos1 ? 1 : 0);
const temp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = temp;
}
}
}
ランダム比較ソート
ソートを行う関数の比較関数として、結果をランダムに返す関数を指定する。
冒頭で紹介したツールでは、これに近い方法が使用されていた。
効率はソートの効率と同じで、適切な実装であれば悪くない……ことを期待したい。
しかし、比較関数に求められる反射律・対称律・推移律を満たさず、同じ要素ペアを比較した際の結果が同じになることすら期待できないため、ソートの動作が保証できないだろう。
function randomCompareSort(array, rng) {
array.sort(() => rng(2) * 2 - 1);
}
ランダムスコアソート
各要素に適当なスコアを割り当て、そのスコアでソートする。
当然、ソートの比較関数は普通のものを用いる。
効率はソートの効率と同じになるだろう。
SQLでシャッフルを行う際に用いたくなる方法か。
function randomScoreSort(array, rng) {
const arrayToSort = array.map((element) => ({ element, score: rng(0x100000000) }));
arrayToSort.sort((a, b) => a.score - b.score);
arrayToSort.forEach((elem, idx) => array[idx] = elem.element);
}
比較結果
作成したツール シャッフルテスト (GitHub リポジトリ) を用いることで、各アルゴリズムの実行後にそれぞれの要素が行った位置の分布と、計算にかかった時間を求めることができる。
また、位置の分布をヒートマップで表すこともできる。
今回は、Firefox 149.0.2 を用い、要素数 64、試行回数 131072 で実行した。
位置の分布と実行時間
各アルゴリズムを 5 回ずつ実行し、計算時間、およびある要素がある位置に行った回数の最大・最小・標準偏差の平均をとった。
結果は以下のようになった。
| アルゴリズム | 最大 | 最小 | 標準偏差 | 計算時間 (秒) |
|---|---|---|---|---|
| ランダム選択 | 2225 | 1895 | 45.216 | 0.076 |
| ランダム交換 (要素数回) | 18679 | 1641 | 2061.197 | 0.161 |
| ランダム交換 (要素数の2乗回) | 2217 | 1876 | 44.866 | 5.354 |
| ランダム比較ソート | 20748 | 52 | 1832.936 | 0.395 |
| ランダムスコアソート | 2218 | 1887 | 45.157 | 0.582 |
「ランダム交換 (要素数回)」は、計算量は「ランダム選択」と同じ $O(n)$ のはずであるが、1ループで2回乱数生成を行うためか、「ランダム選択」の2倍程度の計算時間となった。
「ランダム交換 (要素数の2乗回)」は、$O(n^2)$ の計算量となり、やはりこの中ではぶっちぎりで長時間かかる。
「ランダム比較ソート」「ランダムスコアソート」は、「ランダム交換 (要素数回)」よりは遅いが、「ランダム交換 (要素数の2乗回)」よりは速いという結果になった。
ソート結果を詰め直す分か、「ランダムスコアソート」のほうが「ランダム比較ソート」より遅いようである。
要素の行き先の分布は、「ランダム選択」「ランダム交換 (要素数の2乗回)」「ランダムスコアソート」では (きちんとした検定は行っていないが) だいたい似た感じになり、「ランダム交換 (要素数回)」「ランダム比較ソート」ではそれらと比べて大きな分布の偏りがみられた。
「ランダム交換 (要素数回)」では、要素が行った回数の最大は大きな値となっているが、最小は比較的小さくなっていない。
一方、「ランダム比較ソート」では、最大はかなり大きく、最小はかなり小さくなっており、かなり大きな偏りの存在が示唆されている。
ヒートマップ
各アルゴリズムをさらに 1 回実行し、要素が行った回数の分布のヒートマップを取得した。
これは、各結果における回数の最小～最大の範囲で、回数が少ないほど青、多いほど赤で示したものである。
| ランダム選択 | ランダム交換 (要素数の2乗回) | ランダムスコアソート |
|---|---|---|
 |
 |
 |
| ランダム交換 (要素数回) | ランダム比較ソート |
|---|---|
 |
 |
「ランダム選択」「ランダム交換 (要素数の2乗回)」「ランダムスコアソート」では目立った特徴は見られず、だいたい均等に分布していそうである。
「ランダム交換 (要素数回)」では、対角線のみが真っ赤、対角線以外が真っ青となっており、要素が動かない確率がかなり高いらしいことがわかる。
一方、「ランダム比較ソート」では、対角線以外にも明るい部分はあるものの、四角状の分布がみられ、ソートアルゴリズムに由来する偏りがありそうなことがうかがえる。
暗号学的乱数の使用
ランダムな整数を返す関数を以下のものに差し替え、同様に実行した。
function rngCrypto(max) {
const numDrop = 0x100000000 % max;
for (;;) {
const array = new Uint32Array(1);
crypto.getRandomValues(array);
if (array[0] < numDrop) continue;
return array[0] % max;
}
}
5 回実行した平均をとると、計算時間と要素の行き先の分布は以下のようになった。
| アルゴリズム | 最大 | 最小 | 標準偏差 | 計算時間 (秒) |
|---|---|---|---|---|
| ランダム選択 | 2213 | 1872 | 44.886 | 3.700 |
| ランダム交換 (要素数回) | 18675 | 1639 | 2061.748 | 7.234 |
| ランダム交換 (要素数の2乗回) | 2206 | 1879 | 44.572 | 452.833 |
| ランダム比較ソート | 20762 | 53 | 1832.555 | 10.753 |
| ランダムスコアソート | 2213 | 1883 | 45.158 | 4.157 |
分布にはほとんどあまり差がみられない一方、計算時間は大幅に長くなった。
Math.random() を使用したときと計算時間を比較すると、以下のようになった。
| アルゴリズム | Math.random() |
crypto.getRandomValues() |
倍率 |
|---|---|---|---|
| ランダム選択 | 0.076 | 3.700 | 48.684 |
| ランダム交換 (要素数回) | 0.161 | 7.234 | 44.932 |
| ランダム交換 (要素数の2乗回) | 5.354 | 452.833 | 84.578 |
| ランダム比較ソート | 0.395 | 10.753 | 27.223 |
| ランダムスコアソート | 0.582 | 4.157 | 7.143 |
上3個のアルゴリズムは、乱数で直接交換する位置を決めて交換するため、実行時間に占める乱数生成処理の割合が比較的大きく、その分乱数生成処理の重さが全体の重さに大きな影響を与えると考えられる。
一方、下2個のアルゴリズムは、ソートや要素の乗せ換えといった乱数生成以外の処理の割合が比較的大きいため、乱数生成処理の重さの影響が比較的少なくなったと推測できる。
結論
「ランダム選択」アルゴリズムを用いることで、効率良く配列のシャッフルを行うことができ、シャッフルによる要素の移動状況もほぼ均等になりそうだ。
「ランダム交換 (要素数の2乗回)」「ランダムスコアソート」アルゴリズムでも要素の移動状況はほぼ均等になるようだが、「ランダム選択」アルゴリズムよりも効率が悪く、「ランダム選択」アルゴリズムを用いることができる状況でわざわざこれらのアルゴリズムを採用する意味は無さそうだろう。
「ランダム交換 (要素数回)」「ランダム比較ソート」アルゴリズムは、要素の移動先がシャッフル前の位置の近くになる確率が高くなってしまい、シャッフルの質が悪い。
良い使い道があるとすれば、CTF など用にあえて欠陥を埋め込むことぐらいだろうか。
crypto.getRandomValues() を用いると、Math.random() を用いた場合と比べて、要素の移動状況はあまり変わらなかったが、計算時間が大幅に伸びた。
シミュレーションなどを大量に繰り返す場合は、効率の良い Math.random() を用いたほうがよいだろう。
人間の操作によって呼び出し、1 秒に 1 回未満など低頻度でしか使わないのであれば、より品質が良くなりそうな気がする crypto.getRandomValues() を用いてもよいだろう。
おまけ
Google Chrome におけるランダム比較ソート
Google Chrome 147.0.7727.102 で「ランダム比較ソート」を実行すると、以下のようなヒートマップが得られた。
また、移動先の分布と計算時間は以下のようになった。(5 回平均)
- 最大：5410
- 最小：292
- 標準偏差：356.186
- 計算時間：0.793 秒
Firefox で実行したときよりは分布の偏りが小さいものの、「ランダム選択」アルゴリズムよりは大きな偏りがあり、特に最初の要素は高確率で配列の先頭付近に移動する (積み込みが可能) ことが読み取れる。
また、このアルゴリズムは結果が処理系に依存し、(悪い意味で) 予測が難しそうだということもわかる。
先行研究
他にも「シャッフルを目的とした処理」が無いかと思い、「プログラミング 入門 シャッフル」でググってみたところ、以下の記事を見つけた。
そのシャッフル、本当にシャッフルですか？何気ない落とし穴にハマった話 - BASEプロダクトチームブログ
この記事で、以下のページが紹介されていた。
今回作成したツールに似ているが、ヒートマップの表示に特化しており、具体的な分布の数値や計算時間の取得は難しそうである。