積集合
積集合、あるいは共通部分、交わりは、二つの集合に共通する元の集合である。
リスト
Data.Listにはintersection関数があるが、遅い。
Set
Data.Set.intersection :: Ord a => Set a -> Set a -> Set a
IntSet
Map
二つのマップの両方にある要素を見つけるにはintersectionを使う。
code: (haskell)
Map.intersection xs ys
Elias-Fano encoding
Elias fano encodingは広義の単調増加する自然数列を圧縮する簡潔データ構造の近縁種だ。以下の二つの操作がΟ(log log N)で実装できることを特徴とする。 * index :: EliasFano -> Int -> Word : 任意の場所の値を取り出す
* lookupGT :: EliasFano -> Word -> Int: 与えられた値以上の最小の要素を探し、インデックスを返す
互い違いにlookupGTを呼び出すことによってΟ(N log log N)で積集合を求められるが、よっぽど大きな列でもない限りIntSetのほうが速い。高いメモリ効率を活かせる状況でのおまけと考えるべきだろう。