list.pop(0) vs. collections.dequeue

[Steven D'Aprano]

On Fri, 22 Jan 2010 14:38:18 -0800, Steve Howell wrote:

> 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.


I don't understand what the actual problem you're trying to solve is. 
Despite your disclaimer about not being concerned about reclaiming the 
memory, it sounds like you're trying to micro-optimize memory usage. That 
is, you give me the impression that you prefer this:

while alist:
    x = alist.pop(0)
    process(x)

over this:

for x in alist:
    process(x)
# allow alist to be garbage collected when it goes out of scope


That strikes me as a pointlessly trivial optimization, even if deleting 
at the start of the list was efficient.

But whatever your reason, if you want to insert and delete efficiently 
from both ends of the sequence, use a deque. If you are only doing a 
small number of insertions/deletions at the beginning, and so don't care 
about inefficiency, use a list.

If you only want to insert/delete from one end, use a list. Instead of:

alist.insert(0, x)
alist.pop(0)

use:

alist.append(x)
alist.pop()

That's fast and efficient. In some cases it doesn't matter which order 
the list is, but if it does matter, the worst case is that you need to 
call alist.reverse() occasionally, which is quite fast. Or iterate over 
the list in reverse order, which is even faster.

So what am I missing?



-- 
Steven