1

我有一个调度算法，我比较优先级/任务元组列表的最小值和最大值，对它们进行一些更改优先级的操作，然后将它们重新插入列表并适当地更新列表。heapq 会是最好的数据结构吗？我将如何在不弹出的情况下进行初始比较（这基本上是确定优先级值是否相距足够远以需要进一步操作；如果不是，该函数将停止）？一旦进行了比较，我将如何将最大值与最小值一起使用，因为 heapq 是为仅弹出最小值而设计的？

4

2 回答 2

3

heapq只提供一个最小堆——也就是说，您可以min在 O(log N) 时间内弹出值，但不能弹出max值。

如果你想要一个类似于 的双面数据结构heapq，有几个基本选项。

首先，常规最小堆有什么问题？这不仅仅是 API；找到最大值需要O(n)时间而不是O(1)时间，因此弹出它需要O(n)而不是O(log n)，这是您要改进的关键。

一个简单的 hack 涉及保留两个堆，一个具有正常值，一个具有正常值的修饰，以便它们向后排序。这是伪代码中的实现：

def push(self, value):
    insert into both normal and reversed heaps
def minpop(self):
    check that the min value of normal hasn't reached the min value of reversed
    pop and return the min value of normal
def maxpop(self):
    check that the min value of reversed hasn't reached the min value of normal
    pop and return the min value of reversed

乍一看，似乎每个操作的最坏情况行为应该是 minheap 的两倍，但事实并非如此。特别是，最坏情况下的空间是曾经插入的元素数量，它可能远高于插入数量的两倍 - 删除的数量。（例如，如果您插入了 1000 个项目并删除了 100，则 900 >> 200。）

有许多用例不起作用，如果它在您的用例中不起作用，那应该是显而易见的。但是当它合适的时候，它是非常简单的。

如果不合适，您可以使用真正的最小-最大堆。这基本上只是将最小堆的normal和reversed版本交错到单个结构中，并且可以在上面的“检查”案例中轻松地做正确的事情（而不是留下值）。

但是，如果您想要双端优先级队列的对称性能，您实际上无法比平衡树或跳过列表做得更好。（嗯，不是出于一般目的。如果你有特定的行为特征，那可能不是真的。） AVL 树、红黑树和跳过列表的实现比 min-max 二叉堆要多得多。因此，在 PyPI 和 ActiveState 配方中搜索“平衡树”、“红黑树”、“AVL 树”、“skiplist”等，你会发现像bintreesand之类的东西skiplist，它们应该都可以工作。

但是，我建议blist. 它使用平衡树和数组的特殊混合，而不是经过充分研究的数据结构，乍一看可能会让您认为它不太可信。然而，我相信它比任何竞争模块都得到了更多的使用和实际测试，并且它也得到了相当大的优化。（当您处理A * log Bn + C性能时，更改A或C通常比更改具有更大的影响B。）它还有一个很好的界面——实际上，其中有一些。如果你使用blist.sortedlist，你可以做sl[0], sl[-1], sl.pop(0), sl.pop(-1), and sl.add(x), 几乎完全符合你的预期。

所以，你的代码看起来像这样（如果我理解你的英文描述）：

class MyQueue(object):
    def __init__(self):
        self.sl = blist.sortedlist(key=operator.itemgetter(0))
    def add(self, priority, task):
        self.sl.add((priority, task))
    def step(self):
        if self.sl[-1][0] - self.sl[0][0] < MyQueue.EPSILON:
            return
        minprio, mintask = self.sl.pop(0)
        maxprio, maxtask = self.sl.pop(-1)
        newminprio, newmaxprio = recalc_priorities(minprio, maxprio)
        self.add(newminprio, mintask)
        self.add(newmaxprio, maxtask)

这些方法中的任何一个的问题在于，偷看双方的最坏情况是O(log N)而不是O(1)。但是有一个简单的方法可以解决这个问题，如果这些是您需要的唯一操作：只需将这些值缓存起来：

class MyQueue(object):
    def __init__(self):
        self.sl = blist.sortedlist(key=operator.itemgetter(0))
        self.minprio, self.maxprio = None, None
    def add(self, priority, task):
        self.sl.add((priority, task))
        if prio < self.minprio: self.minprio = prio
        elif prio > self.maxprio: self.maxprio = prio
    def step(self):
        if self.maxprio - self.minprio < MyQueue.EPSILON:
            return
        minprio, mintask = self.sl.pop(0)
        maxprio, maxtask = self.sl.pop(-1)
        newminprio, newmaxprio = recalc_priorities(minprio, maxprio)
        self.add(newminprio, mintask)
        self.add(newmaxprio, maxtask)
        self.minprio, self.maxprio = sl[0][0], sl[-1][0]

这使得快速路径通过step O(1)而不是O(log n)，它使所有现有O(log n)操作保持不变O(log n)。

另请参阅Wikipedia以讨论其他类型的堆，这些堆可以替代此处可能相关的二进制堆。

最后一点，igorrs 的评论让我想起：

有多种不同的数据结构可以在这里获得相同的最坏情况算法复杂性。有时，避免任何事情O(n)就足够了，因此您应该使用最简单的实现并完成它。但有时（特别是对于许多操作但很小n，或非典型数据），常数因子、最佳情况等可能会产生巨大的差异。在这种情况下，正确的做法是构建多个实现并使用真实数据进行测试，看看什么是最快的。

于 2013-01-10T01:37:01.927 回答
1

鉴于您正在考虑堆，我可以假设您的期望（n元素总数）是：

  1. 及时找到最小的钥匙和最大的钥匙O(1)。
  2. 及时重新插入（使用更改的键）具有最小键的元素和具有最大键的元素O(log(n))。

这可以通过min-max heap来完成。不幸的是，我认为这在 Python 的标准库中不可用。

如果您放宽第一个要求，任何平衡树（例如红黑树）都可以解决问题，并O(log(n))为所有所需的操作留出时间。

Python 的标准库也不提供任何平衡树，因此您必须自己动手或寻找实现。

于 2013-01-10T01:15:00.490 回答