競プロ用ライブラリを作る Advent Calendar 2024の10日目です.
RollingHashって?
文字列みたいなデータに対して計算できる次の性質を持ったハッシュ関数$H$です.
- 文字列$S, T$のハッシュ値$H(S), H(T)$から, $S$と$T$を連結した文字列のハッシュ値$H(S + T)$も求められる
- ハッシュが衝突する ($S\ne T$なのに$H(S) = H(T)$になってしまうこと) 確率は無視できるくらいに小さい
仕組み
長さ$N$の$s_0, s_1, ..., s_{N-1}$という列のハッシュを
$\def\modp{\space\operatorname{mod}\space p}H(s) = s_0 + s_1 b + s_2 b^2 +\cdots+ s_N b^N \modp$
という感じに定義します. $p, b$ はパラメータです. $p$が素数で$2\le b\lt p$を満たす整数の組になっています.
長さ$M$の$t_0, t_1, ..., t_{M-1}$という列とくっつけた$s_0, s_1, ..., s_N, t_0, t_1, ..., t_N$という列のハッシュも考えてみると
H(s + t) = H(s) + H(t) b^N
と計算できます. ハッシュ値と一緒に$b^N$の値も持っておけば楽に計算できますね.
パラメータ設定
ここまでで出てきた$b$, $p$というパラメータの設定を考えます.
$p$はパフォーマンスの面から固定でやるのが望ましいです. $p = 2^{61}-1$でやるのが有名ですが, 人と同じことをしてもつまらないので$\mod 2^{64}-59$で行ってみましょう. これはu64で表現できる最大の素数です.
一方, $b$を固定してしまうと衝突させることが出来るので, こちらはランダムに設定する必要があります.
実行時に乱数を振ったりして決定するのが一般的な方法ですが, 何とかしてコンパイル時$b$を決めて実行時のオーバーヘッドを完全に0にしてみます.
予測が出来なければ良いので, ソースコード自体を基に$b$の値を生成してみましょう. Rustではinclude_bytes!(concat!(env!("CARGO_MANIFEST_DIR"), "/", file!()))みたいに書くと自身のソースコードが取得出来ます.
仮にランダムな$b$を決めて, その$b$でソースコードのRollingHashを計算, その値を$b$に設定し直す, というようにすればソースコードに依存した$b$が得られます.
事前に用意されるテストケースは提出されるソースコードを知らないため, 故意に衝突させるのは殆ど不可能です.
CodeforcesのHackみたいなシステムがあるとあまり意味が無くなってしまいますが, AtCoderで使うならこれで十分ですね.
高速化
更に高速化の工夫としてモンゴメリ乗算を導入します. Rustでは128bit/64bitの除算をあまり最適化してくれないので, こうやって速度改善を試みます.
モンゴメリ乗算とは, $0\le a, b\lt p$の範囲の整数$a, b$について, $f(a, b) = abX\modp$を高速に求めるアルゴリズムです.
何らかの定数$X$が掛けられてしまうので, $f(aX^{-1}, bX^{-1}) = abX^{-1}\modp$という風に全ての数に$X$の逆数がかかった状態で値を処理します.
ある数に$X$の逆数を掛けるには, $X^{-2}\modp$を予め計算しておいて$f(a,X^{-2})=aX^{-1}\modp$とすればいいですね.
RollingHashでは違う文字に違うハッシュ値が割り当てられればなんでも良いので, 文字の番号を最初から「$X$の逆数が掛かっている」と見做して逆数を掛けるのを端折っても問題ないです. 高速化のためにはそういう部分も削っておきましょう.
実装
やるだけです. ある程度の最適化はコンパイラが頑張ってくれると信じて程々にコンパイラが最適化しやすいように書いてあげましょう.
まとめ
いかがでしたか?
明日は有名データ構造を実装します.