weblogs : arhuaco : Queues in Python

I hadn't needed a queue in python before. Yesterday I needed one and I wanted to check the standard library for the implementation of a queue. I ran into a nice webpage: FIFO as single linked lists.

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.

Thus you should not implement a queue doing pop(0) to a list (unless you have just a few elements). This implementation has N^2 running time!:

#!/usr/bin/python

LIMIT = 10000000

f = list()
for i in xrange(LIMIT):
  f.append(i)
while len(f):
  f.pop(0)

The right way to do it nowadays is:

#!/usr/bin/python

from collections import deque

LIMIT = 10000000

q = deque()
for i in xrange(LIMIT):
  q.appendleft(i)
while len(q):
  q.pop()

In the webpage FIFO as single linked lists I found a very nice implementation and it runs almost as fast as the previous implementation reversing and copying only once, later I will show an example where the performance is much worse. Amortized algorithms are really pretty. What I liked of this example is that I hadn't seen a class inheriting from list before. This example also shows how you can implement a queue by using a single linked list (or a stack).

#!/usr/bin/python

# Code written by Jeremy Fincher

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

LIMIT = 10000000

f = ListSubclassFifo()
for i in xrange(LIMIT):
  f.enqueue(i)
while len(f):
  f.dequeue()

If you change the test, then deque is much faster than ListSubclassFifo. A hint:

f = ListSubclassFifo()
for i in xrange(LIMIT/5):
  for j in xrange(5):
    f.enqueue(i)
  for j in xrange(5):
    f.dequeue()

Conclusion: use deque.

Discussion (3) Loading...

• python(18)