blist in standard library (was Re: Balanced trees)

Mark Lawrence breamoreboy at
Sat Mar 15 13:31:26 CET 2014

On 15/03/2014 01:13, Joshua Landau wrote:
> On 8 March 2014 20:37, Mark Lawrence <breamoreboy at> wrote:
>> I've found this link useful
>> I also don't want all sorts of data structures added to the Python library.
>> I believe that there are advantages to leaving specialist data structures on
>> pypi or other sites, plus it means Python in a Nutshell can still fit in
>> your pocket and not a 40 ton articulated lorry, unlike the Java equivalent.
> The thing we really need is for the blist containers to become stdlib
> (but not to replace the current list implementation). The rejected PEP
> ( misses a few important
> points, largely in how the "log(n)" has a really large base:
> random.choice went from 1.2µs to 1.6µs from n=1 to n=10⁸, vs 1.2µs for
> a standard list.
> Further, it's worth considering a few advantages:
> * copy is O(1), allowing code to avoid mutation by just copying its
> input, which is good practice.
> * FIFO is effectively O(1), as the time just about doubles from n=1 to
> n=10⁸ so will never actually branch that much. There is still a speed
> benefit of collections.deque, but it's much, much less significant.
> This is very useful when considering usage as a multi-purpose data
> structure, and removes demand for explicit linked lists (which have
> foolishly been reimplemented loads of times).
> * It reduces demand for trees:
>      * There are efficient implementations of sortedlist, sortedset and
> sorteddict.
>      * Slicing, slice assignment and slice deletion are really fast.
>      * Addition of lists is sublinear. Instead of
> "list(itertools.chain(...))", one can add in a loop and end up
> *faster*.
> I think blist isn't very popular not because it isn't really good, but
> because it isn't a specialised structure. It is, however, almost there
> for almost every circumstance. This can help keep the standard library
> clean, especially of tree data structures.
> Here's what we kill:
> * Linked lists and doubly-linked lists, which are scarily popular for
> whatever reason. Sometimes people claim that collections.deque isn't
> powerful enough for whatever they want, and blist will almost
> definitely sate those cases.
> * Balanced trees, with blist.sortedlist. This is actually needed right now.
> * Poor performance in the cases where a lot of list merging and pruning happens.
> * Most uses of bisect.
> * Some instances where two data structures are used in parallel in
> order to keep performance fast on disparate operations (like `x in y`
> and `y[i]`).
> Now, I understand there are downsides to blist. Particularly, I've
> looked through the "benchmarks" and they seem untruthful. Further,
> we'd need a maintainer. Finally, nobody jumps at blists because
> they're rarely the obvious solution. Rather, they attempt to be a
> different general solution. Hopefully, though, a stdlib inclusion
> could make them a lot more obvious, and support in some current
> libraries could make them feel more at home.
> I don't know whether this is a good idea, but I do feel that it is
> more promising and general than having a graph in the standard
> library.

I'd raise this on python-dev or python ideas as a result of reading PEP 
3128.  Specifically the second paragraph states Raymond Hettinger's sage 

"Depending on its success as a third-party module, it still has a chance 
for inclusion in the collections module. The essential criteria for that 
is whether it is a superior choice for some real-world use cases. I've 
scanned my own code and found no instances where BList would have been 
preferable to a regular list. However, that scan has a selection bias 
because it doesn't reflect what I would have written had BList been 
available. So, after a few months, I intend to poll comp.lang.python for 
BList success stories. If they exist, then I have no problem with 
inclusion in the collections module. After all, its learning curve is 
near zero -- the only cost is the clutter factor stemming from 
indecision about the most appropriate data structure for a given task."

My fellow Pythonistas, ask not what our language can do for you, ask 
what you can do for our language.

Mark Lawrence

This email is free from viruses and malware because avast! Antivirus protection is active.

More information about the Python-list mailing list