[Python-Dev] collections module (original) (raw)

Josiah Carlson jcarlson at uci.edu
Mon Jan 12 04:28:26 EST 2004

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.

More information about the Python-Dev mailing list