[Python-Dev] Re: collections module

Terry Reedy tjreedy at udel.edu
Sun Jan 11 13:28:57 EST 2004

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
> ask for more room, overallocating by a small percentage of the current
> size.  If there's free room "at the left end", though, it may or may not
> more efficient to memmove the guts left.  Those are important details
> 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

More information about the Python-Dev mailing list