Skip to main content

a list-like type with better asymptotic performance and similar performance on small lists

Project description

The BList is a type that looks, acts, and quacks like a Python list, but has better performance for many (but not all) use cases. The use cases where the BList is slightly slower than Python’s list are as follows (O(log n) vs. O(1)):

  1. A large lists where inserts and deletes are only at the end of the list (LIFO).

Earlier versions of BList were also slower for large lists that never change length, but this is no longer true as of version 0.9.6, which features amortized worst-case O(1) getitem and setitem operations.

With that disclaimer out of the way, here are some of the use cases where the BLists is dramatically faster than the built-in list:

  1. Insertion into or removal from a large list (O(log n) vs. O(n))

  2. Taking large slices of large lists (O(log n) vs O(n))

  3. Making shallow copies of large lists (O(1) vs. O(n))

  4. Changing large slices of large lists (O(log n + log k) vs. O(n + k))

  5. Multiplying a list to make a large, sparse list (O(log k) vs. O(kn))

You’ve probably noticed that we keep referring to “large lists”. For small lists, BLists and the built-in list have very similar performance.

So you can see the performance of the BList in more detail, several performance graphs available at the following link: http://stutzbachenterprises.com/blist/

Example usage:

>>> from blist import *
>>> x = blist([0])             # x is a BList with one element
>>> x *= 2**29                 # x is a BList with > 500 million elements
>>> x.append(5)                # append to x
>>> y = x[4:-234234]           # Take a 500 million element slice from x
>>> del x[3:1024]              # Delete a few thousand elements from x

For comparison, on most systems the built-in list just raises MemoryError and calls it a day.

The BList has two key features that allow it to pull off this performance:

  1. Internally, a B+Tree is a wide, squat tree. Each node has a maximum of 128 children. If the entire list contains 128 or fewer objects, then there is only one node, which simply contains an array of the objects. In other words, for short lists, a BList works just like Python’s array-based list() type. Thus, it has the same good performance on small lists.

  2. The BList type features transparent copy-on-write. If a non-root node needs to be copied (as part of a getslice, copy, setslice, etc.), the node is shared between multiple parents instead of being copied. If it needs to be modified later, it will be copied at that time. This is completely behind-the-scenes; from the user’s point of view, the BList works just like a regular Python list.

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

blist-0.9.13.tar.gz (91.1 kB view details)

Uploaded Source

Built Distributions

blist-0.9.13.win32-py3.0.exe (222.7 kB view details)

Uploaded Source

blist-0.9.13.win32-py2.6.exe (93.8 kB view details)

Uploaded Source

blist-0.9.13-py2.6-linux-i686.egg (87.4 kB view details)

Uploaded Egg

blist-0.9.13-py2.5-linux-i686.egg (87.2 kB view details)

Uploaded Egg

blist-0.9.13-py2.5-cygwin-1.5.25-i686.egg (90.6 kB view details)

Uploaded Egg

File details

Details for the file blist-0.9.13.tar.gz.

File metadata

  • Download URL: blist-0.9.13.tar.gz
  • Upload date:
  • Size: 91.1 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No

File hashes

Hashes for blist-0.9.13.tar.gz
Algorithm Hash digest
SHA256 321c101a68d0b6613bcdedea1f871dd8d521adf7ce69d3614c1eac6fd41e6881
MD5 07e9d4b53719d3c969c52e6871e15af8
BLAKE2b-256 369aa362e5dfecd05e5ff5065debd4e72f036ac3fcc90031c005bb4ae9853d45

See more details on using hashes here.

File details

Details for the file blist-0.9.13.win32-py3.0.exe.

File metadata

File hashes

Hashes for blist-0.9.13.win32-py3.0.exe
Algorithm Hash digest
SHA256 16183d05ad36c132a6c905f8eacb74544c67d1bfc71170e8184e98d815d9ede4
MD5 a4daf616421ba0106788b9aa0239f1a3
BLAKE2b-256 14c3967fc05e7e94d137804e846c1b185f407e23d90877f5038094a5603a7625

See more details on using hashes here.

File details

Details for the file blist-0.9.13.win32-py2.6.exe.

File metadata

File hashes

Hashes for blist-0.9.13.win32-py2.6.exe
Algorithm Hash digest
SHA256 a9bf000523ad7ce4dcaebd24a4869d3c1a83b633b9b8b000d8524ff099fee56c
MD5 032f6a4e4ab7ab319e2bf8ae92f93fd0
BLAKE2b-256 3951cda9c119ac9a9a16bc02b57f54c63c18097e404a69f568e97551cf8f8a7b

See more details on using hashes here.

File details

Details for the file blist-0.9.13-py2.6-linux-i686.egg.

File metadata

File hashes

Hashes for blist-0.9.13-py2.6-linux-i686.egg
Algorithm Hash digest
SHA256 d0789f13a4b46a0415a1879e4afacee828507176af13670d8078acef1f11be89
MD5 3657e8f8ab62a8f12b614cfa848f6801
BLAKE2b-256 1b3419f9df300d59c13d9bc3bc9e242eea14f086316ad64c2c34b789f0980a2e

See more details on using hashes here.

File details

Details for the file blist-0.9.13-py2.5-linux-i686.egg.

File metadata

File hashes

Hashes for blist-0.9.13-py2.5-linux-i686.egg
Algorithm Hash digest
SHA256 fe345f92f7ddd78ef93dc5f546062f00cd991fc0add03f053a609282160f010e
MD5 ec4c9500c3999bd18912f96875cea0bf
BLAKE2b-256 3e6c682278a5029b388bcf7cf452802c73a2c7503a6af22bb0567248f274702d

See more details on using hashes here.

File details

Details for the file blist-0.9.13-py2.5-cygwin-1.5.25-i686.egg.

File metadata

File hashes

Hashes for blist-0.9.13-py2.5-cygwin-1.5.25-i686.egg
Algorithm Hash digest
SHA256 0515fe0367fd5a6aa2a54af10ad70ec293d179e776b61eea4f589ad7a7ee4bd4
MD5 b5c3f01cc806b83aa5911c78243e0170
BLAKE2b-256 79d68b3afabdadfffad72ee46a5f08085e2736b820d1dca235d279446d8130c6

See more details on using hashes here.

Supported by

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