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 classtime (s)
list (Python’s default)2.26
Queue.deque0.42
mx.Queue.mxQueue0.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.

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

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax