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.7.tar.gz (83.5 kB view details)

Uploaded Source

Built Distribution

blist-0.9.7-py2.5-linux-i686.egg (102.5 kB view details)

Uploaded Egg

File details

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

File metadata

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

File hashes

Hashes for blist-0.9.7.tar.gz
Algorithm Hash digest
SHA256 3496611e325c6d86addbc999cca0632ea386cb2030e1a95b899652698e19a5da
MD5 4fb5604c87586ba4d62d54cc99f6bb92
BLAKE2b-256 fc8a09c4e87e349a0edb5db7e71ba8a2312c79715d1fb99b07b6dbca63e39616

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for blist-0.9.7-py2.5-linux-i686.egg
Algorithm Hash digest
SHA256 027450dcb414f6ba170ab95a952469ba3e248545a2221475b37c57aead2ec88a
MD5 2a7406e260f73c713eec79c333e85ec2
BLAKE2b-256 dd54d982367fd171dc97bfcc2a7b1763b0569eda0d063f4dc4b5c6a7ce06baae

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