DanielStutzbach / blist

The following should throw an exception:

x = blist(range(10))
while True:
    x.extend(x)

For read and delete operations, works just like a list.

For insert operations, works just like a set.

The constructor should take an optional "key" function.

They currently fall back to the default object implementation, returning a value that is too small.

Modifying a list during iteration is undefined by the Python documentation and generally inadvisable. Some people (including the 2to3 tool) rely on CPython's behavior for appending during iteration.

x = list(range(10))
for i in x:
    if i > 100: break
    x.append(i+1)
print len(x)

A regular python list prints 939. With a blist, it prints 39 (as of blist 1.0.2).

For a constant-factor performance improvement, each blist node could grow a integer "start" field indicating an offset to the first child. The children would be wrapped, so that for a blist with a LIMIT of 8, a start of 4, and 7 children, their order would be: 4, 5, 6, 7, 0, 1, 2.

That would dramatically decrease the cost of inserting near the beginning of a node, especially if LIMIT is large. For FIFO operation, blist should be able to soundly beat the list and compete head-to-head with the deque.

Right now, small lists allocate enough space for LIMIT children, even if only one or two are actually needed. For small lists (where the root is a leaf), the memory footprint is terrible compared to an array-based list. The root needs to be able to dynamically choose the number of children. However, it needs to be very careful because hitherto a root node has been treated as a subclass of a regular node. With this change, routines cannot assume that any node has space for LIMIT children.

Height == 0 indicates a leaf
Height == 1 indicates the parent of a leaf
etc.

"height" uses the same memory footprint as "leaf" and requires the same number of CPU instructions to test for leafiness.

"height" will speed up a few operations slightly. Specifically, the extend operation would become O(|log n - log k|), an improvement over O(log n + log k). Many other operations internally use "extend" and would get a small constant-factor speedup.

Finally, "height" will allow for additional error-checking in debug builds, since we can check the following invariant: the height of any non-leaf node's children must equal the node's height minus one.

It should copy the internal blist structure, making it very fast when copy-on-write is being heavily used. Observe how list() handles it:

>>> class blah:
...  pass
...
>>> x = blah()
>>> y = [x,x]
>>> z = copy.deepcopy(y)
>>> id(z[0]), id(z[1])
(2146287308, 2146287308)
>>> id(x)
2146287244

A btuple is a read-only version of the blist and uses the same data structures and principally the same algorithms. It can be created efficiently from an existing blist and taking a slice of a btuple is fast (and returns a new btuple--not a blist). Unlike a blist, a btuple is hashable, allowing it to be used as a key for a dictionary.

Analogous to the sortedset type. It works like a dict but .keys always returns the keys in sorted order. Under-the-hood, it's stores both a hash table (to make lookups O(1)) and a blist.

Right now, a full node is allocated regardless of the list size. For very small lists (where the root is a leaf), we should mimic the behavior of Python's built-in list.