list.pop(0) vs. collections.dequeue

Paul Rubin at nospam.invalid
Mon Jan 25 22:00:02 CET 2010

Steve Howell <showell30 at> writes:
> These are the reasons I am not using deque:

Thanks for these.  Now we are getting somewhere.

>   1) I want to use native lists, so that downstream methods can use
> them as lists.

It sounds like that could be fixed by making the deque API a proper
superset of the list API.

>   2) Lists are faster for accessing elements.

It sounds like that could be fixed by optimizing deque somewhat.  Also,
have you profiled your application to show that accessing list elements
is actually using a significant fraction of its runtime and that it
would be slowed down noticably by deque?  If not, it's a red herring.

>   3) I want to be able to insert elements into the middle of the list.

I just checked, and was surprised to find that deque doesn't support
this.  I'd say go ahead and file a feature request to add it to deque.

>   4) I have no need for rotating elements.

That's unpersuasive since you're advocating adding a feature to list
that many others have no need for.  

> Adding a word or two to a list is an O(1) addition to a data structure
> that takes O(N) memory to begin with.

Yes, as mentioned, additive constants matter.

> Another way of looking at it is that you would need to have 250 or so
> lists in memory at the same time before the extra pointer was even
> costing you kilobytes of memory. 

I've often run applications with millions of lists, maybe tens of
millions.  Of course it would be 100's of millions if the machines were
big enough.

> My consumer laptop has 3027908k of memory.

I thought the idea of buying bigger machines was to solve bigger
problems, not to solve the same problems more wastefully.

More information about the Python-list mailing list