[Python-Dev] collections module (original) (raw)

Josiah Carlson jcarlson at uci.edu
Fri Jan 9 01:07:30 EST 2004

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.

More information about the Python-Dev mailing list