[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.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4