配对堆vs std :: priority_queue

Question

我正在尝试从此处获取的配对堆的C ++实现：http : //home.fnal.gov/~stoughto/build/graphviz-2.22.2/lib/vpsc/pairingheap/PairingHeap.h http ：//home.fnal.gov/~stoughto/build/graphviz-2.22.2/lib/vpsc/pairingheap/PairingHeap.cpp

我将PairingHeap与std :: priority_queue进行了比较，结果如下：

gcc 4.7 -O3，核心i7 2.4Ghz rdstc指令来测量周期

-------------------------------------------------------------------------------

for 100.000 elements:
o std::priority_queue<int>
    - insert:           9,800,415 cycles
    - extract:         29,712,818 cycles
    - total:           39,513,233 cycles       [0.031secs]
o PairingHeap<int>
    - insert:          34,381,467 cycles
    - extract:        259,986,113 cycles
    - total:          294,367,580 cycles       [0.125secs]


-------------------------------------------------------------------------------


for 1.000.000 elements:
o std::priority_queue<int>
    - insert:         95,954,533 cycles
    - extract:       518,546,747 cycles
    - total:         614,501,280 cycles       [0.296secs]
o PairingHeap<int>
    - insert:        344,453,782 cycles
    - extract:     3,856,344,199 cycles
    - total:       4,200,797,981 cycles       [1.593secs]

-------------------------------------------------------------------------------


for 10.000.000 elements:
o std::priority_queue<int>
    - insert:        999,836,450 cycles
    - extract:    10,634,407,049 cycles
    - total:      11,634,243,499 cycles       [4.390secs]
o PairingHeap<int>
    - insert:      3,441,903,781 cycles
    - extract:    61,166,421,272 cycles
    - total:      64,608,325,053 cycles       [24.187secs]

---

Pairing堆应该比std :: priority_queue更快，因为它应该具有渐近地更快的操作，但是在这里，Pairing堆非常慢。我认为这是因为std :: priority_queue在幕后使用了一个向量，这与配对堆一样，它比为每个整数分配节点更加缓存友好。

因此，我的问题是：渐近地更好的数据结构是否能够（在很大程度上）被较差的数据结构所击败，仅因为它们对缓存更友好？当默认的std :: priority_queue可以大大快于它时，是否真的值得在更复杂的数据结构（如配对堆）中花费很多时间？

我只是没有考虑过我使用的Pairing堆的实现只是胡扯，但事实并非如此，因为我尝试过的其他实现甚至更糟！有什么想法吗？

Answer 1

因此，我的问题是：渐近地更好的数据结构是否能够（在很大程度上）被较差的数据结构所击败，仅因为它们对缓存更友好？

是的，这种情况一直在发生。除了缓存友好性之外，还有其他原因（恒定因素）。像同一个单词的其他用法一样，此处的渐近是指某种东西（通常是问题的大小）达到无穷大。A渐近地优于B只是说它最终会更好，而不是对于某些给定值它会更好（甚至相等）。请注意，对于较大的数据集，该比率确实有所提高，但这还不够。

请注意，即使是二进制堆也不太适合某些较大的数据集（例如您的数据集）进行高速缓存。节点的子代和父代可能位于完全不同的页面上，因此您只能从缓存中获取最后几个级别的某些内容（或者如果访问的元素碰巧具有相似的路径，但这几乎是给定的）任何数据结构）。有一个称为B-heap的变体对此进行了改进，但我无法在其上找到很多细节（只有两个实现和关于RAM计算模型是如何引起误解的rant称）。

您必须进行概要分析才能确定，但​​是重复分配和重新分配可能会花费大量时间。池分配器（助推器，或在std :: vector之上手动滚动的分配器-允许用整数替换指针，这样可以节省一些空间）可以大大降低此成本。该实现似乎还对子级列表使用了链接列表，这可能会进一步损害缓存。阵列需要一些其他副本，但实际上可能会有所改进。

当默认的std :: priority_queue可以大大快于它时，是否真的值得在更复杂的数据结构（如配对堆）中花费很多时间？

足够大的数据集加上一些优化（例如，专门的分配器和聪明的节点布局），可能会有利于平衡。在任何情况下，该语句都有些自欺欺人：如果在预期的用例中，配对堆比二进制堆快，那么标准库很可能会使用配对堆！

另外，至少在纯函数语言中，配对堆的实现非常简单（尽管效率不高）。这对您和C ++可能没有多大用处，但这确实对“更复杂”的部分构成了挑战。