在现代硬件上,最小-最大堆优于二进制堆

2020-09-03 03:15:21

堆是一种数据结构,我一直在使用,而其他人不知何故很少使用。(我曾经有一位同事告诉我,他知道有些代码是我的,因为它使用了堆)最近我编写的代码确实可以从使用堆中获益(就像大多数代码一样),但是我需要能够从两端弹出项。因此,我阅读了有关双端优先级队列以及如何实现它们的内容。这些都很少见,但最常见的实现是“间隔堆”,它可以快速解释,具有干净的代码,并且只比二进制堆稍微慢一点。但是还有一种叫做“最小-最大堆”的替代方法,它没有很漂亮的代码,但是它的依赖链更短,这在现代硬件上很重要。因此,它最终通常比二进制堆更快,即使它允许您从两端弹出。这意味着可能再也没有理由使用二进制堆了。

在我们进入细节之前,先快速刷新一下堆数据结构。它们通常用于优先级队列,但是当您的对象有顺序并且您一次只关心对象的一个子集时,它们通常更有用。假设您只关心前10个项目:堆允许您以较低的成本跟踪前10个项目,即使集合经常被修改。或者,您可能有一个滚动视图,可以滚动到一个很大的项目列表中:不需要对整个集合进行排序。仅对当前可见的选择进行排序,其余部分保留为两堆,以便在添加新项目或用户向上或向下滚动时以较低的成本更新视图。最后,本文提供了一个有趣的视觉用途,您必须快速从所有项目都在不断变化的集合中提取最小值。堆非常适合这样做,但是当您想要更改项时,需要一些额外的存储空间来查找它们在堆中的位置。

你可以把整个收藏品分类。但是排序的开销很大,如果集合经常更改,则排序后的集合的维护成本也很高。

您可以使用像红黑树或B树之类的树数据结构。如果您需要搜索项,它们是一个很好的选择,但除此之外,它们比堆慢。(因为它们必须对集合进行排序才能构建树)。

堆的特别之处在于它的空间开销为零。从字面上看,你只需储存物品。要将集合转换为堆,只需更改项的存储顺序。只要项的父项大于或等于其子项,您就拥有一个堆。索引i的父项位于索引(i-1)/2。索引i的两个子项位于(2*i)+1和(2*i)+2。

要将项添加到堆中,可以将其添加到末尾,然后检查它是否大于其父项。如果是,则插入操作违反了堆属性(父项必须大于或等于其子项),您必须在父项链上交换该项,直到一切正常为止。

要从堆中删除一个项目,您可以将其与最后一个项目交换,然后从后面弹出。现在,您将交换的项放在了错误的位置,因此您必须向上或向下滴入它,直到堆属性再次有效。(意思是,如果它大于新的父项,则将其交换,如果子项大于新项,则将其与较大的子项交换)。

最大的项目总是在索引0处,删除该项目比删除随机项目要便宜一些,因为您不必检查是否存在涓滴现象。

您还可以通过更改所有比较的顺序来构造最小堆。在这种情况下,最小的项将在索引0处。

这些算法都非常简单,如果您只实现了一次,则始终可以通过记住只需维护堆属性(父级大于或等于其子级)来重新派生它们。

高速缓存问题:这可能是简单的高速缓存未命中,也可能是不同的线程争夺高速缓存线。这是一大类性能问题。

Amdahl定律:您的代码中任何不并行运行的部分都倾向于主宰您的运行时。无论是在使用多线程时的大规模情况下,还是在相关性链破坏指令级并行性时的微观级情况下,这一点都是正确的。

分支预测错误:这比以前的问题要小得多,因为分支预测器非常棒,但是当它真的击中您时,它可能真的会伤害到您。

显然还有更多种类的性能问题,比如做太多的工作或使用错误的算法,但这些都是与硬件相关的最大问题,会对您造成伤害。

堆非常适合于第1类:因为您的空间开销为零,并且因为堆通常只是存储在平面数组中,所以您几乎没有高速缓存问题。当推送一大堆项目时,您将重复访问相同的缓存线,因此即使在大型堆上也会看到良好的性能。但是弹出是不可预测的,可能会在大堆上跳过内存,这可能会导致缓存未命中。但是堆仍然会比其他方法做得更好。

