An idea about the queue object:
If all the problem is about performance of pop(0) operations when the
queues grow a lot, why not implement a queue as a list of lists
(sublists), and all the magic will be to select an appropriate maximum
size for the sublists? Wouldn't this be actually a simulation of the
"extra space at the left side of the list" algorithm without touching
the C list implementation?
The very general idea:
class queue:
maximum_sublist_size = <some size after benchmarking>
def __init__(self):
self.superlist= [[]]
def put(self, item):
if len(self.superlist[-1]) >= self.maximum_sublist_size:
self.superlist.append([])
self.superlist[-1].append(item)
def get(self):
try:
sublist= self.superlist[0]
except IndexError:
raise QueueEmpty
try:
return sublist.pop(0)
except IndexError:
del self.superlist[0]
return self.get()
def size(self):
if self.superlist:
return self.maximum_sublist_size*(len(self.superlist)-1) \
+len(self.superlist[-1])
return 0
Another idea, for a single list solution where most of the times there
are lots of puts and then mostly lots of gets, perhaps this would be
fast:
An attribute of the instance stores the last operation (put or get)
If the current operation is not the same as the last, first reverse the
underlying list, then do append() or pop().
But that is not practical for very large queues.
Just some ideas.
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