On Sun, 21 Sep 2014 11:21:15 +0200
Stefan Drees
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.