list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 23, 6:40 am, Roy Smith <r... at panix.com> wrote:
> In article
> <a6531cf3-949d-4db9-9800-590302fd7... at l11g2000yqb.googlegroups.com>,
>  Steve Howell <showel... at yahoo.com> 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 athttp://tinyurl.com/cdbwog.  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.