c++ - 配对堆与 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.4Ghzrdstc 测量周期的指令

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

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]

---

配对堆应该比 std::priority_queue 更快，因为它应该渐进地更快操作，但此处配对堆的速度非常较慢。我认为这是因为 std::priority_queue 在底层使用了一个 vector ，而这远不止于此缓存友好，而不是像配对堆那样为每个整数分配节点。

所以，我的问题是:渐近更好的数据结构(在很大程度上)会被更差的数据结构打败吗？仅仅因为它们对缓存更友好？在更复杂的数据结构(例如配对堆)上花费大量时间真的值得吗？默认的 std::priority_queue 在很大程度上可以比它更快？

我只是没有考虑到我使用的配对堆的实现只是废话，但似乎不是，因为我尝试过的其他实现更糟糕!想法？

Answer 1

So, my question is: can asymptotically better data structures be (largely) beaten by worse ones, just because they're much more cache-friendly?

是的，这种情况一直都在发生。除了缓存友好性之外，还有其他原因(常数因素)。与同一个词的其他用法一样，asymptotic 这里指的是趋于无穷 的事物(通常是问题规模)。 A 渐近优于 B 只是说它最终会更好，而不是说它会更好(甚至等于)某个给定值。请注意，对于较大的数据集，该比率确实有所改善，但还不够。

请注意，即使是二进制堆对于较大的数据集(例如您的数据集)也不太适合缓存。一个节点的子节点和父节点很可能在一个完全不同的页面上，所以你只能从最后几级的缓存中得到一些东西(或者如果你访问的元素恰好具有相似的路径，但这几乎是给定的)任何数据结构)。有一个名为 B-heap 的变体对此进行了改进，但我无法找到更多关于它的细节(只有两个实现和关于 RAM 计算模型如何误导的咆哮)。

您必须进行概要分析才能确定，但​​重复分配和取消分配可能会花费大量时间。池分配器(boost，或在 std::vector 之上的手动分配器——允许用整数替换指针，这可能会节省一些空间)可以大大降低此成本。该实现似乎还为子列表使用了一个链表，这可能对缓存造成更大的伤害。数组需要一些额外的拷贝，但在实践中可能会有所改进。

Is it really worth spending much time in a more complex data structure such as a Pairing heap, when a default std::priority_queue can largely be faster than it?

足够大的数据集加上一些优化(例如专门的分配器和巧妙的节点布局)可能会使天平向有利于它的方向倾斜。无论如何，这个说法有点弄巧成拙:如果对于预期的用例，配对堆比二进制堆更快，那么标准库很可能会使用配对堆!

此外，至少在纯函数式语言中，配对堆实现起来非常简单(尽管效率不高)。这对您和 C++ 可能没什么用处，但它对“更复杂”的部分提出了挑战。