# Haskell の IntMap vs HashMap ABC344 の [E - Insert or Erase](https://atcoder.jp/contests/abc344/tasks/abc344_e) は、双方向リストを使って解くことができる。 公式の解法も、連想配列のデータ構造を使った双方向リストを実装することを想定している。 しかし Data.IntMap.Strict (以下 IntMap) を使って双方向リストを実装したところ TLE (Time Limit Exceeded つまり速度不足による時間切れ) してしまった。 後日、細かい実装を突き詰めることで TLE しないところまでもっていくことはできたが、それでもぎりぎりの印象を受ける。可読性を確保するためにちょっとした関数呼び出しを加えるだけで、すぐ TLE というような状況であった。 しかし、IntMap から Data.HashMap.Strict (以下 HashMap) に変更すると実行時間に余裕が出て、そこまで詰めなくても通った。 IntMap と HashMap の使い分けはこれまであまり考えてこなかったので、改めて考察する。 ## Map, IntMap, HashMap Haskell の辞書系のデータ構造で代表的なものは Map (Data.Map.Strict) , IntMap, HashMap の 3種類である。 特に Map と IntMap は containers パッケージに含まれているもので、事実上の標準と思ってよい。 HashMap は unordered-containers に含まれている。 - [Data.Map.Strict](https://hackage.haskell.org/package/containers-0.7/docs/Data-Map-Strict.html) - [Data.IntMap.Strict](https://hackage.haskell.org/package/containers-0.7/docs/Data-IntMap-Strict.html) - [Data.HashMap.Strict](https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict.html) 機能的な差異でいくと - Map ··· 順序付き。データはキーの順に順序付けされる。$O(\log n)$ でキーによる値の参照が可能。また $O (\log n)$ でキーの効率的な横断検索が可能 - IntMap ··· 順序付き、キーは Int 型のみ。同様に順序付けされる。$O(min(n, W))$ でキーによる値の参照が可能。また $O(min (n, W))$ でキーの効率的な横断検索が可能。なお $W$ はキーの整数のビット数 (つまり 32 or 64) - HashMap ··· 順序なし、キーは Hashable である必要。順序がない分、Map や IntMap のような横断検索の機能はない。キーによる値の参照は $O(\log n)$ となっている。 現時点の実装としてはドキュメントによると - Map ··· サイズ付きの平衡二分木 (size balanced binary trees) - IntMap ··· パトリシア木 - HashMap ··· Hash Array Mapped Tries ということらしい。 IntMap の参照コストがキーのビット数に依存しているのは、パトリシア木を使っているからである。 ざっくりした利用用途としては - 順序付きのものが使いたい、キーが整数で良いなら IntMap、そうでないなら Map を使う。IntMap はキーが整数に限定される分、速い - 順序が必要ないなら HashMap でもいい となる。Map のドキュメントにもそう書かれている。 あとは細かい点として Map はサイズ付きなので全体のサイズを $O(1)$ で取得できるが、他二つはそれには $O(n)$ かかる。 競技プログラミングではこれが使い分けのポイントになることもある。 いままでこの考え方に基づいて使い分けを行っていて、経験的にこれと違うことが起きるということはなかった。 また普通に使っていると IntMap はだいたいにおいて速い。過去 HashMap を積極的に使うことはなかった。 ## ABC344 E で起こったこと - Map では実装を頑張ってもワーストケースで TLE する - IntMap では実装を頑張らないと、ワーストケースで TLE する - HashMap だとやや雑な実装でも TLE しない となった。 「実装を頑張る」というのは Map をキーで参照する回数を最小限に減らすなどが挙げられる。 例えば何か値を更新したい場合に ```haskell let a = xs IM.! k xs' = IM.insert k (a + b) xs ``` ではなく ```haskell let xs' = IM.adjust (\a -> a + b) k xs ``` と、更新関数でアトミックに行う。これで参照回数を減らすことができる。 実際 IntMap を使って前者で実装していたところ TLE して通らず。これが原因で当該の問題の正解を逃してしまった。 `adjust` に変更したところ通った。 一方 HashMap を使う場合はここまで躍起にならなくても通る。 以下は実装を突き詰めた後の IntMap と HashMap での速度比較である。  ## ざっくり IntMap と HashMap の差 - IntMap は実装がパトリシア木になっているため、キーをもとにした値の探索コストが、整数のビットサイズに依存する。よって $O(min(n, W))$ となる - HashMap は、キーをもとにした値の探索コストは一様で、$O(\log n)$。つまりデータ件数にのみ依存する となる。 現時点でテストデータが公開されていないので憶測になるが、IntMap で時間のかかるワーストケースのテストは、IntMap が HashMap よりも相対的にコストが嵩む計算、つまりキーによる値の参照が多く実行されるテストになっていると思われる。結果、木の探索の定数倍処理の総計が嵩むのではないか。 IntMap の参照の計算量は $O(min(n, W))$ だが、これは件数 $n$ が少ない間は $O(n)$ となり、件数が整数のビットサイズである 64 を超えると $O(64)$ となるということだと理解している。一方、HashMap は $O(\log n)$ なので $10^5$ に対しても十数回の探索で済む。データ件数が大きくなるとここで差がつく。 なお、整数の分布によって IntMap のパトリシア木における探索コストが相対的に大きくなるようなケースもあるかもと考えたが、調べてみたところそのような、分布の偏りが原因で速度差がつくことはなさそうであった。(正確なところはわからず) 計算量的に両者に違いはあるものの、計算量だけで決まるものでもない。以下、もう少し深入り。 ## ベンチマーク [haskell-perf/dictionaries: Benchmarks for dictionary data structures: hash tables, maps, tries, etc.](https://github.com/haskell-perf/dictionaries) に Map, IntMap, HashMap のベンチマークが公開されているので改めてみてみた。 ![[スクリーンショット 2024-03-11 10.40.46.png]] こうしてみると、挿入は IntMap が常に速い。Map はやはり遅い。 IntMap に関して、データ件数が増えても挿入にかかるコストの相対的な性能劣化は見られない。 ![[スクリーンショット 2024-03-11 10.41.00.png]] 参照をみてみると、IntMap は件数の増大に応じて、参照速度が相対的に Map や HashMap よりも劣化する。ここまで遅くなるとは思っていなかった···! **対して HashMap はデータ件数が増えても相対的な速度劣化がなく、ある程度のサイズ以降は三つの中でもっとも速くなる** ことがわかる。 # わかったこと - Map は、汎用的で順序付きと機能が豊富。その分、だいたいにおいて他二つよりも遅い。ただしサイズ付きなのでレコード件数を $O(1)$ で取得できるメリットがある - IntMap は、基本的に速いがデータ件数が多くなると参照が遅くなることがある (※件数だけに依存しているのか、その他にも要因があるのかがわかっていないので「ことがある」としています)。ABC344 E は、おそらくこのケースに当たった - HashMap は、常に速いわけではないが、データ件数の増大に相対的に強い 「Map は遅い、IntMap は速い。だから整数でいいときは IntMap」という雑な理解から一歩進むことができた。 これまでは「HashMap を使っても思ったように速くなることはないし機能も豊富な IntMap でいいか」と判断していたが、それはエッジケースの考慮不足であった。 整数をキーとした小さな集合に対して辞書が使いたいというときは IntMap で良いが、今回の問題のようにデータ構造のベースなど、負荷のかかる律速な箇所に辞書を使う場合は HashMap の利用も検討したほうがよいだろう。 ## Set, IntSet, HashSet もほぼ同様の関係か Map, IntMap, HashMap の差異についてみてきた。 おそらく Set, IntSet, HashSet も同様の関係にあると思われる。 Set, IntSet はいずれも順序付き集合で、IntSet はパトリシア木で実装されている。HashSet は順序なし、というところも同じ。 ABC344 の [C - A+B+C](https://atcoder.jp/contests/abc344/tasks/abc344_c) では、事前に $O(10^6)$ の全探索をしてその結果を集合に入れて、続く $O(10^5)$ のクエリに答えていく... という方法で解ける。 この問題もやはりデータ件数が大きくなるにつれて HashSet が最も速く、次いで IntSet、そして Set が一番遅くなるという結果になった。 ## あとがき 当初 ABC344 E が微妙な差異で通らなかったときは、正直 Haskell の辞書データ構造の遅さを怨んだ。 計算量はあってるのに定数倍の実装で TLE する ··· というのはもっとも悔しいパターンのひとつである。 が、改めて調べてみると**単に自分の理解不足であったことは否めない。大いに反省している。** ![[スクリーンショット 2024-03-11 11.17.45.png|200]] ↑反省中の私 ## (参考) ABC344 E の HashMap による実装例 ```haskell main :: IO () main = do _ <- getInt as <- getInts q <- getInt qs <- replicateM q getInts let xs' = foldFor' (fromListLL as) qs $ \s query -> do case query of [1, x, y] -> insertAfterLL x y s [2, x] -> deleteLL x s _ -> undefined printList $ toListLL xs' {-- HashMap IntLinkedList --} type IntLinkedList = HM.HashMap Int (Int, Int) emptyLL :: IntLinkedList emptyLL = HM.fromList [(minBound, (minBound, maxBound)), (maxBound, (minBound, maxBound))] fromListLL :: Foldable t => t Int -> IntLinkedList fromListLL = foldl' (flip appendLL) emptyLL toListLL :: IntLinkedList -> [Int] toListLL xs = drop1 . takeWhile (/= maxBound) $ iterate (\k -> snd (xs HM.! k)) minBound insertAfterLL :: Int -> Int -> IntLinkedList -> IntLinkedList insertAfterLL i j xs = do let (_, right) = xs HM.! i HM.adjust (\(l, _) -> (l, j)) i $ HM.insert j (i, right) $ HM.adjust (\(_, r) -> (j, r)) right xs {-# INLINE insertAfterLL #-} insertBeforeLL :: Int -> Int -> IntLinkedList -> IntLinkedList insertBeforeLL i j xs = let (left, _) = xs HM.! i in insertAfterLL left j xs {-# INLINE insertBeforeLL #-} appendLL :: Int -> IntLinkedList -> IntLinkedList appendLL = insertBeforeLL maxBound {-# INLINE appendLL #-} prependLL :: Int -> IntLinkedList -> IntLinkedList prependLL = insertAfterLL minBound {-# INLINE prependLL #-} deleteLL :: Int -> IntLinkedList -> IntLinkedList deleteLL i xs = do let (left, right) = xs HM.! i HM.adjust (\(l, _) -> (l, right)) left $ HM.adjust (\(_, r) -> (left, r)) right xs {-# INLINE deleteLL #-} ```