[Python-Dev] Re: FIFO data structure?

[Tim Peters]

[Jeremy Fincher, on
 <http://tinyurl.com/9x6d>
]
> That's definitely an inadequate test.  First,if I read correctly,
> the test function doesn't test the plain list or array.array('i') as
> fifos, it tests them as a lifos (using simple .append(elt) and .pop()).

That's right, alas.  Mr. Delaney was implementing stacks there, and just
calling them fifos.

> Second, it never allows the fifo to have a size greater than 1, which
> completely negates the O(N) disadvantage of simple list-based
> implementations.

Yup.

> ...
> <http://www.cis.ohio-state.edu/~fincher/fifo_comparison.py>.
> ...

> (The O1ListSubclassFifo uses the standard (at least standard in
> functional programming :)) implementation technique of using two
> singly-linked lists, one for the front of the queue and another for the
> back of the queue.)

The Dark Force has seduced you there:

class O1ListSubclassFifo(list):
    __slots__ = ('back',)
    def __init__(self):
        self.back = []
    def enqueue(self, elt):
        self.back.append(elt)
    def dequeue(self):
        if self:
            return self.pop()
        else:
            self.back.reverse()
            self[:] = self.back
            self.back = []
            return self.pop()

That is, you're subclassing merely to reuse implementation, not because you
want to claim that O1ListSubclassFifo is-a list.  It's better not to
subclass list, and use two lists via has-a instead, say self.front and
self.back.  Then the O(N)

            self[:] = self.back

can be replaced by the O(1) (for example)

            self.front = self.back

Of course, this is Python <wink>, so it may not actually be faster that way:
you save some C-speed list copies, but at the cost of more-expensive
Python-speed dereferencing ("self.pop" vs "self.front.pop").  But even if
it's slower, it's better not to pretend this flavor of FIFO is-a list (e.g.,
someone doing len(), pop(), append() on one of these instances is going to
get a bizarre result).