On Jan 23, 6:40 am, Roy Smith <r...@panix.com> wrote: > In article > <a6531cf3-949d-4db9-9800-590302fd7...@l11g2000yqb.googlegroups.com>, > Steve Howell <showel...@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. -- http://mail.python.org/mailman/listinfo/python-list
