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:
| Python class | time (s) |
| list (Python’s default) | 2.26 |
| Queue.deque | 0.42 |
| mx.Queue.mxQueue | 0.42 |
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
Weird, I got the following numbers:
>>> execfile(’de.py’)
8.79299998283
7.91100001335
9.47399997711
Lists are worse but not that much worse. They might have improved performance of lists, I’m running 2.4.3.
Comment by b — 9/9/2006 @ 9:28
I reran the tests with this code and differencese are indeed massive:
>>> execfile(’de2.py’)
“”
0.911000013351
“”
0.790999889374
“”
2.06299996376
Increasing iterations of each loop 10 times:
>>> execfile(’de2.py’)
“”
8.94199991226
“”
8.04200005531
“”
136.887000084
Comment by b — 10/9/2006 @ 7:34