[Python-ideas] Putting `blist` into collections module

[Antoine Pitrou]

On Sun, 21 Sep 2014 11:21:15 +0200
Stefan Drees <stefan at drees.name> wrote:
> On 2014-09-21 07:36 +02:00, Guido van Rossum wrote:
> > So write a PEP for sorted dict and tree.
> 
> but let us all read it - and the implementation samples - exactly before 
> even thinking about rejecing it ;-) as in the rejected PEP3128 I read 
> (in the fifth paragraph of
> http://legacy.python.org/dev/peps/pep-3128/#use-case-trade-offs not 
> counting the list):
> 
> """
> The performance for the LIFO use case could be improved to O(n) time, by 
> caching a pointer to the right-most leaf within the root node. For lists 
> that do not change size, the common case of sequential access could also 
> be improved to O(n) time via caching in the root node. [...]
> """
> 
> which - not really being in the topic - I would rather expect to read:
> """
> The performance for the LIFO use case could be improved to O(1) time, by 
> caching a pointer to the right-most leaf within the root node. For lists 
> that do not change size, the common case of sequential access could also 
> be improved to O(1) time via caching in the root node. [...]
> """
> 
> At least this is what I would consider an enhancement over O(log n) and 
> also expect from a single cached pointer implementation and the like.

I suspect O(n) means when n doing LIFO iterations, so O(1) amortized.

Also, the LIFO (i.e. stack) use case was important for the prospect of
replacing the list type with blist. If blist is merely a new container,
the LIFO use case is perfectly satisfied by the list type already.

By the way, one should remember the PEP was written years ago. I don't
know how much the blist type has changed (the author doesn't seem to
provide a changelog, unfortunately), but according to the following
benchmarks there doesn't seem to be any remaining performance drawback
compared to list:

http://stutzbachenterprises.com/performance-blist

Regards

Antoine.