[Python-Dev] collections module

[Josiah Carlson]

> The second type would be a high speed queue implemented using
> linked list blocks like we used for itertools.tee().  The 
> interface could be as simple as push, pop, and len.  Each
> operation ought to run about as fast a list assignment (meaning
> that it beats the heck out of the list.pop(0), list.append(data)
> version).

There's been a python-based FIFO that is O(1) on {push, pop} and uses
lists in the ASPN Python cookbook (adding len is easy):
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/210459
You'd probably be more interested in the variant I posted as a comment;
it is significantly faster when the output queue is exhausted.

Speaking of which...the Queue module REALLY should be re-done with the
Fifo above and a single conditional, the multiple mutexes in the current
Queue module are ugly as hell, and very difficult to understand.  If
desired, I'll write the new one.

> Guido wanted this to be discussed by a number of people.  While
> a rich set of collection classes have proven their worth in other
> contexts, it could be that more is not better for python.  One the
> language's elegances is the ability to do just about anything with
> just lists and dicts.  If you have too many mutable containers to 
> choose from, the choice of which to use becomes less obvious.  

The real trick is documenting them so that users can compare and
contrast the features of each, in order to choose properly.

> Likewise, queues are in a mental concept space distinct from dicts, 
> sets, and such.  My only worry with queues is differentiating
> them from Queue objects which have builtin synchronization for 
> use in threads.

It all really depends on the overhead of the underlying mutexes or
conditionals, which can be tested.

 - Josiah