えびちゃんの日記

えびちゃん（競プロ）の日記です。

期待 O(n) 時間の前処理で、クエリごと最悪 O(1) 時間で座標圧縮しようかな

ハッシュを使います。

å°Žå…¥

ある程度の仮定は欲しいです。 というのも、これが一般の型でできたら期待 $O(n)$ 時間でソートができることになるためです*1。

$a = (a_0, a_1, \dots, a_{n-1})$ が与えられ、$a_0 \lt a_1 \lt \dots \lt a_{n-1}$ であるとします。

あるいは、word size がいい感じなのを仮定して基数ソートの類で $\Theta(n)$ 時間でソートができる状況とします。

qiita.com

これに対して前処理をしておき、「$a_i$ の値のみが与えられるので、$i$ を返す」というクエリを最悪 $O(1)$ 時間で処理したいです。 $a$ に含まれない値は与えられません*2。

紹介

突然ですが、cuckoo hashing という手法があります。 競プロ界隈ではハッシュマップの類があまり有名でない気がします*3。

CS166.1226/6 などで、絵つきのスライドで紹介されています。

これは、要素の追加を期待 $O(1)$ 時間、削除と取得を最悪 $O(1)$ 時間でできるデータ構造です。 これに対して $a_i\mapsto i$ の対応づけを入れればおしまいです*4。あれれ。

それ以外の紹介

本当は以下で紹介する話を調べて記事にする予定だったのですが、cuckoo hashing で終わるじゃんと気づいてしまったので、ざっくり紹介だけになります。 簡潔データ構造寄りの文脈の話なので、cuckoo hashing より空間計算量には気を使っているのですが、それこそ競プロ界隈では興味が薄い人が多そうです*5。

座標圧縮に相当するハッシュ関数を monotone minimal perfect hash function と呼ぶ話とか、それを期待 $O(n)$ 時間で構成する文献の紹介とかを以下でします。

ハッシュについての話

キーとしてありうるものの集合 $\mathcal{X}$ とします。たとえば、整数全体の集合 $\Z$ だったり文字列の集合 $\Sigma^*$ だったりします。 そこから $n$ 個選んできたものを $\mathcal{K}$ とします ($\mathcal{K}\subseteq\mathcal{X}$, $|\mathcal{K}| = n$)。

それに対して、クエリ $x\in\mathcal{X}$ が与えられて $x\in\mathcal{K}$ を判定したい状況は頻出です (set)。 あるいは、各 $x\in\mathcal{K}$ に値 $y$ が関連づけられていて、与えられた $x\in\mathcal{K}$ に対してその $y$ を答えたい状況もあります (dict, map)。

以下、$[n]$ で $\{0, 1, \dots, n-1\}$ を意味するとします。

何らかの関数 $h: \mathcal{X}\to[m]$ ($m \ge n$) を用いて、長さ $m$ の配列 $A$ に $A[h(x)] = x$ ($x\in\mathcal{K}$) としておいてみます。 これによって、クエリの $x$ に対して $A[h(x)] = x$ なら $x\in\mathcal{K}$ と判定できそうです*6。 この $h$ をハッシュ関数と呼びます。

しかし、$h$ の選び方によっては、$x, y\in\mathcal{K}$ ($x\neq y$) に対して $h(x) = h(y)$ となってしまうことはありえます。 これを衝突と呼びます。 衝突すると誤って $y\notin\mathcal{K}$ と判定してしまったり、衝突を回避するために計算量を犠牲にすることになったり、もう散々です。

「定数時間を実現するためにハッシュを導入したのに、最悪ケースでは線形時間とかになるらしい。は〜ばかばかしい 😩」となる競プロ er は多そうです。わかるわかる。

以下では衝突のことは気にしないので、衝突が起きた際の処理 (open hashing, closed hashing) とか衝突が起こる確率とかの話はしません。

+perfect

衝突しないハッシュ関数は perfect hash function と呼ばれています。 すなわち、$x, y\in\mathcal{K}$ ($x\neq y$) に対して $h(x) \neq h(y)$ となる $h$ です*7。

$\mathcal{K}$ が静的*8であれば perfect hash function を構成することができます。 また、dict のクエリにおいては、$x\in\mathcal{K}$ は保証されていて、対応する値を返せばよい問題設定であるケースも多いです。 すなわち、$h:\mathcal{K}\to[m]$ を構成すればよいです。

