[Python-Dev] collections module

[Guido van Rossum]

> > My own ideal solution would be a subtle hack to the list
> > implementation to make pop(0) and insert(0, x) go a lot faster -- this
> > can be done by adding one or two extra fields to the list head and
> > allowing empty space at the front of the list as well as at the end.
> 
> I'm sure you know this, but just for sake of argument, how many extra
> fields?

You misunderstood -- the *fields* I was talking about are
counters or pointers that keep track of the overallocation, and 1 or
at most 2 is enough.

> A couple?  A few?  20?  30?  I'm not sure there really is a
> good hard and fast number.

You're talking about the amount of overallocation.  I would propose to
overallocate exactly as much as the list implementation currently does,
which is a very subtle scheme that overallocates more when the list
grows larger to maintain logarithmic behavior.

> I think it makes as much sense to
> preallocate the same number of entries to the front of a list, as to
> what is currently allocated to the back. At that point, you can
> guarantee O(1) {pop(0), pop(), append() and insert(0)} behavior, at the
> cost of slightly more memory.  Then it really wouldn't matter how people
> implement their stacks or queues (front, back, double-list), it would
> still be fast.

Right.

--Guido van Rossum (home page: http://www.python.org/~guido/)