Welcome, guest | Sign In | My Account | Store | Cart

Fifo mean "First In First Out". This is a kind of container, which only allow element insertion and removal and where the first element inserted is the first element removed.

Python, 23 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Fifo:
	def __init__(self):
		self.first=()		
	def append(self,data):
		node = [data,()]
		if self.first:
			self.last[1] = node			
		else:
			self.first = node
		self.last = node		
	def pop(self,n=-1):
		node = self.first
		self.first=node[1]
		return node[0]
		

a=Fifo()
a.append(10)
a.append(20)
print a.pop(0)
print a.pop(0)
a.append(5)
print a.pop(0)

I would thanks Raymond Hettinger who has suggested many great improvements both to the code and the discussion part. He has also provided an interesting alternate implementation in the comment part.

Python offer the pop(0) method of standard list to implement fifo. Unfortunately lists pop(0) operation need to perform a copy of the whole content of the list, this is quite inefficient if you need to store a large set of data.

Linked lists data structure offer a way to do pop operation in constant time. In fact I did the previous code after I read an academic paper that said that double linked lists was the 'natural' way to do this kind of container (by contrast from stacks). I would convince myself that it was possible to create Fifo with single linked lists.

I've done some dirty benchmarking. Here some numerical results, this show the relative time to push N data in a fifo and pop them (this operation was repeated 10 time for each N)

(N, Python-lists, Simple-linked-list-fifo) (50, 0.01, 0.02) (100, 0.02, 0.03) (500, 0.12, 0.15) (1000, 0.3, 0.31) (5000 3.55, 1.69) (10000, 12.19, 3.48)

This results show that in single-linked-list pop and append duration don't depend on the numbers of items contained in the container. Builtin list solution seems to become inefficient when your fifo have to store more than 1000 items.

Note: Paul Moore code (in comment n°1) is very interesting and efficient, unfortunately this is not a fifo implementation but a stack implementation.

9 comments

Paul Moore 22 years, 6 months ago  # | flag

You can do this more efficiently using nested tuples. If you steal Lisp's concept of "cons cells", you can achieve the same sort of result using nested tuples. Effectively, you implement the FIFO [1, 2, 3] (where 1 is the first item you'll pop) as (1, (2, (3, ()))).

Here's how:

class Fifo:
    def __init__(self):
        self.fifo = ()
    def append(self, data):
        self.fifo = (data, self.fifo)
    def pop(self, n):
        # Use tuple unpacking - popping an empty FIFO will
        # raise a ValueError, which is OK
        ret, self.fifo = self.fifo
        return ret

This is more compact than your list representation (tuples take up less space than lists) as well as being faster (tuple unpacking is a fast operation). Of course, it's also more obscure unless you're a Lisp hacker :-)

Raymond Hettinger 22 years, 3 months ago  # | flag

Tighter version. The author doesn't give himself enough credit. The built-in operations are faster only for short lists. His code runs in O(n) time which always wins in the longer run.

Here is a tighter version of the above code.

class Fifo:
        stored = [None]
        stored[0] = stored
        def append(self,data):  # to inside
                if len(self.stored) == 1:
                        return self.stored.append(data)
                self.stored[0] = self.stored = [self.stored[0], data]
        def pop(self):  # from outside
                whole = self.stored[0]
                self.stored[0] = whole[0]
                return whole[1]
Raymond Hettinger 22 years, 3 months ago  # | flag

Fastest FIFO. There was a news group discussion on the fastest FIFO implementation:

http://groups.google.com/groups?th=e79e99edc138cb02

Two O(n) approaches were found, the nested list approach shown above and a dictionary based approach from Alex Martelli. The dictionary approach beat nested list by about 30%. Space consumption was not measured -- Sébastien Keim's nested list approach may use less memory per queue element. Both approaches kept their O(n) characteristics in tests upto 300,000 queued elements. Here is the winning source code:

class Fifo:
    'Fastest implementation of FIFO queues'
    def __init__(self):
        self.nextin = 0
        self.nextout = 0
        self.data = {}
    def append(self, value):
        self.data[self.nextin] = value
        self.nextin += 1
    def pop(self, n=-1):
        value = self.data[self.nextout]
        del self.data[self.nextout]
        self.nextout += 1
        return value

Three slower approaches were also found. Each had performance that degraded to worse than O(n^2) for large test sets. The approaches were prepending to lists, appending to lists, and using array.array('i') which only works for storing integers. Not only were these appoaches slower, but they all took a major performance hit when there were more than 65,536 items in the queue (apparently having long integers as indices will more than double the lookup times).

For Python 2.2 users, variations were tried which sub-classed from built-in types. Revising Alex's code to inherit from a dictionary slowed his code by about 30%. Revising the list based approaches to inherit from built-in lists resulted in a 2% performance gain.

Bernhard Mulder 22 years, 2 months ago  # | flag

This is a stack, not a FIFO queue.

Bernhard Mulder 22 years, 2 months ago  # | flag

No exception raised. This is not quite equivalent to the original class: it does not raise an exception if there are more pops then appends.

Jeremy Fincher 21 years ago  # | flag

An even faster FIFO queue. Here's a version that's (by my tests) even faster than the dict method. It uses a design well-known in the functional programming world for making FIFO queues with singly linked lists.

With this method, keeping a FIFO queue requires two lists. The basic idea is that one list is the front of the queue and the other is the back. Enqueuing an element simply appends that element to the back list. Dequeuing an element pops from the end of the front list. If the front list is empty, then the front list is set to the reversed back list and the back list is reset to be empty. Thus the queue is amortized O(1) time, since one O(N) operation is required per N operations total.

Here's the code. Instead of maintaining two separate lists, it subclasses list and thus itself is the front list; the back list is kept as an attribute. It's slightly faster this way than it is keeping separate lists.

class ListSubclassFifo(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()
Sébastien Keim (author) 20 years, 11 months ago  # | flag

Very nice. I find your solution very pythonic. I have explored an implementation which should be a little faster since it avoid one copy:

class Fifo(object):
    __slots__ = ('data',)
    def __init__(self):
        self.data = [[], []]
    def append(self, value):
        self.data[1].append(value)
    def pop(self,n=-1):
        d = self.data
        if not d[0]:
            d.reverse()
            d[0].reverse()
        return d[0].pop()
Topher Cyll 16 years, 8 months ago  # | flag

Interesting. A quick benchmark shows that Jeremy's code is still faster for me (at least on Python 2.5.1). That said, avoiding the subclassing does make things more readable. Using named attributes for front and back also helps with clarity (I assume both you and Jeremy originally wrote versions that looked like this, but I'll post it for future readers).

Also, this probably varies by the benchmark, but my test shows using separate attributes to be slightly faster than the data array. I like the d.reverse() trick, though!

class Fifo(object):
    __slots__ = ('front', 'back')

    def __init__(self):
        self.front = []
        self.back = []

    def enqueue(self, value):
        self.back.append(value)

    def dequeue(self):
        front = self.front
        if not front:
            self.front, self.back = self.back, front
            front = self.front
            front.reverse()
        return front.pop()
Philippe Fremy 16 years, 7 months ago  # | flag

Fifo is now in python. Since python2.4 , a deque type has been added which can be used as fifo or queue.

See http://docs.python.org/lib/deque-objects.html

I haven't done any timing measurement but I trust python maintainers to have chosen an optimal solution.

Created by Sébastien Keim on Mon, 24 Sep 2001 (PSF)
Python recipes (4591)
Sébastien Keim's recipes (24)

Required Modules

  • (none specified)

Other Information and Tasks