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 list that never changes length.

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

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

Uploaded Source

Built Distribution

blist-0.9.9-py2.5-linux-i686.egg (86.5 kB view details)

Uploaded Egg

File details

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

File metadata

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

File hashes

Hashes for blist-0.9.9.tar.gz
Algorithm Hash digest
SHA256 5f004ad7061e1ee48c47cca8cb168c5604f710e47386920085fa346db0f68abe
MD5 6e9aa2d540135f5fed0b5577fc7bbe19
BLAKE2b-256 228d89d4af0de3af79e34e45ceb72a4261a5825ba827087d32db13a794dd714b

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for blist-0.9.9-py2.5-linux-i686.egg
Algorithm Hash digest
SHA256 22628b53392a9e08bcb14182296c0e970cfca3f9535e89a615eb37f46fcfe173
MD5 68f6a2e7e5b9299f5b6a3ef0949700a4
BLAKE2b-256 daff394cf7d618a2418b4501e57de2ed152140fd2f2b34278c83d7ec521a087d

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