Recipe18.6.Implementing a FIFO Container

Recipe 18.6. Implementing a FIFO Container

Credit: Sébastien Keim, Alex Martelli, Raymond Hettinger, Jeremy Fincher, Danny Yoo, Josiah Carlson

Problem

You need a container that allows element insertion and removal, in which the first element inserted is also the first to be removed (i.e., a first-in first-out, FIFO, queue).

Solution

We can subclass list to implement a Pythonic version of an idea found in Knuth's Art of Computer Programming: the frontlist/backlist approach to building a FIFO out of two one-way linked lists. Here's how:

class Fifo(list):     def _ _init_ _(self):         self.back = [  ]         self.append = self.back.append     def pop(self):         if not self:             self.back.reverse( )             self[:] = self.back             del self.back[:]         return super(Fifo, self).pop( )

Discussion

Here is a usage example, protected by the usual guard so it runs only when the module executes as a main script rather than being imported:

if _ _name_ _ == '_ _main_ _':     a = Fifo( )     a.append(10)     a.append(20)     print a.pop( ),     a.append(5)     print a.pop( ),     print a.pop( ),     print # emits: 10 20 5

The key idea in class Fifo is to have an auxiliary backlist, self.back, to which incoming items get appended. Outgoing items get popped from the frontlist, self. Each time the frontlist is exhausted, it gets replenished with the reversed contents of the backlist, and the backlist is emptied. The reversing and copying are O(n), where n is the number of items appended since the "front list" was last empty, but these operations are performed only once every n times, so the amortized cost of each call to pop is a constantthat is, O(1).

A simpler way to build a FIFO in Python is no doubt to just use a standard list's append and pop(0) methodssomething like:

class FifoList(list):     def pop(self):         return super(FifoList, self).pop(0)

However, when using a list in this way, we need to keep in mind that pop(0) is O(n), where n is the current length of the list. O(1) performance can be ensured by building the FIFO in a slightly less intuitive way, on top of a dictionary:

class FifoDict(dict):     def _ _init_ _(self):         self.nextin = 0         self.nextout = 0     def append(self, data):         self.nextin += 1         self[self.nextin] = data     def pop(self):         self.nextout += 1         return dict.pop(self, self.nextout)

In Python 2.4, we also have collections.deque, a double-ended queue type that also ensures O(1) performance when used as a FIFO (using its append and popleft methods):

import collections class FifoDeque(collections.deque):     pop = collections.deque.popleft

To choose among different implementations of the same interface, such as the various Fifo... classes shown in this recipe, the best approach often is to measure their performance on artificial benchmark examples that provide a reasonable simulation of the expected load in your application. I ran some such measurements on a somewhat slow laptop, with Python 2.4, using the timeit module from the Python Standard Library. For a total of 6,000 appends and pops, with a maximum length of 3,000, class Fifo takes about 62 milliseconds, class FifoList about 78, FifoDict about 137, and FifoDeque about 30. Making the problem exactly ten times bigger, we see the advantages of O(1) behavior (exhibited by all of these classes except FifoList). Fifo takes 0.62 seconds, FifoList 3.8, FifoDict 1.4, and FifoDeque 0.29. Clearly, in Python 2.4, FifoDeque is fastest as well as simplest; if your code has to support Python 2.3, the Fifo class shown in this recipe's Solution is best.

Recipe18.6.Implementing a FIFO Container