堆对于类别3也很好:同样,推送也很容易:(这将是一个主题)如果您将堆用于优先级队列,通常您将在后面推送,在前面弹出,因此可以正确地预测推送的所有比较结果为false。但是,即使您没有将堆用于优先级队列,并且如果您正在推送完全不可预测的项目,分支预测器也可以做得很好:第一次比较有50/50的机会,因为这取决于您是在上半部分还是下半部分。但下一次预测的准确率为75%,因为如果你在前25%的项目中,你只有两次涓涓细流,如果你在前12.5%的项目中,你只有三次涓滴上升。所以分支预测器只有在那之后才会变得更好。但弹出又变得更难了:你必须找到你的孩子中较大的一个,这将是完全不可预测的:左边的孩子和右边的孩子升迁的可能性相等。但是,您可以通过计算子索引为(2*i)+1+(Child 1<;Child 2)来使其无分支,这样会更快。

堆有问题的地方属于类别2:几乎每条指令都依赖于前一条指令。在堆推送和弹出中,CPU可以执行非常少的指令级并行。在这里,推送再一次稍微容易一些,因为您甚至在知道比较结果之前就可以计算下一个索引,但是弹出则比较困难:您需要知道左或右的子项是否更大才能知道下一个索引,并且您需要知道下一个索引才能开始下一个比较。任何事情都不可能同时发生。

因此,虽然堆通常非常快,但我们现在确实看到了堆的性能仍然可以改进的地方:我们需要对这些依赖链做些什么。但首先,我需要介绍实现双端优先级队列的典型方法:

堆有一个主题,即向堆中添加一些内容很容易,但将数据传回更难。推到后面很便宜,从上面弹出来更贵。插入随机物品很容易,删除随机物品要么需要线性搜索,要么需要额外的簿记才能知道物品在哪里。(有了额外的簿记功能,堆的内存开销不再为零,但仍然非常快)。

所以双端堆的日子不好过:它们想让更昂贵的操作POP变得更强大。不仅从堆中弹出顶部,而且从堆中弹出底部的项也应该很便宜。

维基百科关于这一主题的文章解释了如何使用“间隔堆”来实现这一点,“间隔堆”是一种非常优雅的数据结构:所有偶数索引的项形成一个最小堆,所有奇数索引的项形成一个最大堆。因此,您可以使用普通的堆操作,只是您必须强制执行一个额外的属性:min-heap中的项必须小于或等于max-heap中的匹配项。如果强制执行,则它们定义包含这两个项的所有后代的间隔。(这就是这个名字的由来)它真的很优雅,因为我们有一个比堆更强大的数据结构,但是我们仍然没有空间开销:我们只是对相同的项有不同的排列。它的执行完全符合您的预期:相当快,但比二进制堆稍慢,因为您必须执行正常的堆操作,并与另一个堆中的匹配项进行比较。下面是一个图表,其中我推送了N个项目,然后将时间除以N,得出平均推送时间:

所以间隔堆并不慢,但比二进制堆慢。如果您想知道为什么第一个图形变平,而第二个图形随着容器变大而不断增加:这两个操作的最坏情况下的性能都是O(Logn),所以您会认为它们会随着容器的大小而增长(请注意X轴上的对数刻度),但我在这里插入的是随机项,在插入排序项时,您只会遇到推送的最坏情况。当插入随机项时,您有50%的机会往上滴一次,25%的机会往上滴两次,12.5%的机会往上滴三次,等等。这意味着即使堆变大了,做更多工作的机会也会下降。所以曲线图变平了。

但我们来这里不是为了间歇堆。这只是每个人都在使用的数据结构。关于我一直承诺的最小-最大堆,这是怎么回事?

最小-最大堆的概念与间隔堆类似。只是最小-最大堆在每一层上都是交替的。第一、第三、第五等层是最小层,第二、第四、第六等层是最大层。最小层中的项目比它们的所有后代都小。最大层中的项目比它们的所有后代都大。以下是维基百科的一张图片:

