[Python-Dev] FIFO data structure?
Tim Peters
tim.one@comcast.net
Sun, 20 Apr 2003 21:31:04 -0400
[Agthorr]
> I actually just wrote a modification to Queue that is O(1). There's
> no change to the interface, so it doesn't require adding a new data
> structure.
>
> I have the code here:
> http://www.cs.uoregon.edu/~agthorr/Queue.py
>
> The only changes are near the bottom of the file, beginning with the
> _init() function. My implementation uses Python lists, but it uses
> them in a smarter way than the existing Queue implementation.
>
> I'll submit a patch to SourceForge in a day or two.
I'm opposed to this. The purpose of Queue is to mediate communication among
threads, and a Queue.Queue rarely gets large because of its intended
applications. As other recent timing posts have shown, you simply can't
beat the list.append + list.pop(0) approach until a queue gets quite large
(relative to the intended purpose of a Queue.Queue).
If you have an unusual application for a Queue.Queue where it's actually
faster to do a circular-buffer gimmick (and don't believe that you do before
you time it), then, as the comments say, you're invited to *subclass*
Queue.Queue, and override as many of the six queue-implementation methods at
the bottom of the class as you believe will be helpful. It's not helpful to
change the *base* implementation of Queue.Queue for an O() advantage swamped
by increased overhead at typical queue sizes.