[Python-Dev] Re: collections module

[Terry Reedy]

On enhancing list object: queue vs. deque.

My general impression is that queues, while less common than stacks, are
used enough in enough different algorithms that adding one implementation
field to list headers so that pop(0) is an O(1) pointer move might be an
overall win for Python.  The current O(n) move everything every time
behavior is certainly a nuisance when queues are needed.

Deques, on the other hand, seem to be more a theoretical construct.
Algorithm books include them for completeness in describing possible list
disciplines, but generally ignore them thereafter.  I am hard put to
remember an algorithm that actually needs them.  They are certainly much
rarer than queues.  So I do not think trying to make prepends O(1) should
be considered further.

> Possibly -- nobody has given enough detail to say.  I'd be inclined to
> continue doing what we do now when an append runs out of room, which is
to
> ask for more room, overallocating by a small percentage of the current
list
> size.  If there's free room "at the left end", though, it may or may not
be
> more efficient to memmove the guts left.  Those are important details
that
> haven't gotten beyond the hand-wavy stage.

My possibly naive thought is that before reallocating, look at the ratio of
left free to total.  If memmove would result in as much, or perhaps nearly
as much, over-allocation as realloc, then just do that.  Certainly if the
ratio is small (like say .1), don't bother with memmove.  The exact cutoff
is a tuning matter.

Separate issue: for best performance, one would like to be able trade space
for time and preallocate a large enough block so that most append faults
result in a memmove back to the left.  Does the current builtin shrinkage
discipline would allow this.  Or does "q=[0]*1000; q[:]=[]" shrink the
space for q back to nearly nothing?  (One might also want to do same for
stack.  And yes, I remember:  'user tuning' is a 'bad idea'.  But....)

Terry J. Reedy