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.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

2 thoughts on “Efficient FIFO/Queue data structure in Python”

  1. 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.

  2. 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

Leave a Reply to b Cancel reply

Your email address will not be published. The comment form expects plain text. If you need to format your text, you can use HTML elements such strong, blockquote, cite, code and em. For formatting code as HTML automatically, I recommend tohtml.com.

You may subscribe to this blog by email.