Bloom Filter を作ってみた - 超ウィザード級ハッカーのたのしみBloom Filter を実装してみた。簡単な実装なので、速度や空間効率は悪いです。 Bloom Filter というのは、確率的データ構造の一つで、ある要素が集合に含まれるかどうかを試験するものです。空間効率が非常に良いのが利点で、偽陽性、つまり集合に含まれない要素もあるとしてしまう場合があるという欠点があります。偽陰性はありません。 以下が実装例です。 import hashlib import math class BloomFilter: def __init__(self, num_item, false_positive): assert 0 <= false_positive <= 1 # Optimal number of bit array size and hash function # https://en.wikipedia.org/wiki/Bloom_filt
