list.pop(0) vs. collections.dequeue

Steve Howell showell30 at
Sat Jan 23 17:46:18 CET 2010

On Jan 23, 6:40 am, Roy Smith <r... at> wrote:
> In article
> <a6531cf3-949d-4db9-9800-590302fd7... at>,
>  Steve Howell <showel... at> wrote:
> > This innocent program here literally moves about a million bytes of
> > memory around for no good reason:
> >     lst = []
> >     for i in range(2000):
> >         lst.append(i)
> >     while lst:
> >         print lst.pop(0)
> > Why?  Because list.pop(0) is implemented in O(N) instead of O(1).
> I think you're being a little pedantic here.  Yes, it is true that pop(0)
> is O(n), and that if you put an O(n) operation in a loop, you get O(n^2)
> run time.
> The problem is that while it is well-known that putting something that's
> O(n) in a loop gets you O(n^2), it's not well known that pop(0) for a
> Python list is O(n).  This is where you and I apparently start to differ in
> what we think about this.

The source for Python is open.  It pretty clearly shows that you move
N bytes when you pop from the top of the list.

Less clear is how linear the performance of memmove is.  My benchmarks
on the C program show that, at least on my computer, the results do
not seem to contradict the "roughly linear" assumption.

> You are arguing that this is a bug in the implementation of list.  While I
> suppose there's some validity to that argument, I disagree.  What I would
> argue (and have done so several times over the years, with little success)
> is that this is a bug in the documentation!
> I'm looking at  It shows all the operations of a
> list.  What it does not show is their cost.  For pop(), it has a note:
> "The pop() method is only supported by the list and array types. The
> optional argument i defaults to -1, so that by default the last item is
> removed and returned".
> There's nothing there that gives any hint that pop(0) is any more expensive
> than pop(-1).  That is "secret knowledge", which you only get by following
> the newsgroup discussions or looking at the implementation.  You shouldn't
> have to do either.  There's lots of possible ways list could be
> implemented.  Without knowing the details, I'm left to guess about
> important stuff like the cost of operations.
> Every one of these operations should list the cost.  Even if it's something
> as vague as, "While not guaranteed by the language spec, in the current
> implemenation of CPython ...".

I agree with that.

More information about the Python-list mailing list