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:
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.
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/
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for blist-0.9.3-py2.5-linux-i686.egg
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 | 8464fe6908f5f038899202a6863e710e402b2ab536acf9be3072d23fd0eb52b5 |
|
| MD5 | 055cc83172199edcdf8fab870ec9ac79 |
|
| BLAKE2b-256 | efe5b8e75657281f258fa77ed5cc83885d8204f0f9a21b84d6971f434c4f9545 |
Hashes for blist-0.9.3-py2.5-cygwin-1.5.23-i686.egg
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 | 5a87fbc56bee0fad5ab4d3d9c4f1efaffe276bf0716a52a8326dba9e88e14584 |
|
| MD5 | 797c2fb82591dc4976facd71ee0b0e13 |
|
| BLAKE2b-256 | c6d8cb05569d703a10c2102f6b8946b1143b86fa1541d031e18ce4da40e3befe |
