Skip to main content

A dumb but fast bloom filter.

Project description

simplebloom is a (probably) dumb but fast bloom filter. To quote Wikipedia:

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either “possibly in set” or “definitely not in set”. Elements can be added to the set, but not removed […]; the more items added, the larger the probability of false positives.

The included BloomFilter class is quite dumb as it’s fixed size, only supports strings, and always uses the blake2s hash function included with Python 3.6+. But at least it’s fast, hey?

Speed

~1.4 million elements/s on an i7-6700HQ, both adding and checking.

Usage

Note that around 98% of the execution time is spent creating UUIDs.

import uuid
from simplebloom import BloomFilter

keys = [uuid.uuid4().hex for _ in range(100000)]
bf = BloomFilter(len(keys))

for k in keys:
    bf += k

with open('test.filter', 'wb') as fp:
    bf.dump(fp)

with open('test.filter', 'rb') as fp:
    bf = BloomFilter.load(fp)

for k in keys:
    assert k in bf

other_keys = [uuid.uuid4().hex for _ in range(1000000)]
fp = 0
for k in other_keys:
    fp += k in bf
print(bf.false_positive_prob, fp / len(other_keys))

The BloomFilter class

A simple but fast bloom filter. Elements must be strings.

Add an element and check whether it is contained:

bf = BloomFilter(1000)
bf += 'hellobloom'
assert 'hellobloom' in bf

false_positive_prob defaults to 1 / num_elements.

The number of bits in the filter is num_bits = num_elements * log(false_positive_prob) / log(1 / 2**log(2)), rounded to the next highest multiple of 8.

The number of hash functions used is num_hashes = round(num_bits / num_elements * log(2)) .

Parameters:

num_elements: expected max number of elements in the filter false_positive_prob: desired approximate false positive probability

BloomFilter.__iadd__ / add element

Use the “inplace add” syntax to add elements bf += k, where bf is the BloomFilter and k a string.

BloomFilter.__contains__ / contains element

Use the “contains” syntax to check if an element is (probably) in the filter k in bf, where bf is the BloomFilter and k a string.

BloomFilter.load

Load a filter from a path or file-like:

bf = BloomFilter.load('bloom.filter')

with open('bloom.filter', 'rb') as fp:
    bf = BloomFilter.load(fp)
Parameters:
  • fp: path or file-like

BloomFilter.loads

Load a filter from a buffer:

data = bf.dumps()
bf = BloomFilter.loads(data)
Parameters:

data: filter data

BloomFilter.dump

Dump filter to a path or file-like:

bf.dump('bloom.filter')

with open('bloom.filter', 'wb') as fp:
    bf.dump(fp)
Parameters:
  • fp: path or file-like

BloomFilter.dumps

Returns filter data as buffer:

data = bf.dumps()
bf = BloomFilter.loads(data)

Developing

Extension code is generated by Cython. Install Cython to make and build changes to the extension.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

simplebloom-1.0.6.tar.gz (66.4 kB view hashes)

Uploaded Source

Built Distributions

simplebloom-1.0.6-pp310-pypy310_pp73-win_amd64.whl (25.2 kB view hashes)

Uploaded PyPy Windows x86-64

