list.pop(0) vs. collections.dequeue
showell30 at yahoo.com
Sat Jan 23 17:46:18 CET 2010
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.
More information about the Python-list