乱択アルゴリズム — サイコロを振ると速くなる不思議

なぜ乱数を混ぜると速くなるのか。ランダムピボットのクイックソート、片側誤りのブルームフィルタ、モンテカルロとラスベガスの違いを前提知識ゼロから積み上げ、乱数の扱いを間違えたときに起きる事故まで見ます。

比喩: 毎回グーを出す人には勝てる

じゃんけんで毎回グーしか出さない人には、必ず勝てます。相手の手が決まっているなら、それを潰す一手も決まっているからです。

アルゴリズムも同じ立場に立たされます。「配列の先頭をピボット（基準）にして2つに割る」と決め打ちしたクイックソートは、すでに昇順に並んだ配列を渡された瞬間に最悪になります。割るたびに片側が空になるので、分割が $n$ 回起き、各回に $n$ 個近い比較が要る。合計 $O(n^2)$ です。しかも「すでに並んでいる」は、ORDER BY で取った行、日付順のログ、前回のソート結果と、現実で最もよく現れる形です。運が悪いのではなく、弱点が入力の側に固定して置かれている。

乱択アルゴリズム（randomized algorithm）は、ここでサイコロを振ります。ピボットを毎回ランダムに選ぶ。すると同じ入力を何度渡されても、同じ遅さは再現しません。速さを決めるのが入力ではなく、こちらが振った目になるからです。

直感: 最悪ケースの引っ越し

これが乱択の中心にある、たった一つのアイデアです。最悪ケースを、入力の空間から乱数の空間へ引っ越しさせる。

計算量には2つの言い方がありました（計算量を1から理解する）。どんな入力でもこれ以下という最悪計算量と、入力がある分布から来ると仮定したときの平均計算量です。後者の弱点は「入力がランダムに来る」という仮定そのもの。現実のデータは並び済み・逆順・同値の連続と強く偏っていますし、悪意ある相手ならわざと最悪の入力を送れます。

乱択アルゴリズムが与えるのは3つ目の保証、期待計算量です。

つまり「どんなデータを渡されても、かかる時間の平均はこの上限を超えない」ということです。

$T(x)$ は入力 $x$ に対する実行時間、$\mathbb{E}$ は平均、$n$ は入力サイズです。読み下すと「どんな入力に対しても、実行時間の平均は $f(n)$ 以下」。平均を取っている相手が入力ではなくアルゴリズム自身が振った乱数だ、というのが決定的な違いです。入力の分布を何も仮定していないので、相手が誰でも崩れません。攻撃者は私のコードを読めますが、私が今日どの目を出すかは読めない。この一文は、後半で出てくるハッシュ表への攻撃と、その対策にそのままつながります。

クイックソート: ランダムなピボットが効く理由

変更点は一行です。ピボットを先頭から取るのをやめ、区間の中から一様ランダムに選ぶ。

なぜ速くなるかは、比較の回数を数えると見えます。ソート後に $i$ 番目と $j$ 番目に来る2要素が直接比較されるのは、片方がピボットになったときだけ。そして $i$ と $j$ の間にある $j-i+1$ 個のうちどちらでもない誰かが先に選ばれた瞬間、2つは別の区間に分かれて二度と出会いません。つまり比較が起きるのは、その $j-i+1$ 個で最初に選ばれたのが $i$ か $j$ のときに限られ、確率は $2/(j-i+1)$。あとは全ペアを足すだけです。

つまり「すべての要素の組について、その2つが出会う確率を足し合わせると、比較の回数は要素数と桁数の積くらいに収まる」ということです。

$C_n$ は比較の総回数、$H_n = 1 + \frac{1}{2} + \dots + \frac{1}{n}$ は調和数（足すほどゆっくり増え $\ln n$ に近づく量）です。言い換えると、比較ソートの理論下限 $n\log_2 n$ のおよそ1.39倍、4割増しで済むということ。決め打ちピボットの最悪 $n^2/2$ とは、$n$ が伸びるほど桁で離れていきます。

最悪ケースが消えたわけではありません。毎回いちばん小さい要素を引けば $O(n^2)$ です。ただしその確率は、要素が100個でも宝くじの1等をはるかに下回る。起きうるが、狙って起こさせる方法が誰にもない。 これが「乱数の空間へ引っ越した」ことの実際の意味です。

ちなみに、同じ $O(n\log n)$ ならマージソートでもよさそうに見えます。それでも実務でクイックソートが好まれるのは、追加の配列を持たずその場で並べ替えられることと、連続したメモリを前から順に舐める動きがキャッシュに乗りやすいことの2点です。オーダーが同じでも実測が桁で変わる — 乱択が選ばれる背景には、この「定数倍の強さ」もあります。

ここから先は、この発想がクイックソートの外でどう化けるのかを見ます。ときどき間違う代わりに軽くなる流儀、答えは正しいが時間が読めない流儀、その代表格であるブルームフィルタ、次元の呪いを乱択だけがすり抜ける理由、そして乱数を扱い損ねたときの事故まで。