6

二进制堆通常用于例如优先级队列。基本思想是不完全堆排序：您保持数据排序“刚好够”以快速取出顶部元素。

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

有没有人为优先级队列尝试过 4 元堆（和 3 元）并进行了一些基准测试？在 Java 中，在对它们进行广泛的基准测试之前，您永远不知道它们是更快还是更慢。从我通过谷歌找到的所有信息来看，它可能完全依赖于语言和用例。一些消息来源说，他们发现 3-ary 对他们来说表现最好。

还有几点：

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

3 回答 3

2

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

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

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

结果如下：

  • 我的 4 进制DoubleMinHeap：10.371
  • DoubleMinHeap埃尔基：12.356
  • Heap<Double>埃尔基：37.458
  • 爪哇PriorityQueue<Double>：45.875

所以 4 元堆（可能还没有 L1 缓存对齐！）和用于原始双精度的 ELKI 堆之间的差异并不太大。嗯，10%-20%左右；这可能会更糟。

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

于 2013-01-04T01:00:34.113 回答
1

我自己没有对其进行基准测试，但有几点需要说明。

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

合理的情况是，尽管 n 元堆具有缓存局部性优势，但平均而言，二进制堆仍然是最佳解决方案。以下是一些可能会出现这种情况的略微手动的原因：

  • 对于大多数有趣的对象，比较成本可能比堆数据结构本身中的缓存位置效应更重要。n 元堆需要更多的比较。这本身可能足以超过堆本身的任何缓存局部性影响。
  • 如果您只是在适当的位置制作一堆数字（即由整数或双精度数组支持），那么我可以看到 chache 位置将是一个值得的好处。但事实并非如此：通常你会有一堆对象引用。对象引用本身的缓存局部性则不太有用，因为每次比较都需要遵循至少一个额外的引用来检查引用的对象及其字段。
  • 优先级堆的常见情况可能是相当小的堆。如果从性能的角度来看，你足够关心它，那么它可能都在 L1 缓存中。因此，无论如何，n 元堆都没有缓存位置优势。
  • 使用按位操作更容易处理二进制堆。当然这不是一个很大的优势，但每一点都有帮助....
  • 在其他条件相同的情况下，更简单的算法通常比更复杂的算法更快，这仅仅是因为恒定开销较低。您将获得诸如降低指令缓存使用率、更高的编译器能够找到智能优化的可能性等好处。这再次有利于二进制堆。

显然，当然，您需要对自己的数据进行自己的基准测试，然后才能得出关于哪个性能最好的真正结论（以及差异是否足以关心，我个人对此表示怀疑......）

编辑

此外，鉴于原始海报在下面的评论中提到的原始键，我确实使用一组可能感兴趣的原始键编写了优先级堆实现：

如果有人对运行测试感兴趣，这可能会相对容易地被破解为 n 元版本以进行基准测试。

于 2012-12-24T12:00:28.537 回答
1

我还没有对 4 进制堆进行基准测试。我目前正在尝试优化我们自己的堆实现，并且我也在尝试 4 元堆。你是对的：我们需要仔细进行基准测试，因为很容易被实现差异误导，热点优化会严重影响结果。另外，小堆可能会显示出与大堆不同的性能特征。

JavaPriorityQueue是一个非常简单的堆实现，但这意味着 Hotspot 会很好地对其进行优化。这一点也不坏：大多数人会实现更糟糕的堆。但是，例如，它确实不能进行有效的批量加载或批量添加（批量修复）。然而，在我的实验中，即使在重复插入的模拟中也很难始终如一地击败这种实现，除非你使用非常大的堆。此外，在许多情况下，替换堆中的顶部元素而不是poll()+是值得的add()；这不受 java 的PriorityQueue.

ELKI 中跨版本的一些性能提升（我已经看到您是 ELKI 用户）实际上是由于改进的堆实现。但这是一个起起落落的过程，很难预测哪种堆变化在实际工作负载中表现最好。我们实现的主要好处可能是具有“replaceTopElement”功能。您可以在此处检查代码：

SVN de.lmu.ifi.dbs.elki.utilities.heap 包

你会注意到我们在那里有一整套堆。它们针对不同的东西进行了优化，并且需要更多的重构。其中许多类实际上是从模板生成的，类似于GNU Trove所做的。原因是在管理盒装原语时，Java 的成本可能相当高，因此拥有原语版本确实是值得的。（是的，有计划将其拆分为一个单独的库。这不是高优先级。）

请注意，ELKI 故意不认可该java.util.CollectionsAPI。我们特别发现这个java.util.Iterator类非常昂贵，因此试图鼓励人们在整个 ELKI中使用C++ 风格的迭代器：

for (Iter iter = ids.iter(); iter.valid(); iter.advance()) {

java.util.Iterator通常通过API节省大量不必要的对象创建。另外，这些迭代器可以有多个（和原始的）值获取器；其中Iterator.next()是吸气剂和高级运算符的混合体。

好吧，我现在跑题太多了，回到 4 元堆的话题：

如果您打算尝试 4-ary heaps，我建议您从ObjectHeap那里的课程开始。

更新：我一直在进行微基准测试，但到目前为止的结果尚无定论。很难PriorityQueue持续击败。特别是批量加载和批量修复似乎并没有削减我的基准测试中的任何内容 - 可能它们导致 HotSpot 优化较少，或者在某些时候取消优化。通常，更简单的 Java 代码比复杂的逻辑更快。到目前为止，没有批量加载的 4 进制堆似乎效果最好。我还没有尝试过 5 进制。3 元堆与 4 元堆大致相等；并且 4-ary 的内存布局更好一些。我也在考虑尝试一种堆堆方法来安全地调整数组大小。但我预计增加的代码复杂性意味着它在实践中会运行得更慢。

于 2012-12-31T14:42:17.767 回答