原稿・資料 ― ありえるえりあアスキー NETWORK MAGAZINE原稿 アスキー NETWORK MAGAZINE 2005年3月号(http://nmag.jp/modules/xfsection/article.php?articleid=3)の「いま改めて知っておきたいこれからのP2P」の原稿です。 Read More…
Bloom filterのシンプルな実装 - 西尾泰和のはてなダイアリー
Bloom filterは指定されたものがリストに含まれるならばTrue、含まれないならばFalseを返すようなデータ構造である。もちろん、単純にリストを保持するだけでもリストに含まれるかどうかの判定は可能だが、Bloom filterのメリットはオリジナルのリストを保存しておく必要がないという点にある。そのためメモリの消費量を格段に節約することができる。しかし、そのメモリ効率の代償として多少正確性が失われる。Bloom filterは指定されたものがリストにない場合でもたまにTrueを返すのだ。しかし、間違ってTrueを返す確率はあらかじめ計算することができるので、誤差が許容できる範囲であれば問題なく使うことができる。 下記はアルゴリズム勉強用のシンプルな実装である。 SIZE = 1987 def hashes(s): xs = [0, 0, 0] for c in s: o = or
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
