python - 重新排列优先级队列的优先级(有效方式)

Question

我正在寻找一种更有效的方法来重新确定优先级队列中项目的优先级。我有一个基于 heapq 的(相当幼稚的)优先级队列实现。相关部分如下:

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)

这是一个简单的协程，用于在我的实际应用程序中演示重新确定优先级的特性。

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)

有测试

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

制作:

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

现在，我的问题是，在重新确定优先级队列的优先级时，是否存在任何数据结构可以避免调用 heapify(.)？我在这里愿意用内存换取速度，但应该可以用纯 Python 实现它(显然比我天真的实现要好得多)。

更新:
为了让您更多地了解具体情况，我们假设在初始(批量)推送后没有任何项目添加到队列中，然后队列中的每次提取(弹出)都会生成大致如下方案的重新优先化次数:

• 0* n，很少
• 0.05* n，通常
• n，很少

其中 n 是队列中当前项目的数量。因此，在任何一轮中，或多或少只有相对较少的项目需要重新排列优先级。所以我希望可以存在一种数据结构，它能够利用这种模式，因此优于在每一轮中执行强制性 heapify(.) 的成本(为了满足堆不变)。

更新 2:
到目前为止，heapify(.) 方法似乎确实非常有效(相对而言)。我能想到的所有替代方案都需要利用 heappush(.)，而且它似乎比我最初预期的要贵。 (无论如何，如果问题状态仍然如此，我不得不在 python 领域中寻找更好的解决方案)。

Answer 1

由于新的优先排序函数可能与之前的排序函数没有关系，因此您必须付出成本才能获得新的排序(并且至少需要 O(n) 才能找到新排序中的最小元素)。如果你有一个小的、固定数量的优先级函数并且经常在它们之间切换，那么你可以从为每个函数保持一个单独的堆中受益(尽管 heapq 不是这样，因为它不支持廉价地定位和删除以及对象从堆的中间)。