Java中的4-ary堆

Question

二进制堆通常用于例如优先级队列.基本思想是不完整的堆排序:您将数据排序"足够"以快速取出顶部元素.

虽然理论上4-ary堆比二进制堆差,但它们也有一些好处.例如,它们将需要较少的堆重组操作(因为堆较浅),而在每个级别上显然需要更多的比较.但是(这可能是他们的主要好处？)他们可能有更好的CPU缓存局部性.因此,一些消息来源称3-ary和4-ary堆在实践中优于斐波那契和二进制堆.它们应该更难实现,其他情况只是一些额外的if情况.

有没有人尝试过4-ary堆(和3-ary)优先级队列并做了一些基准测试？在Java中,在广泛地对它们进行基准测试之前,你永远不知道它们是更快还是更慢.从我通过谷歌找到的所有内容来看,它可能是语言和用例依赖.一些消息来源说他们发现3-ary对他们来说效果最好.

还有一点:

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

Answer 1

根据 @ErichSchubert 的建议，我采用了ELKI的实现并将它们修改为 4 元堆。正确建立索引有点棘手，因为许多有关 4 元堆的出版物都使用 1 索引数组的公式？！？

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

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

结果如下：

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

因此，4 进制堆（可能还没有 L1 缓存对齐！）和原始双精度的 ELKI 堆之间的差异并不是太大。嗯，10%-20%左右；还可能会更糟糕的。

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