Java中的4元堆

Question

二进制堆通常用于例如优先级队列。基本思想是不完整的堆排序:将数据排序为“刚好足够”，以便快速提取顶级元素。

理论上，四进制堆比二进制堆更糟糕，但它们也有一些好处。例如，它们将需要更少的堆重构操作(因为堆要浅得多)，而显然需要在每个级别上进行更多的比较。但是(这可能是他们的主要利益？)它们可能具有更好的CPU缓存局部性。因此，一些消息来源说，在实践中，3进制和4进制堆的性能都优于斐波纳契堆和二进制堆。它们不应该更难实现，附加的案例只是一些额外的if案例。

有人试验过优先级队列的4进制堆(和3进制)并做了一些基准测试吗？在Java中，在对它们进行广泛的基准测试之前，您永远不知道它们是更快还是更慢。从我在Google上找到的所有信息来看，它可能是非常依赖于语言和用例的。一些消息人士说，他们发现了三份最适合他们的工作。

还有几点：

• PriorityQueue显然是一个二进制堆。但是这个类--例如，也缺乏批量加载和批量修复支持，或者说replaceTopElement --可能会产生巨大的影响。例如，批量加载是O(n)而不是O(n log n)；在添加更大的候选集合之后，批量修复本质上是相同的。可以用一个整数来跟踪堆中哪些部分无效。replaceTopElement比poll + add便宜得多(只需考虑投票是如何实现的:用最后一个元素替换顶部元素)
• 当然，对于复杂对象来说，堆是很流行的，但是优先级通常是一个双值整数。我们不是在比较字符串。通常它是一个(原始的)优先级。
• PQ通常只是用来得到顶部k个元素。例如，A*-搜索可以在达到目标时终止。所有不太好的路都会被丢弃。所以队列永远不会被完全清空。在4路堆中，有较少的顺序:大约一半多(一半多的父节点)。因此，它将对这些不需要的元素施加较少的秩序。(当然，如果您打算完全清空堆，这当然是不同的，例如，因为您正在进行堆排序。)

Answer 1

按照@ErichSchubert的建议，我已经将埃尔基的实现修改成了一个4进制的堆。这是一个小技巧，使索引正确，因为许多出版物围绕4元堆使用公式的1索引数组？！？

下面是一些基于ELKI单元测试的早期基准测试结果。预先分配了200000个Double对象(以避免过多地测量内存管理)并对其进行调整。

作为热身，对每个堆执行10次迭代，对100次迭代进行基准测试，但我可能会进一步放大。10-30秒并不是真正的基准测试，OTOH我也应该尝试测量标准偏差。在每次迭代中，将200000个元素添加到堆中，然后再对其中的一半进行轮询。是的，工作量也可以变得更加复杂。

以下是研究结果：

• 我的四位DoubleMinHeap：10.371
• ELKI DoubleMinHeap：12.356
• ELKI Heap<Double>：37.458
• Java PriorityQueue<Double>：45.875

因此，4进制堆之间的区别(可能还没有对齐L1缓存！)而原始双打的ELKI堆也不是太大。嗯，10%-20%左右；可能会更糟。

原始double的堆与Double对象的堆之间的差别要大得多。而且ELKI Heap确实比PriorityQueue快得多(但这个变化似乎很大)。但是ELKI中有一个轻微的"bug“--至少原始堆还没有使用大容量加载代码。它就在那里，只是没有被使用，因为每个元素都会立即修复堆，而不是推迟到下一个poll()。我通过删除几行代码并添加一个ensureValid();调用来修复这个问题。此外，我还没有一个4元对象堆，我还没有包括ELKI的DoubleObjectMinHeap .相当多的基准，我可能会给卡钳一个尝试。

Answer 2

不是自己设定基准，但有几点可以说明这一点是相关的。

首先，请注意，PriorityQueue的标准Java实现使用二进制堆：

• http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/PriorityQueue.java

很有道理的是，尽管n进制堆具有缓存局部性，但二进制堆仍然是平均情况下的最佳解决方案。以下是一些可能出现这种情况的轻微波动原因：

• 对于大多数有趣的对象，比较成本可能比堆数据结构本身中的缓存局部性影响要重要得多。N元堆需要更多的比较。这本身可能就足以超过堆本身中的任何缓存局部性。
• 如果您只是简单地将一个数字堆放在适当的位置(即，由一个in或加倍数组支持)，那么我可以看到chache位置将是一个值得的好处。但情况并非如此:通常，您将有一个对象引用的堆。对象引用本身的缓存局部性就不那么有用了，因为每次比较都需要遵循至少一个额外的引用来检查引用的对象及其字段。
• 优先级堆的公共案例可能是一个很小的堆。如果您从性能的角度对它有足够的关注，那么它可能都在L1缓存中。因此，无论如何，n进制堆没有缓存局部性的好处。
• 使用按位操作处理二进制堆更容易。当然，这不是什么大优势，但每一个小小的帮助.
• 更简单的算法通常比更复杂的算法更快，所有其他算法都是相等的，仅仅是因为较低的常量开销。您可以获得诸如较低的指令缓存使用率、编译器能够找到智能优化的可能性更高等好处。同样，这有利于二进制堆。

当然，当然，在真正得出结论之前，您需要对自己的数据进行自己的基准测试(如果差异足够，我个人对此表示怀疑……)

编辑

此外，考虑到下面的注释中提到的原始键，我确实使用了一个原语键数组编写了一个优先级堆实现：

• https://github.com/mikera/mikera/blob/master/src/main/java/mikera/util/RankedQueue.java

如果有人对运行测试感兴趣的话，这很可能会被黑客入侵到一个n元版本中，用于基准测试。