list.pop(0) vs. collections.dequeue
showell30 at yahoo.com
Tue Jan 26 06:13:00 CET 2010
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:
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
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.
More information about the Python-list