BloomFilter - sileのブログ
オンラインで読める『Real World Haskell』という本の目次を眺めていたら、BloomFilterという言葉を発見。 どうやらデータ構造の一種らしいが、聞いたことがなかったので調べてみた(Wikipediaで)。 結果、セット(集合)を表すためのデータ構造だということが分かった。 偽陽性*1はあるが、メモリ使用量が凄く少なくて済むのが特徴で、例えば-目安として、だが- 要素数が100万のセットなら1MB程度のメモリで表現できるようだ。ちなみに、集合中の要素の列挙や削除といった操作は出来ない 実装としては、衝突を考慮しない and 要素を格納しないハッシュ、といった感じ。 BloomFilterの初期化、要素追加、帰属判定を行うcommon lispのプログラムを書いてみたので、下に載せる。 ;; 構造体: ビット配列と要素の追加・判定に用いるハッシュ関数のリストを持つ (def
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Priority Queues in CL
GitHub - ruricolist/cl-bloom: Simple Bloom filters in Common Lisp with efficient hashing.
Lemonodor: Bloom Filters
