list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 22, 1:29 pm, Christian Heimes <li... at cheimes.de> wrote:
> Steve Howell wrote:
> > I disagree that Python code rarely pops elements off the top of a
> > list.  There are perfectly valid use cases for wanting a list over a
> > dequeue without having to pay O(N) for pop(0).  Maybe we are just
> > quibbling over the meaning of "rarely."
>
> I was speaking from my own point of view. I've written several tenths of
> thousands of lines of Python code in the last seven years, mostly
> related to data manipulation, web applications and operating system
> interaction but also GUI stuff and scientific code. I can't recall any
> performance critical or prominent code that modifies the head of a list
> a lot.
>

That maybe would be an argument for just striking the paragraph from
the tutorial.  If it's rare that people pop the head off the list in
code that is performance critical or prominent, why bother to even
mention it in the tutorial?

> Of course there a use cases where you may want to use list.pop(). Unless
> you need a FILO structure you can always replace a LILO with a FIFO --
> instead of list.insert(0, value) and list.pop(0) use list.append(value)
> and list.pop(). It's not possible to optimize a data structure for all
> use cases.
>
> > I am not proposing a linked list of pointers.  I am wondering about
> > something like this:
>
> > p = &p[1];
> > (and then reclaim p[0] as free memory, I already said I understood
> > that was the tricky bit)
>
> > The pointer arithmetic for accessing each element would still work in O
> > (1), right?
>
> You mean it's an impossible trick unless you come up with your own
> memory management system. Realloc(), the standard function to change the
> size of chunk of allocated memory in C, doesn't support your desired
> operation.
>

Impossible is a strong word.  You could be lazy about giving the
memory back, and just wait till the whole list is garbage collected.
I don't think there's anything in Python's contract that says memory
has to be freed the exact moment you stop using it, especially since
we're talking about doing an O(N) memmove just to free up one
pointer's worth of memory.

I know the Python programmer could simply iterate through the list
rather than popping off unused elements, but that just means that you
not only tie up the memory for the pointers just as long, but you also
prevent the objects themselves from being garbage collected.

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.

I suppose the solution is to either give up the sugar of lists, or try
to wrap something like deque or list-with-offset into a sequence.