list.pop(0) vs. collections.dequeue
Alf P. Steinbach
alfps at start.no
Sat Jan 23 09:32:26 CET 2010
* Steve Howell:
> On Jan 23, 12:13 am, Terry Reedy <tjre... at udel.edu> wrote:
>> Challenge yes, mock no.
>> Part of writing good basic data structures is not adding needless
>> complication from featuritis and not penalizing 99.99% of access to
>> satify a .01% need better satisfied another way.
> I would like to challenge your assertion that advancing ob_item
> instead of doing memmove during list_ass_slice would impact the
> performance of list accesses in any way. It would only slow down
> operations that add/insert items into the list by, and then only by a
> single conditional statement, and those add/insert operations are
> already O(N) to begin with.
I'm sorry, no, the last part is incorrect.
Appending to a 'list' can currently be constant time, if OS reallocation is
constant time (as the string '+' optimization relies on).
With the pop optimization it can no longer be constant time without risking an
accumulation of unused memory, a memory leak, although it can be amortized
constant time, at the cost of wasting some percentage of memory.
Cheers & hth.,
More information about the Python-list