[Python-Dev] collections module
tzot at sil-tec.gr
Sat Jan 10 11:44:48 EST 2004
An idea about the queue object:
If all the problem is about performance of pop(0) operations when the
queues grow a lot, why not implement a queue as a list of lists
(sublists), and all the magic will be to select an appropriate maximum
size for the sublists? Wouldn't this be actually a simulation of the
"extra space at the left side of the list" algorithm without touching
the C list implementation?
The very general idea:
maximum_sublist_size = <some size after benchmarking>
def put(self, item):
if len(self.superlist[-1]) >= self.maximum_sublist_size:
return self.maximum_sublist_size*(len(self.superlist)-1) \
Another idea, for a single list solution where most of the times there
are lots of puts and then mostly lots of gets, perhaps this would be
An attribute of the instance stores the last operation (put or get)
If the current operation is not the same as the last, first reverse the
underlying list, then do append() or pop().
But that is not practical for very large queues.
Just some ideas.
More information about the Python-Dev