list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 25, 9:31 am, Steve Howell <showel... at yahoo.com> wrote:
> 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.

I should also point out that my telephone has gigabytes of memory.
It's a fairly expensive device, but I regularly carry multiple
gigabytes of memory around in my front pants pocket.

There are some valid reasons to reject a proposal to make deleting
elements off the top of the list be O(1).

Memory consumption is not one of them.

Even the most naive patch to make pop(0) and del lst[0] advance the
pointer would eventually reclaim memory once the list is garbage
collected.  Also, by allowing users to pop elements off the list
without a memmove, you encourage users to discard elements earlier in
the process, which means you can amortize the garbage collection for
the list elements themselves (i.e. less spiky), and do it earlier.