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

Uploaded Source

Built Distributions

blist-0.9.10-py2.6-linux-i686.egg (86.4 kB view details)

Uploaded Egg

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

Uploaded Egg

File details

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

File metadata

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

File hashes

Hashes for blist-0.9.10.tar.gz
Algorithm Hash digest
SHA256 9d67be8c1941300a2d45c32f867dae356ba03d4ea0c4ab4bd5f5d8a9969232f4
MD5 be84b252d207d52f6220e93feda821c6
BLAKE2b-256 278708a0d36f3955da0b04312a1c0cc47592d056cd8a87f4d443675623a2485e

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for blist-0.9.10-py2.6-linux-i686.egg
Algorithm Hash digest
SHA256 deb4853650cab8cb0e707553ecce19493f78d93045bd24d638e5e1f6844bfff2
MD5 66931f686069df2952a061c17358bde6
BLAKE2b-256 de35d3144007d79a07517444aa114d16d4704d042ad9eada0fd079cf1d023932

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for blist-0.9.10-py2.5-linux-i686.egg
Algorithm Hash digest
SHA256 91a2efef7ca0177b2b370cc78620a6873425abd03c3dd67129e15207b47019fc
MD5 a47dece903dc00f000d6bb8ef842f93b
BLAKE2b-256 aba2f59dfd4e42e61557d92d3c0e7b2541b7a640beb42fdc11e005c5db41e3e1

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