そうした状況では、配列 $A$ のための $\log(\binom{|X|}{n})$ bits が必要なくなり、$2.46n + o(n)$ bits と期待 $O(n)$ 時間で構成する手法があるらしいです。

+minimal

さらに、perfect hash function のうちで $m = n$ とできるもの、すなわち $h: \mathcal{K}\to[n]$ ($x\neq y \implies h(x) \neq h(y)$) を minimal perfect hash function といいます。

これもなんやかんやして $2.46n + o(n)$ bits にできるらしいです。

+monotone

キーの集合を整数 $\mathcal{X} = [u]$ とします。 このとき、minimal perfect hash function が $x\lt y \implies h(x)\lt h(y)$ を満たすとき、monotone minimal perfect hash function といいます*9。

要するに、いわゆる座標圧縮は monotone minimal perfect hash function に相当していますね。 競プロ界隈でそういう呼び方をしている人はほぼいなさそうです。

また、整数の大小関係だけではなく、与えられた任意の順序を保存できるハッシュ関数 ($x\prec y \implies h(x)\lt h(y)$) は order-preserving と呼んで区別する流派もあるようです。

これは $O(n\log(\log(u)))$ bits と期待 $O(n)$ 時間でできるみたいです。クエリを $O(\log(\log(u)))$ 時間にしてよいなら $O(n\log(\log(\log(u))))$ bits に落とす手法もあるとかなんとか。

文献

この辺の話は Navarro, Gonzalo. Compact data structures: A practical approach. Cambridge University Press, 2016. の 4.5.3 Dictionaries, Sets, and Hashing に載っています。結構お高い。フォロヮからお年玉をもらったので新年早々買ってしまいました*10。今月ちょっとピンチです。

以下も読んでみると面白いかも。えびちゃんはまだです。

  • Belazzougui, Djamal, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. “Theory and practice of monotone minimal perfect hashing.” Journal of Experimental Algorithmics (JEA) 16 (2008): 3-1.
  • Belazzougui, Djamal, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. "Monotone minimal perfect hashing: searching a sorted table with $O(1)$ accesses." In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pp. 785–794. Society for Industrial and Applied Mathematics, 2009.

実測

一応してみました。

あーあって感じ。もっとチューニングをがんばればいい感じになるのかもしれません。

おきもち

ハッシュ系とかのデータ構造はあんまり流行らないのかなぁという気がします。 ヒュだとハッシュを使う人もいるのかなあ。えびちゃんはヒュに興味が持てないのでわかりません。

競プロで出てくるものの大半は整数（integer alphabet の文字列含む）なので、もっと整数系のデータ構造とかは流行ってもよさそうなのに、wavelet matrix とかも（最近はある程度知れ渡ってきた気もするものの）まだ知る人ぞ知る感がある気もします。

他にも log を落とす系のものもあんまり人気がなさそうです。仕方なさそう。

rsk0315.hatenablog.com

「log を落とす系は定数倍が悪いことが多いから...」と敬遠する割には、ビット並列で高速化するやつは「非本質な定数倍高速化だし...」と言う人もいたりしそうです。

rsk0315.hatenablog.com

rsk0315.hatenablog.com

人には人の興味なので、興味のありそうなアルゴリズムを調べてみるとよさそうです。

おわり

今年もよろしくお願いします。

*1:最悪と言ってはいないので不可能ではないかも？ わかりません。ただ簡単そうではない気がします。

*2:特に、与えられた $x$ 以下で最大の $a_i$ は？という形式の predecessor query は考えません。

*3:最悪計算量以外興味なし、期待計算量は FAKE のような風潮があったりなかったり。気持ちはわかる。

*4:$a_i$ に対して適当なハッシュ値を計算するのが定数時間でできるのは仮定します。

*5:競プロ界隈の興味のために記事を書いているわけでもないのですが。

*6:この $A$ のために $\log(\binom{|X|}{n}) = n\log(|X|/n) + O(n)$ bits 必要になります。

*7:$x\in\mathcal{X}, y\in\mathcal{X}\setminus\mathcal{K}$ について $h(x) = h(y)$ となっても問題ない気がするけどだめ？

*8:追加されたりしない状況。削除されるのはここでは問題なさそうだけど削除もされないとするのが普通そう。

*9:minimal じゃないものについては monotone perfect hash function とかになるかもしれません。ここではそういうのは考えません。

*10:@rsk0315_h4x さんありがとうございます。