Mo's Algorithm について
はじめに
この記事は Mo's Algorithm について整理するための自分用メモです.
ポエム
Mo's Algorithm とは, 二次元グリッドにおける与えられた点の集合を上下左右方向への移動だけで巡回するときのより効率の良い順番を見つけるためのアルゴリズムといえるのでは.
1次元
自明だけど一応.
一次元座標 (x_i) (0 ≤ x_i < X) (0 ≤ i < Q) なる distinct な点集合を巡回する方法を考える.
やり方
当然 x 座標が小さいものから順に行けばよい.
計算量
x 軸移動 ： O(X)
よって全体の計算量は O(X) である
2次元
普通の Mo と大体同じ.
二次元座標 (x_i, y_i) (0 ≤ x_i < X, 0 ≤ y_i < Y) (0 ≤ i < Q) なる distinct な点集合を巡回する方法を考える.
やり方
まず, b_x を使って x 座標によって以下のようにバケット毎に分ける.
バケット数は ceil(X / bx) 個.
各バケット毎に独立で, それぞれの点を (y_i) とみなして 1 次元の方法を適用する.
計算量
バケット内の点から点への移動は以下のようになる.
x 軸移動 ： O(b_x)
y 軸移動 ： O(Y)
バケット全体では以下のようになる. ただし, c_j はそのバケット内の点の数.
x 軸移動 ： O(c_j * b_x)
y 軸移動 ： O(Y)
バケット間での移動の合計は
x 軸移動 ： O(X)
y 軸移動 ： O(Y * (X / b_x)) = O(X * Y / b_x)
よって全体で以下.
x 軸移動 ： O( (Σc_j) * b_x + X) = O(Q * b_x + X)
y 軸移動 ： O(X * Y / b_x + Y)
合計 ： O(Q * b_x + X * Y / b_x + X + Y)
このとき, 合計を最小にするバケットサイズは b_x = (XY/Q)^(1/2) である.
ちなみに, このバケットサイズが 1 より小さいことはない. （そうなる条件は Q > XY だが, これは各点が distinct であることに矛盾するため）
合計：O( (XYQ)^(1/2) + X + Y )
b_x が X を超えてしまうことを考慮していないが, そのような状況では Y >> XQ の条件を満たし, y座標でソートすることになるので, O(XQ + Y) = O(Y) となり問題ない.
また実際に, Mo's Algorithm を使う多くの場合は X, Y が同じか近い値である*1ので, 最終的に全体の計算量は O( (XYQ)^(1/2) ) となる.
3次元
時空間 Mo と大体同じ.
三次元座標 (x_i, y_i, z_i) (0 ≤ x_i < X, 0 ≤ y_i < Y, 0 ≤ z_i < Z) (0 ≤ i < Q) なる distinct な点集合を巡回する方法を考える.
やり方
二次元と同様にまず, b_x を使って x 座標でバケット毎に分ける.
バケット数は ceil(X / b_x) (= B とする) 個.
そして, 点を (y_i, z_i) とみなして 2 次元の方法をバケットごとに独立で適用する.
計算量
各バケット内の点から点への移動の合計は以下のようになる. ただし, c_j はそのバケット内の点の数.
x 軸移動 ： O(b_x * c_j)
y 軸移動 ： O( (YZ * c_j)^(1/2) )
z 軸移動 ： O( (YZ * c_j)^(1/2) )
バケット同士の間の移動の合計は以下.
x 軸移動 ： O(X)
y 軸移動 ： O(YB)
z 軸移動 ： O(ZB)
全体は以下.
x 軸移動 ： O( (Σc_j) * b_x) = O(Q * b_x + X)
y 軸移動 ： O( (YZ)^(1/2) * ( Σc_j^(1/2) ) + YB ) = O( (YZ)^(1/2) * (QB)^(1/2) + YB ) *2 = O( (XYZQ)^(1/2) / b_x^(1/2) + XY / b_x )
z 軸方向 ： O( hoge + ZB ) = O( hoge + XZ / b_x ) (hogeは y 軸方向の第一項と同じ)
合計 ： O(Q * b_x + (XYZQ)^(1/2) / b_x^(1/2) + XY / b_x + XZ / b_x + X)
細かい議論は省略するが X, Y, Z がある程度近い値*3のとき, 後ろの三項がボトルネックになることはない.
そのとき, 合計を最小にするバケットサイズは b_x = (XYZ/Q)^(1/3) である.
よって, 時空間 Mo を使う大抵の場合において全体の計算量 O( (XYZ)^(1/3) * Q^(2/3)) になる.
n 次元
あんまり実用性なさそうだけど一応.
煩雑になるので, 各軸での最大値を統一する.
n 次元座標 (x_0_i, x_1_i, ... , x_(n - 1)_i ) (0 ≤ x_j_i < X (0 ≤ j < n) ) (0 ≤ i < Q) なる distinct な点集合を巡回する方法を考える.
ただし, n ≧ 2 とする
計算量
全体で O(X * Q^( (n-1)/ n) ) になることを帰納法で示す.
n-1 次元での計算量が O(X * Q^( (n-2) / (n-1) ) ) と仮定する.
すると, 各バケット内での点から点への移動の合計は
x_0 軸移動 ： O(B * c_j)
その他の各軸移動 ： O(X * c_j^( (n-2) / (n-1) ) )
バケット間の移動の合計は
x_0 軸移動 ： O(X)
その他の各軸移動 ： O(X * C)
よって全体は
x_0 軸移動 ： O(QB + X^2 / B + X)
その他の各軸移動 ： O(X * (Σc_j^( (n-2) / (n-1) ) ) + X * C) = O(X * (Q^( (n-2) / (n-1) ) * C^(1 / (n-1) ) ) + X * C)*4 = O(X^(n / (n-1) ) * Q^( (n-2) / (n-1) ) / B^(1 / (n-1) ) + X^2 / B)
合計 ： O(QB + X^(n / (n-1) ) * Q^( (n-2) / (n-1) ) / B^(1 / (n-1) ) + X^2 / B + X) = O(QB + X^(n / (n-1) ) * Q^( (n-2) / (n-1) ) / B^(1 / (n-1) ) )
この合計を最小にするバケットサイズは B = X / Q^(1/n) である.
そして, このとき全体の計算量は O(X * Q^( (n-1) / n) ) となり, 帰納法が成立する.
追記
この計算量の解析はガバガバで, nが定数とみなせないサイズになると定数項が爆発するので注意.
まとめ
移動の各方向の計算量が対称でない場合は（ある軸だけ log 付いたりとか）より良くできる場合があるので, これを眺めながら良い感じバケットサイズを計算したりとかに使えるかも（？）
