[Python-Dev] Re: FIFO data structure? (original) (raw)

Jeremy Fincher fincher.8@osu.edu
Sun, 20 Apr 2003 17:53:15 -0400

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

On Sunday 20 April 2003 03:04 pm, David Eppstein wrote:

See <http://tinyurl.com/9x6d> for some tests indicating that using dict for fifo is a slow way to go.

That's definitely an inadequate test. First,if I read correctly, the test function doesn't test the plain list or array.array('i') as fifos, it tests them as a lifos (using simple .append(elt) and .pop()). Second, it never allows the fifo to have a size greater than 1, which completely negates the O(N) disadvantage of simple list-based implementations.

Change the test function's for loops to this:

for i in xrange(iterations): fifo.append(i) for i in xrange(iterations): j = fifo.pop()

And you'll have a much more accurate comparison of the relative speed of the queues, taking into account naive list implementations' O(N) dequeue.

I've written my own speed comparison using timeit.py. It's available at <http://www.cis.ohio-state.edu/~fincher/fifo_comparison.py>. Interestingly enough, the amortized-time 2-list approach is faster than all the other approaches for n elements somewhere between 100 and 1000. Here are my results with Python 2.2:

1 ListSubclassFifo 0.000233 1 DictSubclassFifo 0.000419 1 O1ListSubclassFifo 0.000350

10 ListSubclassFifo 0.001200 10 DictSubclassFifo 0.002814 10 O1ListSubclassFifo 0.001546

100 ListSubclassFifo 0.010613 100 DictSubclassFifo 0.028463 100 O1ListSubclassFifo 0.012658

1000 ListSubclassFifo 0.174211 1000 DictSubclassFifo 0.294973 1000 O1ListSubclassFifo 0.121407

10000 ListSubclassFifo 8.536460 10000 DictSubclassFifo 3.056266 10000 O1ListSubclassFifo 1.224752

(The O1ListSubclassFifo uses the standard (at least standard in functional programming :)) implementation technique of using two singly-linked lists, one for the front of the queue and another for the back of the queue.)

Jeremy

-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.1 (FreeBSD)

iD8DBQE+oxbLqkDiu+Bs+JIRAgdZAJ9xiAkwpjDylj8aiAqDFL8Jm5zNTgCfU7nU kMThW2eItzfr5pXjMf2P0Y8= =9Tu7 -----END PGP SIGNATURE-----