list.pop(0) vs. collections.dequeue
roy at panix.com
Sat Jan 23 15:40:56 CET 2010
<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):
> 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)
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 ...".
More information about the Python-list