2

我正在使用 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 heap 应该比 std::priority_queue 更快，因为它应该具有渐近更快的操作，但在这里 Pairing heap非常慢。我认为这是因为 std::priority_queue 在底层使用了一个向量，这比为每个整数分配节点更友好，就像配对堆一样。

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

我只是没有考虑到我使用的 Pairing heap 的实现只是垃圾，但似乎不是，因为我尝试过的其他实现更糟糕！想法？

4

2 回答 2

5

所以，我的问题是：渐近更好的数据结构可以（很大程度上）被更差的数据结构击败，仅仅因为它们对缓存更友好吗？

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

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

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

当默认的 std::priority_queue 在很大程度上比它快时，是否真的值得在更复杂的数据结构（例如配对堆）上花费大量时间？

一个足够大的数据集加上一些优化（例如专门的分配器和聪明的节点布局）可能会使平衡向有利于它的方向倾斜。无论如何，这句话有点弄巧成拙：如果在预期的用例中配对堆比二叉堆快，那么标准库很可能会使用配对堆！

此外，至少在纯函数式语言中，配对堆的实现非常简单（尽管效率不高）。这对你和 C++ 可能没什么用，但它是一些东西并且挑战了“更复杂”的部分。

于 2013-07-04T12:01:53.927 回答
1

这里的一个主要问题是内存分配和缓存效率。

您可以尝试使用自定义operator new+operator delete为PairNode类实现一个固定大小的分配器，以减少分配开销（类似于“更有效的 C++”，第 10 项中的分配器）。此外，这种方法最终可能对缓存更加友好，因为元素更有可能具有参考位置。

我之前已经使用QuadEdgeDelaunay 三角测量的结构（存在类似问题）完成了此操作，并且速度增加超过 10-20 倍 IIRC。如果您需要使分配器线程安全，那么您将为此付出高昂的性能代价。

至于实际回答在一种情况下性能是否更好的问题，它不太可能是普遍的，逐案分析是最容易知道的方法（任何其他方法都会很复杂，因为不实施就无法预测实施的质量）。不仅如此，不同的处理器会有所不同，结果可能取决于您倾向于获得的数据。

于 2013-07-04T11:54:11.057 回答