[Library Checker] Associative Array

スポンサーリンク

問題概要

問題文 →

連想配列(Associative Array)の問題.

単純な処理なので使用頻度はかなり高いです.標準ライブラリを使う場合にパフォーマンスが良い実装方法を確認したり,適切なライブラリを整備する利点はかなり大きいと思います.

解法

標準ライブラリ等の利用

要素数を $N$ としたときに,map による検索は $O(\log N)$ 時間.unordered_map による検索は期待時間 $O(1)$ 時間であるという計算量の違いがあります(ただしその名の示す通り,unordered_map は順序を保持しないため,最小値・最大値や二分探索などは高速には行えません).

したがって本問の処理では map よりも unordered_map の方が計算量が優れています.ただし $N$ が小さい場合には本問のような処理でも map の方が高速に動作することもあります.

unordered_map は reserve を使って適切なメモリ確保をしておくだけで少し高速になります.

  • 解答例(std::unordered_map 使用,reserve あり,314ms)

ところでいずれにせよ,std::unordered_map はかなり遅く,policy hash table を使う方が良いのではないかという話があります(codeforces blog).std::unordered_map はなぜ遅いのかにもコメントがされていますが,私は詳しく分かっていません.policy based data structures については次の 日本語の文献(Joe さん) も確認しておくとよいと思います.

  • 解答例(__gnu_pbds::gp_hash_table 使用,234ms)

unordered_map より 4 倍くらい高速というような話も見ていたので,予想していたよりは速くないな….

ハッシュテーブルを実装する

実装量も少なめで,上述の手法よりも高速です.あまり余計な機能を持たせず実装した例を挙げておきます.

上記の実装は,ハッシュテーブルをオープンアドレス法(開番地法)で実装しています.オープンアドレス法はさらにいくつかの分類がありますが,この実装はそのうち線形探索法ということになります(LC 上位の提出でもほとんどが線形探索法であるように見えます).どのようなアルゴリズムであるかは実装を見ればかなり理解しやすいと思うので省略します.

ライブラリ化の際には,必要に応じて,テーブルが一定以上埋まってた場合の自動再構築,削除機能をつける,等の機能拡充をすることが考えられます.

オープンアドレス法について

英語版 wikipedia が詳しいです.

キー全体の集合を $S$ とし,テーブルサイズを $n$ とします.$|S|/n = a$ を負荷率といいます.

抽象化されたオープンアドレス法は次のようなものです.

  • キーに対して,無限列 $(i_0, i_1, i_2, \ldots)$ を定めるようなハッシュ関数を用意する.
  • $(i_0, i_1, i_2, \ldots)$ のうちはじめて未使用のインデックスにデータを置く.

$i_k$ に違うキーのデータが置かれていたという状況を衝突といいます.計算量解析が最も容易なのは,無限列が一様ランダムに定まる場合で,このとき新しいキーに対する衝突回数期待値は $(1-a)^{-1}$ であることが簡単に分かります(確率 $1-a$ で当たりが出るサイコロを当たるまで振るときの回数期待値).特に,事前に $1$ 未満の正実数を固定して,負荷率をその値以下になる状態を保つように実装すれば,衝突回数の期待値は $O(1)$ で,ハッシュテーブルのもろもろの操作の期待時間計算量が $O(1)$ ということになります.

ただし,一様ランダムな無限列をとるハッシュを作るのは非現実的なので,実用上は次のような選択肢が用いられるようです.

Linear Probing はこれらの方法の中では,探索時のキャッシュヒット率が高いというメリット,同じ負荷率に対して衝突回数の期待値が高くなりやすいというデメリットがあります.デメリットについては,一度衝突した場所ほどさらに衝突しやすく,大きな塊(クラスタ)が出来てしまいやすいというのが原因です.

ただし計算量オーダーが $O(1)$ であるという種の性質は大丈夫で,$h$ がキーごとに独立に一様ランダムに定められていて,負荷率が $a$ の場合,衝突回数の期待値が $\Theta((1-a)^{-2})$ であると解析できます(https://en.wikipedia.org/wiki/Linear_probing).

また,長さ $2^{n+1}$ の配列に $2^n$ 個のキーをセットするという実験を手元で行った結果,$n$ がある程度大きな値のときの衝突回数の平均値は $0.5$ に非常に近い値になりました.

ハッシュ関数について

キーの集合を $S$ として,目標は写像 $S\longrightarrow \{0,1,\ldots,n-1\}$ を一様ランダムに選択することで,計算量解析の類もその前提で行われることがほとんどだと思います.が,実際そんなに都合良く写像を得る方法はありません.

Rolling Hash の場合には,任意の入力に対して十分高い確率で意図通りの動作をするという証明が可能ですが(),HashMap の場合に「任意の入力(例えば 64bit 符号なし整数からなる任意の長さ $m$ の列)に対して十分高い確率で良い計算量が保証できる」ということが理論的に証明されたハッシュ関数が使われているかどうかは,私は知りません.

標準ライブラリ類を使う場合も,デフォルトで実装されている hash 関数がまあまあダメな場合が珍しくないようで,Python の set, dict や C++ の gp_hash_table も簡単に hack できるということが知られています(, ).

そこで,十分複雑だし hack の仕方が見つけられないなーと思われている写像で計算が高速なものがよく使われているということだと思います.詳しい議論は次のような記事やコメントを参照してください.

なお,ハッシュテーブルの実装において連鎖法(chaining)を使うと,理論保証のあるハッシュが存在するとの情報をいただきました:https://x.com/noshi91/status/1751542895205867703

LC 最速提出について

      2024/01/28 現在の最速:https://judge.yosupo.jp/submission/161872

      これを見ていきます.65ms の実行時間なのですが,コピペして提出しなおしたところ 89ms になってしまい,Rejudge しても 65ms は全然再現できません.この間にはテストケースの追加は行われていないはずなのですが,何かジャッジ環境の変化があるのか?

      → コンパイラのバージョンアップにより遅くなるという問題が見つかっているようです. https://x.com/yosupot/status/1751575503704863006?s=20

      私が上で解説したものと比べてアルゴリズムの大きな違いはなさそうです.最も独特な部分は __builtin_prefetch(GCC 拡張) を使用している部分でしょうか.少し先にどのようなクエリが来るのかを調べておき,そのクエリが来る少し前に配列の必要な部分を先読みしてキャッシュにのせておくというような意味のようです.__builtin_prefetch を外して提出しなおしたところ 97ms だったので,prefetch によって 1割程度の実行時間削減に成功しているということだと思います.

      タイトルとURLをコピーしました