list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 22, 7:09 pm, Roy Smith <r... at panix.com> wrote:
> In article
> <3ac173bd-4124-434d-b726-0b9baaeec... at 36g2000yqu.googlegroups.com>,
>  Steve Howell <showel... at 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.