java - Java 中的四元堆

Question

二叉堆通常用于例如优先队列。基本思想是不完全堆排序:保持数据排序“恰到好处”以快速取出顶部元素。

虽然四元堆在理论上比二元堆差，但它们也有一些好处。例如，它们将需要更少的堆重组操作(因为堆更浅)，同时显然需要在每个级别进行更多比较。但是(这可能是他们的主要好处？)他们可能有更好的 CPU 缓存局部性。所以一些消息来源说 3 元和 4 元堆在实践中优于 Fibonacci 和二元堆。它们应该不会更难实现，额外的案例只是一些额外的 if 案例。

有没有人为优先级队列试验过 4 元堆(和 3 元堆)并做过一些基准测试？在 Java 中，在对它们进行广泛的基准测试之前，您永远不知道它们是快还是慢。从我通过谷歌发现的所有内容来看，它可能非常依赖于语言和用例。一些消息来源说，他们发现 3-ary 最适合他们。

补充几点:

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

Answer 1

根据@ErichSchubert 的建议，我从ELKI 中获取了实现。并将它们修改为 4 元堆。获得正确的索引是一个小技巧，因为很多关于 4 元堆的出版物都使用 1 索引数组的公式？!？

以下是一些基于 ELKI 单元测试的早期基准测试结果。 200000 Double对象被预先分配(以避免过多地测量内存管理)和洗牌。

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

结果如下:

• 我的四进制 DoubleMinHeap : 10.371
• 埃尔基 DoubleMinHeap : 12.356
• 埃尔基 Heap<Double> : 37.458
• Java PriorityQueue<Double> : 45.875

所以 4 元堆(可能还没有 L1 缓存对齐!)和用于原始 double 的 ELKI 堆之间的区别不是太大。嗯，10%-20%左右；情况可能更糟。

原始堆之间的区别double s 和 Double 的堆对象要大得多。和 ELKI Heap确实比 Java PriorityQueue 快得多(但那个似乎有很大的差异)。不过，在 ELKI 中有一个轻微的“错误”——至少原始堆还没有使用批量加载代码。它就在那里，只是没有被使用，因为每个元素都会立即修复堆，而不是将其延迟到下一个poll()。 .我为我的实验修复了这个问题，主要是删除几行并添加一行 ensureValid();称呼。此外，我还没有 4 元对象堆，而且我还没有包括 ELKI 的 DoubleObjectMinHeap。然而......还有很多基准测试，我可能会尝试一下 caliper。