155

你们有没有人实现过Fibonacci-Heap？几年前我就这样做了，但它比使用基于数组的 BinHeaps 慢了几个数量级。

那时，我认为这是一个宝贵的教训，说明研究并不总是像它声称的那样好。然而，许多研究论文声称他们的算法的运行时间基于使用斐波那契堆。

你有没有设法产生一个有效的实施？或者您是否使用过大到斐波那契堆效率更高的数据集？如果是这样，一些细节将不胜感激。

4

4 回答 4

140

Boost C++ 库在boost/pending/fibonacci_heap.hpp. 该文件显然已经存在pending/多年，根据我的预测将永远不会被接受。此外，该实现中存在错误，这些错误已由我的熟人和全能酷家伙 Aaron Windsor 修复。不幸的是，我可以在网上找到的该文件的大多数版本（以及 Ubuntu 的 libboost-dev 包中的那个）仍然存在错误。我不得不从 Subversion 存储库中提取一个干净的版本。

自1.49版以来， Boost C++ 库添加了许多新的堆结构，包括斐波那契堆。

我能够针对 dijkstra_shortest_paths.hpp 的修改版本编译dijkstra_heap_performance.cpp以比较斐波那契堆和二进制堆。（在 行中，更改为。）我首先忘记使用优化进行编译，在这种情况下，斐波那契堆和二进制堆的性能大致相同，而斐波那契堆的性能通常微不足道。在我用非常强大的优化编译后，二进制堆得到了巨大的提升。在我的测试中，斐波那契堆仅在图形非常大且密集时才优于二进制堆，例如：typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueuerelaxedfibonacci

Generating graph...10000 vertices, 20000000 edges.
Running Dijkstra's with binary heap...1.46 seconds.
Running Dijkstra's with Fibonacci heap...1.31 seconds.
Speedup = 1.1145.

据我了解，这涉及到斐波那契堆和二进制堆之间的根本区别。两种数据结构之间唯一真正的理论区别是斐波那契堆在（摊销的）恒定时间内支持递减键。另一方面，二叉堆从它们作为数组的实现中获得了很大的性能。使用显式指针结构意味着斐波那契堆会遭受巨大的性能打击。

因此，要在实践中从斐波那契堆中受益，您必须在减少键非常频繁的应用程序中使用它们。就 Dijkstra 而言，这意味着底层图是密集的。一些应用程序可能本质上是减少键强度；我想尝试Nagomochi-Ibaraki 最小切割算法，因为它显然会生成很多 reduce_keys，但要让时序比较工作起来太费劲了。

警告：我可能做错了什么。您可能希望尝试自己重现这些结果。

理论说明：在 reduction_key 上改进的斐波那契堆性能对于理论应用很重要，例如 Dijkstra 的运行时。斐波那契堆在插入和合并方面也优于二叉堆（斐波那契堆的摊销常数时间）。插入本质上是无关紧要的，因为它不会影响 Dijkstra 的运行时，并且修改二进制堆以在摊销的常数时间内也具有插入是相当容易的。在恒定时间内合并非常棒，但与此应用程序无关。

个人笔记：我和我的一个朋友曾经写过一篇论文，解释了一个新的优先级队列，它试图在没有复杂性的情况下复制斐波那契堆的（理论）运行时间。这篇论文从未发表过，但我的合著者确实实现了二进制堆、斐波那契堆和我们自己的优先级队列来比较数据结构。实验结果的图表表明，斐波那契堆在总比较方面略胜二叉堆，这表明斐波那契堆在比较成本超过开销的情况下表现更好。不幸的是，我没有可用的代码，并且可能在您的情况下比较便宜，所以这些评论是相关的，但不直接适用。

顺便说一句，我强烈建议尝试将斐波那契堆的运行时间与您自己的数据结构相匹配。我发现我只是自己重新发明了斐波那契堆。之前我认为斐波那契堆的所有复杂性都是一些随机的想法，但后来我意识到它们都是自然而然的。

于 2009-02-03T18:02:09.227 回答
34

早在 1993 年，Knuth 就在他的著作Stanford Graphbase中比较了斐波那契堆和二叉堆的最小生成树。他发现斐波那契在他正在测试的图形大小下比二叉堆慢 30% 到 60%，不同密度的 128 个顶点。

源代码位于 MILES_SPAN 部分中 的C（或者更确切地说是 CWEB，它是 C、数学和 TeX 的交叉）中。

于 2009-04-19T04:46:04.937 回答
1

免责声明

我知道结果非常相似，并且“看起来运行时间完全由堆以外的东西控制”（@Alpedar）。但我在代码中找不到任何证据。它的代码是开放的，所以如果你能找到任何可能影响测试结果的东西，请告诉我。

也许我做错了什么，但我写了一个测试，基于A.Rex anwser 比较：

  • 斐波那契堆
  • D-Ary 堆 (4)
  • 二叉堆
  • 松弛堆

所有堆的执行时间（仅适用于完整图）非常接近。测试是针对具有 1000、2000、3000、4000、5000、6000、7000 和 8000 个顶点的完整图进行的。对于每个测试，生成 50 个随机图，输出是每个堆的平均时间：

对输出感到抱歉，它不是很冗长，因为我需要它来从文本文件构建一些图表。

以下是结果（以秒为单位）：

堆结果表

于 2012-11-11T21:19:05.963 回答
0

我还用斐波那契堆做了一个小实验。这是详细信息的链接：Experimenting-with-dijkstras-algorithm。我刚刚搜索了术语“Fibonacci heap java”，并尝试了一些现有的 Fibonacci heap 的开源实现。似乎其中一些有一些性能问题，但也有一些相当不错。至少，它们在我的测试中击败了幼稚的二进制堆 PQ 性能。也许他们可以帮助实施有效的。

于 2015-02-15T18:50:34.243 回答