[Python-Dev] collections module

Christos Georgiou 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:

class queue:
    maximum_sublist_size = <some size after benchmarking>
    def __init__(self):
        self.superlist= [[]]
    def put(self, item):
        if len(self.superlist[-1]) >= self.maximum_sublist_size:
            self.superlist.append([])
        self.superlist[-1].append(item)
    def get(self):
        try:
            sublist= self.superlist[0]
        except IndexError:
            raise QueueEmpty
        try:
            return sublist.pop(0)
        except IndexError:
            del self.superlist[0]
            return self.get()
    def size(self):
        if self.superlist:
            return self.maximum_sublist_size*(len(self.superlist)-1) \
                +len(self.superlist[-1])
        return 0

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
fast:

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 mailing list