🤾

ソートの計算量はどこから生じるのか？

2024/05/29に公開

ソート

idea

事の発端

スリープソートはなぜ $O(1)$ なのか

このツイートに対して私が提案したのは光ファイバの遅延を利用して $O(1)$ でソートするアルゴリズムだったが、これはスリープソートという既出のアルゴリズムだった。

スリープソートは配列の各要素の値を読み取って、その値の大きさに応じた時間スリープさせてから値を返すようにサブルーチンを生成し、各サブルーチンから値が返った順番に読み取ればソート済みになっているというアルゴリズムである。

スリープソートは完全な並列化が可能であるため時間計算量は $O(1)$ で動作する。

バカげたアルゴリズムに聞こえるかもしれないが、時間計算量が $O(1)$ というのは魅力的だ。

なぜスリープソートは完全な並列化が可能なのか？

その本質を知ることができればソートの改良に活かすことができるかもしれないではないか。

ということでお風呂の中でちょっと考えたのだが、どうやらソートの計算量とは以下のようにして生じるものであるらしい。

ソートにおいて完全な並列化が可能であるとは、各要素が自分自身を空間上のどこに配置すべきか知るために、他の要素の情報を必要としないことを意味する。
配置先の空間が十分な大きさを持つならば、各要素が自分自身を空間上のどこに配置すべきか知るために、他の要素の情報を必要としない。
配置先の空間が十分な大きさを持たない場合、各要素は他の要素との相対的な位置関係を知る必要が生じる。
ソートの計算量とは、各要素が自分自身を空間上のどこに配置すべきか知るために、知らなければならない他の要素がどれだけあるかを表している。

順を追って説明しよう。

1. ソートにおいて完全な並列化が可能であるとは、各要素が自分自身を空間上のどこに配置すべきか知るために、他の要素の情報を必要としないことを意味する

ソートを並列化するということは、ソートしたい配列をいくつかの小さな配列に分割して問題を解く^[1]ことを意味する。すなわち並列度を上げるということはひとつのクラスタから参照できる要素の数が減って、他の要素の情報を知ることができなくなることを意味するのである。

下の図で言えば、クラスタ１の中でソートを行うときにクラスタ２の中にある要素の情報を用いることはできないし、反対にクラスタ２の中でソートを行うときにクラスタ１の中にある要素の情報を用いることもできない。

クイックソートは並列度を徐々に上げることができるようにうまくクラスタ分けしていくアルゴリズムであると言え、逆にマージソートは並列度が高い状態から徐々に大きなクラスタに統合していくようなアルゴリズムであると言える。バケットソートはクラスタ数を一定として設定しておくアルゴリズムである。

完全な並列化とは、配列の要素数に等しい数の計算機を用意して、ひとつのクラスタにひとつの要素が割り当てられている状態である。

この状態で動作するソートアルゴリズムがあるとすれば、各クラスタは自分が受け取った要素のみを見て、それをソート後の空間のどこに配置すべきかを判断しなければならない。したがってソートにおいて完全な並列化が可能であるとは、各要素が自分自身を空間上のどこに配置すべきか知るために、他の要素の情報を必要としないことを意味する。

2. 配置先の空間が十分な大きさを持つならば、各要素が自分自身を空間上のどこに配置すべきか知るために、他の要素の情報を必要としない

とはいえ、各要素が他の要素の情報を知らずして自分自身をどこに配置すべきか知る方法なんてあるのだろうか？

それがあるのだ。配置先の空間が連続体濃度で無限の大きさを持つならば。

やり方はまったく簡単で、配置先の空間における原点と単位長さをすべてのクラスタに共有しておき、単位長さに自分が与えられた要素の値をかけて空間上にプロットすればよい。

スリープソートは配置先の空間に時間というほぼ連続体濃度で無限の大きさを持つ空間を割り当てることでこれを実現し、完全な並列化により時間計算量 $O(1)$ を達成したアルゴリズムであると言える。

メモリのアドレス空間が連続体濃度で無限である（かつ要素が配置された部分だけを瞬時に読み取れる）ならばまったく同じことができる。

実際のところ配置先の空間に連続体濃度の大きさが必要になるのは並び替えたい値の候補の集合が連続体濃度になっているときだけで、たとえば 64bit の情報量で表現される値を並び替えたいのであれば、配置先の空間の大きさとしては $2^{64}$ 個の要素があれば足りる。

3. 配置先の空間が十分な大きさを持たない場合、各要素は他の要素との相対的な位置関係を知る必要が生じる

現実的にメモリは $2^{64}$ bit ≒ 2.3EB^[2]よりもずっと小さな大きさしか持たない。このとき初めて生じる問題が値の異なる要素の配置先のバッティングである。いわゆる鳩の巣原理だ。

配置先の空間が十分な大きさを持っている場合は、各要素は自分の値に固有な配置先を定義することができたので、他の要素の値を知る必要がなかった。しかしいま、配置先の空間にはひとつの値にひとつの配置先を割り当てる余裕はなく、鳩の巣原理によって必ず配置先が被ってしまう値の異なる要素が出てくる。それらは後で比較してやらないと最終的なソート結果は定まらない。

そして上図はバケットソートのアルゴリズムそのものである。どのソートアルゴリズムでも要素間の比較が入ってくる理由は本質的に同じで、限られた椅子のどこに座るのかを決めるために「おまえらあっちに詰めろ」とか「おまえがそっちにズレろ」と融通し合う必要が生じるからである。

4. ソートの計算量とは、各要素が自分自身を空間上のどこに配置すべきか知るために、知らなければならない他の要素がどれだけあるかを表している

それで最終的には、各要素が他のどの要素とコミュニケーション（すなわち比較処理）を取れば、全体の中で自分が相対的にどこに配置されるべきかを確定できるのかが問題として残るというわけである。

ソートのアルゴリズムの時間計算量を構成する要素は大きく分けて

逐次的に各要素を走査するための計算量
着目している要素と他の要素を比較するための計算量

の２つの掛け算になっていて、たとえばマージソートの $O(n \log n)$ は、 $n$ 個の要素を走査する必要があって、その個々の要素の位置を確定するためには１つの要素あたり平均して $\log n$ 個くらいの要素と比較してみればよい、ということになる。

並列度合を高めると各要素を走査するための計算量のほうを減らせるというわけで、マージソートをもし完全に並列化できたとしたら $O(\log n)$ くらいはまでは計算量が下がるかもしれないと期待できることになる^[3]。

スリープソートは他の要素とまったく比較する必要がないから、全体を逐次的に走査すれば $O(n)$ で、それを $n$ 台の計算機で並列化できてしまうので $O(1)$ まで時間計算量を下げられるというわけだ。

したがってソートの計算量を減らすならば、他の要素を参照しなくても自分の位置を概算できるようなハッシュ関数を作るしかないと想像できる^[4]。

実際に２要素の比較に基づくアルゴリズムの時間計算量は $\Omega(n \log n)$ が下界となることが知られている。

おしまい

以上、配置先に十分な広さがあるならばソートの計算量ってめちゃくちゃ減らせるんだな、メモリの容量が小さいから生じる問題なんだな、って気づけた日だった。

脚注

分割統治法という。 ↩︎
エクサバイト。キロ、メガ、ギガ、テラ、ペタの次がエクサ。 ↩︎
実際は最後に $n/2$ 個どうしの配列をマージするので、そこが律速となって時間計算量は $O(n)$ までしか下がらない。 ↩︎
そして仮にそのようなアルゴリズムを作っても、入力される配列の各要素が一様ランダムに分布していないと性能は出ないだろう。 ↩︎