On Jan 22, 7:09 pm, Roy Smith <r...@panix.com> wrote: > In article > <3ac173bd-4124-434d-b726-0b9baaeec...@36g2000yqu.googlegroups.com>, > Steve Howell <showel...@yahoo.com> wrote: > > > In my case I'm not really concerned about giving the memory back right > > away, it's more about keeping my code simple. Once I'm done with an > > element, I do just want to pop it off and keep all the simplicity of > > the lists, but I am just concerned enough speed that for a 1000 > > element list, I don't want to be doing 1000 memmoves for an average of > > 500 pointers, which effectively moves about a million bytes around for > > no reason. > > If you really want to pop all the elements from a long list, reverse the > list and pop them off the end. Popping every element off the beginning of > the list is O(n^2), as you pointed out. Reversing the list is O(n), and > each pop after that is O(1), so the overall complexity is O(n).
I really want to use list *normally* with all its perfectly good semantics and reasonable implementation, except for its blind spot with respect to popping the first element off the list. The whole reason I use CPython vs. C in the first place is that CPython programmers can generally program basic data structures better than I can. But list.pop(0) is the exception. And, with the possible exception of dicts, lists are the most fundamental data structures that Python has. I know Python's number one concern will never be speed, but if Python makes an O(1) operation into an unnecessarily O(N) operation for no good reasons other than "it's too complicated, " or it "adds another pointer to the structure," or "it adds another conditional check to list_ass_slice for operations that aren't popping off the top," I think it's reasonable to challenge the design philosophy. -- http://mail.python.org/mailman/listinfo/python-list