[Python-Dev] collections module

[Josiah Carlson]

> You miss one thing -- the Queue class exists *specifically* for thread
> communication.  It has very different semantics than I'd want for a
> generic queue.  E.g. with Queue, if you try to get something out of an
> empty queue, your thread *blocks*.  That's only appropriate for
> applications that expect this.  (Imagine the newbie questions to
> c.l.py. :-)

Agreed.

About the only question is what the new fifo queue should be called, and
wether it should be located in Queue (probably not, given the module
description), Raymond's proposed high speed data structure module, or
somewhere else.


> 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?  A couple?  A few?  20?  30?  I'm not sure there really is a
good hard and fast number.  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.


 - Josiah