136 lines
4.8 KiB
Python
136 lines
4.8 KiB
Python
"""Walk through OHBF: a hand example, a realistic filter, and a timing run."""
|
|
|
|
import hashlib
|
|
import os
|
|
import random
|
|
import sys
|
|
import time
|
|
|
|
sys.path.insert(0, os.path.join(os.path.dirname(__file__), ".."))
|
|
|
|
from ohbf import OneHashBloomFilter, bloom_parameters # noqa: E402
|
|
|
|
|
|
def section(title: str) -> None:
|
|
print(f"\n=== {title} ===")
|
|
|
|
|
|
def hand_example() -> None:
|
|
section("1. Hand example: sizes (5, 7, 11), injected hashes")
|
|
hashes = {b"apple": 100, b"pear": 37, b"plum": 58, b"grape": 345}
|
|
f = OneHashBloomFilter((5, 7, 11), hash_fn=hashes.__getitem__)
|
|
|
|
for name in ("apple", "pear", "plum", "grape"):
|
|
h = hashes[name.encode()]
|
|
mods = ", ".join(f"{h}%{s}={p}" for s, p in zip(f.sizes, f.positions(name)))
|
|
print(f" {name:<6} h={h:<4} -> {mods}")
|
|
|
|
f.add("apple")
|
|
f.add("pear")
|
|
print("\n after add(apple), add(pear); ^ marks the bits grape checks:")
|
|
grape = f.positions("grape")
|
|
for i, size in enumerate(f.sizes):
|
|
row = " ".join(str(b) for b in f.partition_bits(i))
|
|
mark = " ".join("^" if j == grape[i] else " " for j in range(size))
|
|
print(f" m{i + 1}={size:<3} {row}")
|
|
print(f" {mark}".rstrip())
|
|
|
|
for name in ("apple", "plum", "grape"):
|
|
verdict = name in f
|
|
note = {
|
|
"apple": "inserted",
|
|
"plum": "partition 1 bit 3 is 0",
|
|
"grape": "FALSE POSITIVE: never inserted, all 3 bits set by apple/pear",
|
|
}[name]
|
|
print(f" {name!r} in f -> {verdict} ({note})")
|
|
|
|
|
|
def realistic() -> None:
|
|
section("2. from_capacity(100_000, 0.01)")
|
|
n, p = 100_000, 0.01
|
|
m_target, k_target = bloom_parameters(n, p)
|
|
f = OneHashBloomFilter.from_capacity(n, p)
|
|
print(f" standard Bloom sizing: m={m_target}, k={k_target}")
|
|
print(f" partition sizes: {list(f.sizes)}")
|
|
print(f" total bits: {f.bit_count} ({f.bit_count - m_target:+d} vs target)")
|
|
print(f" k used: {f.k}")
|
|
print(f" blake2b digest: {f.digest_size} bytes ({8 * f.digest_size} bits)")
|
|
|
|
rng = random.Random(42)
|
|
for _ in range(n):
|
|
f.add(b"member:" + rng.randbytes(16))
|
|
queries = 200_000
|
|
hits = sum(b"other:" + rng.randbytes(16) in f for _ in range(queries))
|
|
print(f" inserted {len(f)} keys, queried {queries} non-members")
|
|
print(f" expected fp (Eq. 6): {f.expected_fp_rate():.5f}")
|
|
print(f" observed fp: {hits / queries:.5f} ({hits} hits)")
|
|
|
|
|
|
class SaltedBloomFilter:
|
|
"""Baseline: one m-bit array, k independent blake2b calls with distinct salts."""
|
|
|
|
def __init__(self, m: int, k: int):
|
|
self.m, self.k = m, k
|
|
self.bits = bytearray((m + 7) // 8)
|
|
self.salts = [i.to_bytes(16, "big") for i in range(k)]
|
|
|
|
def _indexes(self, key: bytes):
|
|
for salt in self.salts:
|
|
d = hashlib.blake2b(key, digest_size=8, salt=salt).digest()
|
|
yield int.from_bytes(d, "big") % self.m
|
|
|
|
def add(self, key: bytes) -> None:
|
|
for i in self._indexes(key):
|
|
self.bits[i >> 3] |= 1 << (i & 7)
|
|
|
|
def __contains__(self, key: bytes) -> bool:
|
|
for i in self._indexes(key):
|
|
if not self.bits[i >> 3] & (1 << (i & 7)):
|
|
return False
|
|
return True
|
|
|
|
|
|
def timing() -> None:
|
|
section("3. Timing: OHBF vs k salted blake2b hashes, 1 KB keys")
|
|
n, p = 20_000, 0.01
|
|
m, k = bloom_parameters(n, p)
|
|
rng = random.Random(1)
|
|
members = [rng.randbytes(1024) for _ in range(n)]
|
|
others = [rng.randbytes(1024) for _ in range(n)]
|
|
|
|
def run(f) -> tuple[float, float, int]:
|
|
t0 = time.perf_counter()
|
|
for key in members:
|
|
f.add(key)
|
|
t1 = time.perf_counter()
|
|
fp = sum(key in f for key in others)
|
|
assert all(key in f for key in members)
|
|
t2 = time.perf_counter()
|
|
return t1 - t0, t2 - t1, fp
|
|
|
|
results = {}
|
|
for name, make in [
|
|
("OHBF (1 hash)", lambda: OneHashBloomFilter.from_capacity(n, p)),
|
|
(f"salted ({k} hashes)", lambda: SaltedBloomFilter(m, k)),
|
|
]:
|
|
best = min((run(make()) for _ in range(3)), key=lambda r: r[0] + r[1])
|
|
results[name] = best
|
|
|
|
print(f" n={n}, k={k}, key=1024 bytes, best of 3 runs")
|
|
print(f" {'filter':<20} {'add':>9} {'lookup*':>9} {'fp':>7}")
|
|
for name, (add_s, look_s, fp) in results.items():
|
|
print(f" {name:<20} {add_s * 1e3:>7.1f}ms {look_s * 1e3:>7.1f}ms {fp / n:>7.4f}")
|
|
(oa, ol, _), (sa, sl, _) = results.values()
|
|
print(f" speedup: add {sa / oa:.2f}x, lookup {sl / ol:.2f}x")
|
|
print(
|
|
" * lookup = n non-member queries (these short-circuit) + n member\n"
|
|
" queries (all k bits checked). The salted filter short-circuits too,\n"
|
|
" so on misses it often hashes only 1-2 times; the gap there is smaller."
|
|
)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
hand_example()
|
|
realistic()
|
|
timing()
|