[Python-Dev] Re: FIFO data structure?

[Guido van Rossum]

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

I was just going to say that I was disappointed that there was
discussion about O(1) vs. O(N) but no actual performance
measurements.

But a comment on David's measurements: they assume the queue is empty.
What happens if the queue has an average of N elements, for various N?
At what point does the dict version overtake the list version?

Also ask yourself the following questions.  How much time are you
paying for the overhead of using a class vs. using a list directly?

--Guido van Rossum (home page: http://www.python.org/~guido/)