I am looking for a more efficient way to override items in a priority queue. I have a (rather naive) heapq based priority queue implementation. The relevant parts are as follows:
from heapq import heapify, heappop class pq(object): def __init__(self, init= None): self.inner, self.item_f= [], {} if not None is init: self.inner= [[priority, item] for item, priority in enumerate(init)] heapify(self.inner) self.item_f= {pi[1]: pi for pi in self.inner} def top_one(self): if not len(self.inner): return None priority, item= heappop(self.inner) del self.item_f[item] return item, priority def re_prioritize(self, items, prioritizer= lambda x: x+ 1): for item in items: if not item in self.item_f: continue entry= self.item_f[item] entry[0]= prioritizer(entry[0]) heapify(self.inner)
And here is a simple collaborative procedure to just demonstrate the reorientation of features in my real application.
def fecther(priorities, prioritizer= lambda x: x+ 1): q= pq(priorities) for k in xrange(len(priorities)+ 1): items= (yield k, q.top_one()) if not None is items: q.re_prioritize(items, prioritizer)
When testing
if __name__ == '__main__': def gen_tst(n= 3): priorities= range(n) priorities.reverse() priorities= priorities+ range(n) def tst(): result, f= range(2* n), fecther(priorities) k, item_t= f.next() while not None is item_t: result[k]= item_t[0] k, item_t= f.send(range(item_t[0])) return result return tst
production:
In []: gen_tst()() Out[]: [2, 3, 4, 5, 1, 0] In []: t= gen_tst(123) In []: %timeit t() 10 loops, best of 3: 26 ms per loop
Now, to my question, is there any data structure that would avoid heapify(.) Calls when reorienting the priority queue? I am ready to trade memory for speed here, but it can be implemented in pure Python (obviously, with much better timings than my naive implementation).
Update :
So that you can learn more about a particular case, suppose that no elements are added to the queue after the initial (batch) clicks, and then each selection (pop) from the queue will generate the number of reconfigurations in approximately the same way as this scheme:
- 0 *
n , very rarely - 0.05 *
n , usually n , very rarely
where n is the current number of items in the queue. Thus, in any round, there is a more or less relative number of items to reorient. Therefore, I hope that there may be a data structure that could use this template and, therefore, exceed the cost of doing the required heapify(.) In each round (to satisfy the heap invariant).
Update 2 :
It still seems that the heapify(.) Approach is quite effective (relatively speaking). All the alternatives that I was able to figure out should use heappush(.) , And this seems more expensive than I originally expected. (In any case, if the state of the problem remains the same, I have to find the best solution from the python ).