list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 25, 8:31 pm, Paul Rubin <no.em... at nospam.invalid> wrote:
> Steve Howell <showel... at yahoo.com> writes:
> > I haven't profiled deque vs. list, but I think you are correct about
> > pop() possibly being a red herring....
> > For really large lists, I suppose memmove() would eventually start to
> > become a bottleneck, but it's brutally fast when it just moves a
> > couple kilobytes of data around.
>
> One way to think of Python is as a scripting wrapper around a bunch of C
> functions, rather than as a full-fledged programming language.  Viewed
> that way, list operations like pop(0) are essentially constant time
> unless the list is quite large.  By that I mean you can implement
> classic structures like doubly-linked lists using Python tuples, but
> even though inserting into the middle of them is theoretically O(1), the
> memmove's of the native list operations will be much faster in practice.
> Programs dealing with large lists (more than a few thousand elements)
> are obviously different and if your program is using such large lists,
> you have to plan a little differently when writing the code.

Thanks.  That is a good way of looking at.

>
> Realistically the CPython interpreter is so slow that the memmove is
> unnoticable, and Python (at least CPython) just isn't all that
> conductive to writing fast code.  It makes up for this in programmer
> productivity for the many sorts of problems in which moderate speed
> is acceptable.
>

Definitely, and moderate speed is enough in a surprisingly large
number of applications.


> > Thanks for your patience in responding to me, despite the needlessly
> > abrasive tone of my earlier postings.  
>
> I wondered whether you might have come over from the Lisp newsgroups,
> which are pretty brutal.  We try to be friendlier here (not that we're
> always successful).  Anyway, welcome.
>

:)

> >   1) Summarize all this discussion and my lessons learned in some kind
> > of document.  It does not have to be a PEP per se, but I could provide
> > a useful service to the community by listing pros/cons/etc.
>
> I suppose that can't hurt, but there are probably other areas (multicore
> parallelism is a perennial one) of much higher community interest.
>
> http://wiki.python.org/moin/is probably a good place to put such
> a document.
>

Ok, that's where I'll start.

> >   2) I would still advocate for removing the warning against list.pop
> > (0) from the tutorial.  I agree with Steven D'Aprano that docs really
> > should avoid describing implementation details in many instances
>
> On general principles I agree with Alex Stepanov that the running time
> of a function should be part of its interface (nobody wants to use a
> stack of popping an element takes quadratic time) and therefore should
> be stated in the docs.  Python just has a weird incongruence between the
> interpreter layer and the C layer, combined with a library well-evolved
> for everyday problem sizes, so the traditional asymptotic approach to
> algorithm selection often doesn't give the best practical choice.
>
> I don't feel like looking up what the tutorial says about pop(0), but if
> it just warns against it without qualification, it should probably
> be updated.

Here it is:

http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

My opinion is that the warning should be either removed or qualified,
but it is probably fine as written.

'''
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).
'''

The qualifications would be that deque lacks some features that list
has, and that the shift-by-one operation is actually a call to memmove
() and may not apply to all implementations.