list.pop(0) vs. collections.dequeue

[Arnaud Delobelle]

Steve Howell <showell30 at yahoo.com> writes:

> On Jan 22, 12:14 pm, Chris Rebert <c... at rebertia.com> wrote:
>> On Fri, Jan 22, 2010 at 11:14 AM, Steve Howell <showel... at yahoo.com> wrote:
>> > The v2.6.4 version of the tutorial says this:
>>
>> > '''
>> > It is also possible to use a list as a queue, where the first element
>> > added is the first element retrieved (“first-in, first-out”); however,
>> > lists are not efficient for this purpose. While appends and pops from
>> > the end of list are fast, doing inserts or pops from the beginning of
>> > a list is slow (because all of the other elements have to be shifted
>> > by one).
>> > '''
>>
>> > Is that really true in CPython?  It seems like you could advance the
>> > pointer instead of shifting all the elements.  It would create some
>> > nuances with respect to reclaiming the memory, but it seems like an
>> > easy way to make lists perform better under a pretty reasonable use
>> > case.
>>
>> > Does anybody know off the top of their head if the "have-to-be-shifted-
>> > by-one" warning is actually valid?
>>
>> Judging by the "Sorted dictionary" thread responses: Yes.
>>
>
> I think you are referring to this comment:
>
> '''
> Insertion and deletion are still O(n) as all items to the right of the
> inserted/deleted one have to be shifted by one place.
> '''
>
>
> I can certainly see why most reasonable implementations of a list
> would have insertion/deletion in the middle of the list be O(N), but I
> don't think that limitation has to apply for the special cases of the
> beginning and end of the list.

I made the comment you quoted.  In CPython, it is O(n) to delete/insert
an element at the start of the list - I know it because I looked at the
implementation a while ago.  This is why collections.deque exists I
guess.  I don't know how they are implemented but insertion/deletion at
either end are O(1) and so is random access.  So they are the data
structure that you want.

If you want evidence for lists, rather than my word, try:

>>> import timeit
>>> timeit.Timer('while t:del t[0]', 't=[0]*100000').timeit(1)
1.8452401161193848
>>> timeit.Timer('while t:del t[-1]', 't=[0]*100000').timeit(1)
0.017747163772583008

>>> timeit.Timer(
    'while t:del t[0]', 
    'from collections import deque; t=deque([0]*100000)'
).timeit(1)
0.022077083587646484
>>> timeit.Timer(
    'while t:del t[-1]',
    'from collections import deque; t=deque([0]*100000)'
).timeit(1)
0.027813911437988281

-- 
Arnaud