[Python-Dev] Re: FIFO data structure?

[Jeremy Fincher]

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