simplebloom-1.0.6-pp310-pypy310_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (25.5 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-pp310-pypy310_pp73-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (26.2 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-pp310-pypy310_pp73-macosx_11_0_arm64.whl (24.1 kB view hashes)

Uploaded PyPy macOS 11.0+ ARM64

simplebloom-1.0.6-pp310-pypy310_pp73-macosx_10_15_x86_64.whl (24.2 kB view hashes)

Uploaded PyPy macOS 10.15+ x86-64

simplebloom-1.0.6-pp39-pypy39_pp73-win_amd64.whl (25.1 kB view hashes)

Uploaded PyPy Windows x86-64

simplebloom-1.0.6-pp39-pypy39_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (25.5 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-pp39-pypy39_pp73-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (26.1 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-pp39-pypy39_pp73-macosx_11_0_arm64.whl (24.1 kB view hashes)

Uploaded PyPy macOS 11.0+ ARM64

simplebloom-1.0.6-pp39-pypy39_pp73-macosx_10_15_x86_64.whl (24.1 kB view hashes)

Uploaded PyPy macOS 10.15+ x86-64

simplebloom-1.0.6-pp38-pypy38_pp73-win_amd64.whl (24.6 kB view hashes)

Uploaded PyPy Windows x86-64

simplebloom-1.0.6-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (24.8 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-pp38-pypy38_pp73-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (25.6 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-pp38-pypy38_pp73-macosx_11_0_arm64.whl (23.4 kB view hashes)

Uploaded PyPy macOS 11.0+ ARM64

simplebloom-1.0.6-pp38-pypy38_pp73-macosx_10_9_x86_64.whl (23.1 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

simplebloom-1.0.6-pp37-pypy37_pp73-win_amd64.whl (24.6 kB view hashes)

Uploaded PyPy Windows x86-64

simplebloom-1.0.6-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (24.8 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-pp37-pypy37_pp73-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (25.6 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-pp37-pypy37_pp73-macosx_10_9_x86_64.whl (23.1 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

simplebloom-1.0.6-cp313-cp313-win_amd64.whl (27.8 kB view hashes)

Uploaded CPython 3.13 Windows x86-64

simplebloom-1.0.6-cp313-cp313-win32.whl (26.0 kB view hashes)

Uploaded CPython 3.13 Windows x86

simplebloom-1.0.6-cp313-cp313-musllinux_1_2_x86_64.whl (30.5 kB view hashes)

Uploaded CPython 3.13 musllinux: musl 1.2+ x86-64

simplebloom-1.0.6-cp313-cp313-musllinux_1_2_aarch64.whl (29.3 kB view hashes)

Uploaded CPython 3.13 musllinux: musl 1.2+ ARM64

simplebloom-1.0.6-cp313-cp313-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (29.0 kB view hashes)

Uploaded CPython 3.13 manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-cp313-cp313-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (30.2 kB view hashes)

Uploaded CPython 3.13 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-cp313-cp313-macosx_11_0_arm64.whl (28.2 kB view hashes)

Uploaded CPython 3.13 macOS 11.0+ ARM64

simplebloom-1.0.6-cp313-cp313-macosx_10_13_x86_64.whl (28.2 kB view hashes)

Uploaded CPython 3.13 macOS 10.13+ x86-64

simplebloom-1.0.6-cp312-cp312-win_amd64.whl (28.6 kB view hashes)

Uploaded CPython 3.12 Windows x86-64

simplebloom-1.0.6-cp312-cp312-win32.whl (26.6 kB view hashes)

Uploaded CPython 3.12 Windows x86

simplebloom-1.0.6-cp312-cp312-musllinux_1_2_x86_64.whl (31.4 kB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.2+ x86-64

simplebloom-1.0.6-cp312-cp312-musllinux_1_2_aarch64.whl (30.2 kB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.2+ ARM64

simplebloom-1.0.6-cp312-cp312-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (29.9 kB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-cp312-cp312-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (31.2 kB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-cp312-cp312-macosx_11_0_arm64.whl (29.0 kB view hashes)

Uploaded CPython 3.12 macOS 11.0+ ARM64

simplebloom-1.0.6-cp312-cp312-macosx_10_9_x86_64.whl (28.8 kB view hashes)

Uploaded CPython 3.12 macOS 10.9+ x86-64

simplebloom-1.0.6-cp311-cp311-win_amd64.whl (28.3 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

simplebloom-1.0.6-cp311-cp311-win32.whl (26.3 kB view hashes)

Uploaded CPython 3.11 Windows x86

simplebloom-1.0.6-cp311-cp311-musllinux_1_2_x86_64.whl (31.0 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.2+ x86-64

simplebloom-1.0.6-cp311-cp311-musllinux_1_2_aarch64.whl (29.9 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.2+ ARM64

simplebloom-1.0.6-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (29.7 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (30.9 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-cp311-cp311-macosx_11_0_arm64.whl (28.8 kB view hashes)

Uploaded CPython 3.11 macOS 11.0+ ARM64

simplebloom-1.0.6-cp311-cp311-macosx_10_9_x86_64.whl (28.4 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

simplebloom-1.0.6-cp310-cp310-win_amd64.whl (28.2 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

simplebloom-1.0.6-cp310-cp310-win32.whl (26.5 kB view hashes)

Uploaded CPython 3.10 Windows x86

simplebloom-1.0.6-cp310-cp310-musllinux_1_2_x86_64.whl (31.1 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.2+ x86-64

simplebloom-1.0.6-cp310-cp310-musllinux_1_2_aarch64.whl (30.0 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.2+ ARM64

simplebloom-1.0.6-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (29.4 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (30.5 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-cp310-cp310-macosx_11_0_arm64.whl (28.9 kB view hashes)

Uploaded CPython 3.10 macOS 11.0+ ARM64

simplebloom-1.0.6-cp310-cp310-macosx_10_9_x86_64.whl (28.4 kB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

simplebloom-1.0.6-cp39-cp39-win_amd64.whl (28.9 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

simplebloom-1.0.6-cp39-cp39-win32.whl (27.0 kB view hashes)

Uploaded CPython 3.9 Windows x86

simplebloom-1.0.6-cp39-cp39-musllinux_1_2_x86_64.whl (31.7 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.2+ x86-64

simplebloom-1.0.6-cp39-cp39-musllinux_1_2_aarch64.whl (30.6 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.2+ ARM64

simplebloom-1.0.6-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (30.0 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (31.0 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-cp39-cp39-macosx_11_0_arm64.whl (29.5 kB view hashes)

Uploaded CPython 3.9 macOS 11.0+ ARM64

simplebloom-1.0.6-cp39-cp39-macosx_10_9_x86_64.whl (29.1 kB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

simplebloom-1.0.6-cp38-cp38-win_amd64.whl (29.0 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

simplebloom-1.0.6-cp38-cp38-win32.whl (27.1 kB view hashes)

Uploaded CPython 3.8 Windows x86

simplebloom-1.0.6-cp38-cp38-musllinux_1_2_x86_64.whl (31.4 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.2+ x86-64

simplebloom-1.0.6-cp38-cp38-musllinux_1_2_aarch64.whl (30.3 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.2+ ARM64

simplebloom-1.0.6-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (30.2 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (31.2 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-cp38-cp38-macosx_11_0_arm64.whl (29.9 kB view hashes)

Uploaded CPython 3.8 macOS 11.0+ ARM64

simplebloom-1.0.6-cp38-cp38-macosx_10_9_x86_64.whl (29.4 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

simplebloom-1.0.6-cp37-cp37m-win_amd64.whl (29.4 kB view hashes)

Uploaded CPython 3.7m Windows x86-64

simplebloom-1.0.6-cp37-cp37m-win32.whl (27.2 kB view hashes)

Uploaded CPython 3.7m Windows x86

simplebloom-1.0.6-cp37-cp37m-musllinux_1_2_x86_64.whl (31.7 kB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.2+ x86-64

simplebloom-1.0.6-cp37-cp37m-musllinux_1_2_aarch64.whl (30.8 kB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.2+ ARM64

simplebloom-1.0.6-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (30.7 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ ARM64

simplebloom-1.0.6-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (31.5 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

simplebloom-1.0.6-cp37-cp37m-macosx_10_9_x86_64.whl (29.8 kB view hashes)

Uploaded CPython 3.7m macOS 10.9+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page