Skip to main content

a list-like type with better asymptotic performance

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. Below are some of the unique features of the BList:

  • just as fast as a Python list() when the list is small

  • insertion or removal from the list takes O(log n) time

  • getslice runs in O(log n) time and uses O(log n) memory, regardless of slice size

  • making a shallow copy runs in O(1) time and uses O(1) memory

  • setslice runs in O(log n + log k) time if the inserted slice is a BList of length k

  • multipling a BList by k takes O(log k) time and O(log k) memory

Example:

>>> from blist import *
>>> x = blist([0])
>>> x *= 2**29
>>> x.append(5)
>>> y = x[4:-234234]
>>> del x[3:1024]

None of the above operations have a noticeable delay, even though the lists have over 500 million elements due to line 3. The BList has two key features that allow it to pull this 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.

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

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

Uploaded Source

Built Distributions

blist-0.9.3-py2.5-linux-i686.egg (67.2 kB view details)

Uploaded Egg

blist-0.9.3-py2.5-cygwin-1.5.23-i686.egg (76.4 kB view details)

Uploaded Egg

File details

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

File metadata

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

File hashes

Hashes for blist-0.9.3.tar.gz
Algorithm Hash digest
SHA256 3343763716c5bc79b1ba8c4ae463281c185d72489f389e6f3c6886e8233f6367
MD5 1921f33de12691f97fb1095d23d2f9c7
BLAKE2b-256 38fd45cdfeeff4426b4168e75adaa5313bf7ef08ece86baeafb43ae6e130967e

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for blist-0.9.3-py2.5-linux-i686.egg
Algorithm Hash digest
SHA256 8464fe6908f5f038899202a6863e710e402b2ab536acf9be3072d23fd0eb52b5
MD5 055cc83172199edcdf8fab870ec9ac79
BLAKE2b-256 efe5b8e75657281f258fa77ed5cc83885d8204f0f9a21b84d6971f434c4f9545

See more details on using hashes here.

File details

Details for the file blist-0.9.3-py2.5-cygwin-1.5.23-i686.egg.

File metadata

File hashes

Hashes for blist-0.9.3-py2.5-cygwin-1.5.23-i686.egg
Algorithm Hash digest
SHA256 5a87fbc56bee0fad5ab4d3d9c4f1efaffe276bf0716a52a8326dba9e88e14584
MD5 797c2fb82591dc4976facd71ee0b0e13
BLAKE2b-256 c6d8cb05569d703a10c2102f6b8946b1143b86fa1541d031e18ce4da40e3befe

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