[Python-Dev] collections module

[Josiah Carlson]

> It needn't be especially fancy.  Here is what I had in mind:
> 
> n = 50
> class fifo(object):
> 
>     def __init__(self):
> 	  # block[0:n] is for data and block[n] is a link field
>         self.head = self.tail = [None] * (n+1)
>         self.headptr = self.tailptr = 0
...etc...

I've got a few of the standard FIFO implementations sitting here, and I
thought I would give them a run against each other.

Testing methods are as follows:  Initially create a FIFO of n elements.
Alternate between pushing and popping 2n elements from the FIFO.  Empty
the FIFO.

Timing each block, we get the following:
                 Create  Steady  Empty
n = 10000:
Fifo             0.047   0.328   0.141
Fifo_list        0.171   0.485   0.14
fast_list_fifo   0.0     0.297   0.157
doublelistfifo   0.0     0.359   0.172
fifo_raymond     0.109   0.422   0.172

n = 20000:
Fifo             0.093   0.657   0.297
Fifo_list        0.375   0.984   0.266
fast_list_fifo   0.0     0.594   0.312
doublelistfifo   0.0     0.719   0.344
fifo_raymond     0.203   0.859   0.329

n = 30000:
Fifo             0.157   0.984    0.437
Fifo_list        0.563   1.453    0.422
fast_list_fifo   0.0     0.89     0.469
doublelistfifo   0.016   1.078    0.515
fifo_raymond     0.297   1.297    0.5

n = 40000:
Fifo             0.203   1.328    0.594
Fifo_list        0.984   1.953    0.594
fast_list_fifo   0.015   1.188    0.625
doublelistfifo   0.0     1.437    0.687
fifo_raymond     0.438   1.734    0.656

Fifo: dictionary used as a fifo
fifo_list: [cur, [next, [...]]]
fast_list_fifo: push appends, pop increments a pointer, but never
removes element
doublelistfifo: self explanatory
fifo_raymond: the fifo described by raymond.


Initialization for Raymond's fifo can be ignored, it is merely inserting
objects one at a time (I am short on time this evening).  Interpret the
rest of the numbers as is reasonable, but consider that there is likely
a few percent margin of error on each number, unless something always
beats another.  I must be going to bed now, the wife is yelling at me.

 - Josiah