Python Cookbook 2Nd Edition Jun 1002005 [Electronic resources] نسخه متنی

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.

See Also

Library Reference and Python in a
Nutshell docs for built-ins list and
dict; Library Reference
docs on modules collections (Python 2.4 only) and
timeit. Python in a
Nutshell's chapter on optimization;
Donald Knuth, The Art Of Computer Programming
(exercise 14, section 2.2.1).