efficient idiomatic queue?

[David Eppstein]

In article <mailman.1011223225.3777.python-list at python.org>,
 "Delaney, Timothy" <tdelaney at avaya.com> wrote:

> So, it looks like there is a definite speed penalty with the dict versions,
> although the majority of that is probably namespace lookup time (more
> operations). A C version would probably do quite well.

It's good to see actual data, but I don't think this is a fair comparison: 
your queues always have at most one item in them, so you never see how well 
these versions scale to different lengths. Try replacing

        for i in xrange(iterations):
                fifo.append(i)
                j = fifo.pop()

with

        for i in xrange(iterations):
                fifo.append(i)
        for i in xrange(iterations):
                j = fifo.pop()

When I did that, I got the following results, showing that among the 
Fifo's, the dictionary versions are very competitive with the method of 
indexing a list and replacing the list when the index gets too big 
(ListIndexFifo, code below the data), while the other list-based Fifos are 
not good for long queues. (List itself is just a stack, not a queue, of 
course.)

1000     list                 0.007062
1000     <type 'array.array'> 0.008669
1000     DictIntFifo          0.021960
1000     DictLongFifo         0.026667
1000     ListPrependFifo      0.024463
1000     ListAppendFifo       0.026615
1000     ListIndexFifo        0.021000

10000    list                 0.072249
10000    <type 'array.array'> 0.086427
10000    DictIntFifo          0.222813
10000    DictLongFifo         0.262345
10000    ListPrependFifo      0.839607
10000    ListAppendFifo       1.063594
10000    ListIndexFifo        0.202094

100000   list                 0.770646
100000   <type 'array.array'> 27.156242
100000   DictIntFifo          2.345710
100000   DictLongFifo         2.797171
100000   ListPrependFifo      76.949710
100000   ListAppendFifo       91.907281
100000   ListIndexFifo        2.047624

class ListIndexFifo:
        """"""
        
        def __init__(self):
                """"""
                self.data = []
                self.index = -1

        def append(self, value):
                self.data.append(value)

        def pop(self):
                self.index = self.index + 1
                if self.index > len(self.data) / 2:
                        self.data = self.data[self.index:]
                        self.index = 0
                return self.data[self.index]
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/