list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 24, 11:24 pm, Paul Rubin <no.em... at nospam.invalid> wrote:
> Steve Howell <showel... at yahoo.com> writes:
> > There is nothing wrong with deque, at least as far as I know, if the
> > data strucure actually applies to your use case.  It does not apply to
> > my use case.
>
> You haven't explained why deque doesn't apply to your use case.  Until a
> convincing explanation emerges, the sentiment you're creating seems to
> be "what's wrong with that guy and why doesn't he just use deque?".  So,
> why aren't you using deque?  If deque somehow isn't adequate for your
> use case, maybe it can be improved.
>

These are the reasons I am not using deque:

  1) I want to use native lists, so that downstream methods can use
them as lists.
  2) Lists are faster for accessing elements.
  3) I want to be able to insert elements into the middle of the list.
  4) I have no need for rotating elements.

I also have reasons for not using the other workarounds, such as
reversing the list.

> >> And when discussing performance in this context, additive constants
> >> do matter.
> > Wrong again.  Operations that mutate lists are already expensive
>
> I'm talking about memory consumption, which is part of Python's concept
> of performance.  You're proposing adding a word or two to every list,
> with insufficient justification presented so far.  Any such
> justification would have to include a clear and detailed explanation of
> why using deque is insufficient, so that would be a good place to start.
>

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.

That extra pointer should really be taken not just in context of the
list itself taking O(N) memory, but also the fact that all the
elements in the list are also consuming memory (until they get popped
off).  So adding the pointer has neglible cost.

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.  My consumer laptop has 3027908k of
memory.