21st August 2006, 1 min read

Efficient FIFO/Queue data structure in Python

For the types of algorithms I implement these days, I need a fast FIFO-like data structure. Actually, I need a double-ended queue. Python has a list type, but it is somewhat a misnomer because its performance characterics are those of a vector. Recently, I found mxQueue which is a separate (non-free) download. Unfortunately, mxQueue has a non-Pythonic interface and, to make matters worse, I found out that Python comes by default with a really nice Queue of its own, called deque: you can find it in the new collection module. Thus, as a good scientist, I decided to test these 3 implementations. As it turns out, Queue.deque is a perfectly good FIFO data structure:

Through other tests, I was able to verify that both Queue.deque and mx.Queue.mxQueue have constant time deletion from both the head and the tail, unlike Python’s list.


from collections import deque
from time import time
from mx.Queue import *
def deleteFromHead(t):
for i in xrange(1000): t.append(1)
for i in xrange(1000000):
t.append(10)
del t[0]
def deleteFromHead2(t):
for i in xrange(1000): t.push(1)
for i in xrange(1000000):
t.push(10)
t.pop()
before=time()
t=Queue()
deleteFromHead2(t)
after=time()
print after-before
before=time()
t=deque()
deleteFromHead(t)
after=time()
print after-before
before=time()
t=[]
deleteFromHead(t)
after=time()
print after-before