Skip to main content

A Cython fast number set based on bitfields

Project description


This is a fork of which has been adapted to be efficient with sparse bitfields and large numbers. The API is the same but support for Python 2 has been dropped.

WARNING : The serialisation mechanism isn't portable at the moment.


$ sudo pip3 install sparsebitfield


>>> import sparsebitfield
>>> field = sparsebitfield.SparseBitfield()
>>> field.add(100)
>>> print(list(field))
>>> second = sparsebitfield.SparseBitfield([2, 100])
>>> list(field | second)
[2, 100]

>>> second.add(10000)
>>> second.pickle()
b'BZ:x\x9c\xed\xce\xc1\t\x00 \x0c\x04\xb0+8@\xf7\x9f\xd6\x87\x0f7P(\xc9\x04I\x8eZ\xb9:\x00\x93\xd4\xef\x00\x00\x00\x00\x00\x00\x00<\xb3\x01\xda\x86\x00\x17'

>>> import random
>>> large=sparsebitfield.SparseBitfield(random.sample(range(1000000), 500000)) # 500,000 items, randomly distributed
>>> len(large)
>>> len(large.pickle())
125269  # 122KB

>>> large=sparsebitfield.SparseBitfield(range(1000000)) # 1 million items, all sequential
>>> len(large)
>>> len(large.pickle())
69 # <100 bytes

Sparse bitfields support most of the same operations/usage as regular sets, see the tests for examples.


Sparsebitfield was designed to efficiently handle tracking large sets of items.

The main design goals were:

  • Space-efficient serialisation format
  • Fast membership tests and set differences
  • Space-efficent handling of large sparse bitfields
  • Support for large integers (>2**64)

Internally, sparsebitfield achieves this by using a 1-d bitmap split into pages. These pages are organised as a sorted list.

Within a page, a number is recorded as being present in the set by setting the n-th bit to 1. I.e. the set([1]) is recorded as ...00000010b, while set([1,4]) would be ...00010010b.

If a particular page is empty (no set members in that range) or full, then the bitfield is discarded, and represented by an EMPTY or FULL flag. Pages which haven not been written to don't take up any memory at all. Also empty pages are not included in the pickled data.

Project details

Download files

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

Files for sparsebitfield, version 0.2.3
Filename, size File type Python version Upload date Hashes
Filename, size sparsebitfield-0.2.3.tar.gz (97.5 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page