[Python-Dev] Re: FIFO data structure?
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-----