这样看起来,不清楚间隔堆有什么好处。如果你看那篇维基百科文章中的伪代码,你会看到类似于“m:=i的最小的子孙的索引”。意思是取索引i,检查最多6个子代,看看哪一个是最小的,然后把它的索引赋给变量m,难怪没人用这个。

但是,由于我已经向您提供了堆在哪里变慢的信息,所以我想让您注意一件事:我们在这里经常可以跳过级别。如果我想要找到上图中根的最小后代8,我可以跳过下一级,只查看8的孙子。这意味着我只需要比较31、10、11和16。还记得依赖链是堆的性能问题吗?我们仍然有同样的问题,但现在链条只有一半长,因为我们只需要看一半的层。当然,我们每层都要做更多的工作,但无论如何我们都没有充分利用CPU的指令级并行性。

在包含N个项的二进制堆上,您最终得到了层,并且必须进行最多的比较。在间隔堆中,您在内部使用两个堆,因此每个堆最终都有层。因此,它只移除一层,以换取每层做更多的工作。在最小-最大堆中,我们可以跳过每隔一层,因此我们只需进行比较。这是一个很大的区别。例如,。这意味着如果这是唯一计算的数字,那么大小为1,000,000的最小-最大堆将与大小为1,000的二进制堆一样快。实际上,好处并不是很大,因为我们必须为最小-最大堆做更多的工作。现在是推送物品的时候了:

因此,在这两种情况下,最小-最大堆都比二进制堆稍微快一些。但请记住,我们在这里不是在比较两个等价的数据结构。最小-最大堆的弹出窗口上有两行:一行用于弹出最小项,另一行用于弹出最大项。因为最小-最大堆严格地比二进制堆更强大。所以它有更多的功能和更快的速度。你多久会遇到这样的事情?

(哦,是的,我还应该为间隔堆画两条线,一条线用于弹出min,另一条线用于弹出max,但是我想把重点放在min-max堆上)。

需要指出的一个细节是,弹出最大值比弹出最小值稍微快一些。至少对图表的某些部分是这样。我认为原因是Popping Max不得不关注较少的层。这很令人惊讶,因为我最初的预期正好相反:POPPING MAX最初需要做更多的工作,因为MAX项目有两个候选项目,但如果您将最初的比较设置为无分支,这最终会变得很便宜,所以少使用一个层的成本节约更有好处。

还有最后一个操作,make_heap()。这是一个O(N)循环,可以快速将任何集合转换为堆。它比反复调用push_heap()快得多。下面是最小-最大堆如何执行此操作:

在这里,最小-最大堆的速度与二进制堆几乎相同,主要是因为二进制堆已经非常快了。(如果您认为与您的体验相比,该二进制堆看起来非常快,那么您刚刚发现我在这里没有使用STL堆。Libstdc++有一个非常慢的make_heap实现,所以为了进行公平的比较,我不得不编写自己更快的make_heap。下面我将解释)早期y轴会跳来跳去,但这不是测量噪音:我选择了一个有点奇怪的y轴:调用make_heap的时间除以堆中的项目数。这使得它更容易与上面的PUSH_HEAP图进行比较,但是它会导致初始的跳变,因为最初的性能特征变化很大:在上面的Make_Heap图中,6个项目的时间为18纳秒,7个项目的时间为20纳秒,8个项目的时间为27纳秒。所以时间增加了,但是我显示的是平均数,第七件商品在这一点上比平均数便宜,所以平均数下降了。然后第八件商品更贵,因为它开始了一个新的层。

最小-最大堆是在1986年发明的,那么为什么没有人使用它呢?答案有点难找,因为没有人使用,导致文献匮乏。Google也很难搜索到最小-最大堆,因为Google只想向您展示有关普通二进制最大堆或普通二进制最小堆的文章。有人用C++实现了一个最小-最大堆,然后说在他实现之后,他发现一篇文章说间隔堆更快,所以他有点放弃了。我想他一定指的是Skov&;Olsen在2001年发表的论文“三个不同优先级Deques的比较分析”,这篇论文看起来很棒(甚至包括源代码),但是它发现最小-最大堆非常慢。他们的问题是,在可能的情况下,他们不会跳过层的把戏。但是,当一篇明显看起来质量很高的论文(我不是在开玩笑,实际上我认为它是一篇非常高质量的论文)告诉你它很慢时,你会相信它。我很幸运,除了维基百科的文章之外,我没有看到任何东西,而且我一直在考虑如何进一步提高堆的速度。因此,让我们讨论一下如何高效地实现最小-最大堆:

