list.pop(0) vs. collections.dequeue

[Roy Smith]

In article 
<a6531cf3-949d-4db9-9800-590302fd7089 at l11g2000yqb.googlegroups.com>,
 Steve Howell <showell30 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.

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 http://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 ...".