二进制堆的有效实现

Question

我正在寻找有关如何有效实现二进制堆的信息.我觉得应该有一篇关于有效实现堆的好文章,但我还没找到.事实上,我已经无法找到任何有关超出基础知识的有效实现的资源,例如将堆存储在数组中.我正在寻找制作快速二进制堆的技术,超出我在下面描述的那些.

我已经编写了一个比Microsoft Visual C++和GCC的std :: priority_queue或使用std :: make_heap,std :: push_heap和std :: pop_heap更快的C++实现.以下是我在实现中已经涵盖的技术.我自己只想出了最后两个,尽管我怀疑这些是新想法:

(编辑:添加了关于内存优化的部分)

从1开始索引
查看维基百科的二进制堆实现说明.如果堆的根位于索引0处,则索引n处的节点的父,左子和右子的公式分别为(n-1)/ 2,2n + 1和2n + 2.如果使用基于1的数组,则公式变为更简单的n/2,2n和2n + 1.因此,使用基于1的数组时,父项和左子项更有效.如果p指向基于0的数组并且q = p-1,那么我们可以将p [0]作为q [1]来访问,因此使用基于1的数组没有开销.

在使用leaf替换之前,将pop/remove移动元素设置到堆的底部
经常通过将最顶部元素替换为最左边的底部叶子然后将其向下移动直到堆属性恢复来描述.这需要我们经历的每个级别的2次比较,并且由于我们将叶子移动到堆的顶部,因此我们可能会在堆中走得很远.所以我们应该期望比较少于2 log n.

相反,我们可以在顶部元素所在的堆中留一个洞.然后我们通过迭代地移动较大的孩子来将那个洞向下移动.这需要我们经过的每个级别只有1个比较.通过这种方式,洞将成为一片叶子.此时,我们可以将最右下方的叶子移动到孔的位置,并将该值向上移动,直到堆属性恢复为止.由于我们移动的值是一片叶子,我们不希望它在树上移动很远.所以我们应该期待比log n更多的比较,这比以前更好.

支持replace-top
假设您要删除max元素并插入新元素.然后,您可以执行上述任何一个删除/弹出实现,但不是移动最右侧的底部叶子,而是使用您希望插入/推送的新值.(当大多数操作属于这种类型时,我发现锦标赛树比堆更好,但是堆更好一点.)

使sizeof(T)的幂为2
父,子和子子公式适用于索引,并且不能使它们直接在指针值上工作.所以我们将使用索引,这意味着从索引i中查找数组p中的值p [i].如果p是T*且i是整数,那么

&(p[i]) == static_cast<char*>(p) + sizeof(T) * i

并且编译器必须执行此计算以获得p [i].sizeof(T)是编译时常量,如果sizeof(T)是2的幂,则可以更有效地进行乘法.通过添加8个填充字节以将sizeof(T)从24增加到32,我的实现变得更快.降低缓存效率可能意味着这对于足够大的数据集来说并不是一个胜利.

预乘法索引
我的数据集性能提升了23%.除了查找父级,左子级和右子级之外,我们对索引执行的唯一操作是在数组中查找索引.因此,如果我们跟踪j = sizeof(T)*i而不是索引i,那么我们可以进行查找p [i]而不需要在评估p [i]时隐含的乘法,因为

&(p[i]) == static_cast<char*>(p) + sizeof(T) * i == static_cast<char*>(p) + j

然后,j值的左子和右子公式分别变为2*j和2*j + sizeof(T).父公式有点棘手,除了将j值转换为i值之外,我还没有找到方法做到这一点,如下所示:

parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T)

如果sizeof(T)是2的幂,那么这将编译为2个移位.这比使用索引i的普通父亲多1次操作.然而,我们然后在查找上保存1个操作.因此,净效应是找到父母用这种方式花费相同的时间,而左子和右子的查找变得更快.

内存优化

TokenMacGuy和templatetypedef的答案指出了基于内存的优化,可以减少缓存未命中.对于非常大的数据集或不常使用的优先级队列,可以通过OS将队列的一部分交换到磁盘.在这种情况下,为了最佳地使用缓存而增加大量开销是值得的,因为从磁盘进行交换非常慢.我的数据很容易适应内存并且可以连续使用,因此队列的任何部分都不会被交换到磁盘.我怀疑大多数优先级队列的使用都是这种情况.

还有其他优先级队列旨在更好地利用CPU缓存.例如,4堆应该具有更少的缓存未命中,并且额外开销的数量不是那么多.LaMarca和Ladner在1996年报告说,他们从一致的4堆中获得了75%的性能提升.但是,Hendriks在2010年报告说:

还测试了LaMarca和Ladner [17]提出的改进数据局部性和减少缓存未命中的隐式堆的改进.我们实现了一个四向堆,对于非常偏斜的输入数据,它确实显示出比双向堆稍微更好的一致性,但仅适用于非常大的队列大小.分层堆可以更好地处理非常大的队列大小.

问题
是否有更多的技术？

Answer 1

关于该主题的一篇有趣的论文/文章考虑了缓存/分页对堆的整体布局的行为; 这个想法是,与数据结构的实现几乎任何其他部分相比,支付缓存未命中或页面的成本要高得多.本文讨论了解决此问题的堆布局.

Poul-Henning Kamp,你做错了