c# - 需要高效稳定的 PriorityQueue 实现

Question

我为最初使用 Eric Lippert's PriorityQueue implementation 的棋盘游戏实现了 A-*使用 SortedDictionary，但性能对于我的电路板尺寸而言并不令人满意。

使用 PriorityQueue 的 MinHeap 实现使我在长对角线路径上获得 *2 加速(5-6 秒减少到 2-3 秒)；但后来我意识到它提供了一种不稳定的排序。对于这个应用程序，我需要一个稳定的排序。

是否有任何众所周知的 PriorityQueue 实现结合了 MinHeap 的效率，但提供了与 SortedDictionary 一样的稳定排序？

更新:来自以下评论的更多详细信息:

• 需要的 PriorityQueue 操作:Enqueue()、Dequeue() 和 Count;
• 在 A-* 的每次迭代中:IsEMpty 和 Dequeue() 各调用一次，Enqueue() 调用 6 次；

解决方案:

虽然复杂度SortedDictionary<uint,Queue<TValue>>和 MinListHeap<KeyValuePair<TPriority,TValue>>是相同的，维护插入顺序的额外代码复杂性似乎是一个恒定的时间惩罚。这可能不是确定的，但我一直在寻找现阶段改进阶段容易获得的成果。

此外，随着我​​对这个问题的更多思考，我意识到稳定性只需要在短路径上，而不是在长路径上；因此，可以根据从开始到目标的距离的初始启发式估计，在进入 FindPath() 时选择所需的 PriorityQueue 实现。

Answer 1

这应该是一条评论，但它太长了。所以这里是:

我无法按照您建议的链接找到优先级队列作为排序字典的实现，但谷歌搜索表明该优先级队列是使用二叉搜索树实现的。 如果是这种情况，那么这些似乎不是自平衡搜索树，因为我不明白用堆替换 BST 会带来 2 倍的改进。自平衡 BST 在 insert() 上为您提供有保证的 log(n) 性能和 find() . deque()也是如此(= removeMin() ):它也应该是一个保证 log(n):你向左走，直到没有剩下的 child 。

好的，所以我们对二叉搜索树 (BST) 的每个操作都有 log(n)。堆呢？那么，对于您正在查看的操作，它是相同的:removeMin() (= dequeue() ) 返回具有最高/最低键的节点(这是 O(1))，但随后将最后一个节点放在初始位置并通过递归地将其与其子节点进行比较来将其下沉。这需要在每个级别进行 2 次比较，并且通常涉及 log(n) 级别。所以 removeMin()是一个 O(log(n) ) 操作。怎么样insert() (= enqueue())？在这里，在通常的实现中，我们将新项目放在末尾，然后通过与它的 parent 进行比较来将其 float 。在通常情况下，这需要 0.5*log(n) 次操作，即 O(log(n))。这意味着 BST 和堆在 enqueue() 和 dequeue() 上都应该有 log(n) 性能。并且这两种数据结构在 isEmpty() 上都应该有 O(1) 的性能。 .

这个推理，如果正确，表明以下之一:

• BST 实现中的常数因子使 minHeap 优先级队列中的常数因子相形见绌
• 所使用的 BST 不是自平衡的。

人们可能还会认为 0.5*log(n) insert() 上的堆可能比 BST 更好 insert() , 但是，BST 插入实际上也通常是关于 0.5*log(n)实际上，我认为这不可能。常数因子是合理的:如果 minHeap 被实现为一个自动调整大小的数组(或者更好的是一个非调整大小的数组)，那么 minHeap 可能不需要在 enqueue 上分配额外的存储空间。 ，这是 BST 实现必须做的。

也有可能 BST 不是自平衡的。在这种情况下，在最坏的情况下，dequeue()或 enqueue()将花费 O(n) 时间，具体取决于添加项目的顺序。所以这将是值得关注的。

编辑 1:使常规 BST 实现稳定的方法是采用一种约定，如果我们插入具有相同键的节点，则新节点成为(比方说)同键节点。这样，具有相同键的第一个节点将被出列。对于自平衡 BST，这可能需要更多的工作，因为旋转可能会违反这个期望的不变量。在这种情况下，我想我会做的(考虑 red-black trees ，而不是 AVL trees )是在旋转两个节点 A 和 B 时，我会检查它们的 key 是否实际上相同，如果是，则切换节点数据同时维护节点结构。但是这个问题可能有更好的解决方案。

编辑 2 根据 this acticle ，SortedDictionary其实是基于红黑树的。这反过来又表明实现中存在错误(令人怀疑但并非闻所未闻)或恒定因素是罪魁祸首。