NSSetの内部実装

NSSet の内部実装

ふと気になったので調べてみたところ、以下のリンクを見つけた。

どうやら実装としてはハッシュテーブルらしい。だから、要素の挿入、削除、検索が一定時間でできる。

なんでそんなことがわかるかというと、NSSet のC言語実装である CFSet が CFHashTable というハッシュテーブルを使って書かれているから。

実は CoreFoundation のソースコードは公開されていて、その一部である CFSet のソースコードも見ることができる。

CFSet のメソッドを見ていると、NSSet のどのメソッドと対応しているか、それとなくわかる。気になる実装を軽く眺めてみるだけでも楽しいかも。もしかしたら、CoreFoundation のクラスの内部でクラッシュした時に、参考になるかも(笑)

C++ で Bloom Filter を実装してみた

Bloom Filter を勉強する機会があったので、実装してみた。

概要

Bloom Filter 自体の説明はよそに譲るとして、ざっくり特徴を言うと、

  • 二分木やハッシュテーブル等のデータ構造と比べると、はるかにメモリ効率が良い
    • キーの値をメモリ上で格納する必要がない
    • 逆に言うと、キーの集合を復元できない
  • false positive(追加していないキーに対して true と返す誤り)による誤検出の可能性があるが、false negative(追加しているキーに対して、false と返す誤り)はない
    • false positive する確率は 1 – exp(- k * n / m)) * k の式から算出できる
      • パラメータ k: ハッシュ関数の個数、n: 追加する要素数, m: ビット列の長さ
      • 要素を追加するほど、false positive が起きやすい
        • n = 10 のとき 0.028, n = 100 のとき 0.254, n = 1000 のとき 0.947

Bloom Filter

コード

実行例

応用

Bloom Filter の応用をいくつか紹介。

まとめ

使いドコロが難しそうだけど、false positive が起こっても許容できる状況では威力を発揮しそうですね!

参考リンク