Fifo as single linked lists (Python recipe) by Sébastien Keim

ActiveState Code (http://code.activestate.com/recipes/68436/)

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 :-)

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]

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.

This is a stack, not a FIFO queue.

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.

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()

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()

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()

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.