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.

2 Comments

  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.

    Comment by b — 9/9/2006 @ 9:28

  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

    Comment by b — 10/9/2006 @ 7:34

Sorry, the comment form is closed at this time.

« Blog's main page

23 queries. 0.372 seconds. Valid XHTML

Powered by WordPress

Subscribe to this blog in a reader or by Email.