当你推一个东西的时候,你首先要检查你是在最小层还是在最大层。如果堆(包括新项)的长度为1,则位于最小层上。如果堆的长度是2或3,那么您就在最大层上。如果堆的长度是4、5、6或7,那么您就在最小层上,等等。检查这一点的最便宜的方法是使用最高有效位的位置。(至少我找不到更便宜的方法)意思是使用“位扫描反转”指令,然后检查最高有效位是否在偶数或奇数位置。看起来C++20最终添加了一种使用std::countl_Zero访问该指令的方法。不过我没有C++20,所以我不得不用老的平台特有的方法:微软提供_BitScanReverse64(Size),但在Linux上你必须这样做(63-__builtin_clzl(Size))。这样做的好处是我验证了我的代码实际上只是调用了“bsr”,其中标准C++版本有一个可能强制它执行分支的接口。(不过这一点不确定,所以如果您能够使用C++20,那么只需检查程序集是否有额外的分支)。

在推送中你要做的下一件事是检查你是否在错误的层中:如果新项目在最小层中,但它比最大层中的父项大,那么你必须交换这两个。(或者反过来,如果新项目从最大层开始),那么在那之后,你可以通过与你的祖父母进行比较来正常地涓涓细流,总是跳过其间的层。我的实现在这里。我在实现中使用了“goto”,因为我找不到一种方法来组织初始切换,而不必进行额外的比较。我相信有一种方法可以做到这一点,但这看起来并没有那么糟糕,因为这只是最初的切换。

和往常一样,流行音乐变得更难了。弹出最小项的开始与在二进制堆上弹出相同。要弹出最大项,我们需要找到前三个项中最大的一个。如果堆的长度为1,我们将立即完成,因为唯一的项是最大的项。如果堆的长度为2,我们也会立即完成,因为第一个项目在最小层中,所以最大的项目已经在数组的末尾。否则,最大项的索引为1+(heap[1]<;heap[2])。这意味着我们将比较结果转换为整数并将其加到1,以便这里没有分支。在我们找到最大的项之后,我们将其与数组的末尾互换,然后将过去位于末尾但现在位于错误位置的项向下滴入。

向下滴水时,我们希望尽可能跳过层层。幸运的是,除了最后一层之外,所有层都有可能做到这一点。当我们到达一个层,其中要么没有两个子代,要么没有四个孙子代,这意味着我们已经到达迭代的末尾。因此,对迭代结束的检查可以与允许我们跳过层的检查相同。这就给我们留下了两种情况需要处理:一种是常见的情况,当我们有四个孙子孙女,可以跳过一层;另一种情况是,我们可以有任意数量的子孙。

在一般情况下,我们必须找到四个孙子孙女中最小的一个。(在弹出最大项时,只需将我所有句子中的逻辑从“最小”改为“最大”即可。没有其他区别)四个孙子在数组中总是紧挨着彼此,所以这应该很快。要找到N个项目中最小的一个,需要(N-1)个比较,但重要的是我们如何进行比较。如果我们按顺序比较它们(就像std::min_element那样),那么我们就有一个从每次比较到下一次比较的依赖链,CPU一次只能做一个。我们可以像这样绘制依赖链:

如果我们将a与b进行比较,将c与d进行比较,然后将BOT的结果进行比较

进行比较的第二种方式还有另一个好处。因为四个孙子孙女都是紧挨着的,所以前两次比较可能是无分支的。第一个是(i+(heap[i+1]<;heap[i])),第二个是(i+2+(heap[i+3]<;heap[i+2]))。这意味着我们再次将比较结果转换为整数。

然后我的编译器甚至决定将最终的比较转换为有条件的移动,所以整个过程是无分支的。我认为这个分支完全不可预测,所以在这里使用cmov是个好主意。不幸的是,我认为没有办法强制编译器这样做,所以我很幸运。(一)。

.