有人真正高效地实现了斐波那契堆吗？

Question

有人真正高效地实现了斐波那契堆吗？

performancealgorithmlanguage-agnosticdata-structuresfibonacci-heap

160

你们当中有没有人实现过斐波那契堆？我几年前曾经实现过，但是它比使用基于数组的二叉堆慢了几个数量级。

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

你是否曾经成功实现过一个高效的斐波那契堆？或者是你处理的数据集太大了，所以斐波那契堆更高效？如果是这样，一些细节将会非常感激。

- mdm

26

你学过算法吗？这些算法专家总是把他们庞大的常数隐藏在大O符号后面！:) 实际上，在实践中，大多数时候，“n”这个东西甚至远远达不到“n0”！ - Mehrdad Afshari

我知道 - 现在。当我第一次得到《算法导论》的副本时，我就实现了它。此外，我并没有选择Tarjan作为发明无用数据结构的人，因为他的Splay树实际上非常酷。 - mdm

mdm：当然不是无用的，但就像插入排序在小数据集中击败快速排序一样，由于较小的常数，二叉堆可能会更有效。 - Mehrdad Afshari

1

实际上，我需要堆的程序是为了在VLSI芯片中寻找Steiner树进行路由，因此数据集并不小。但现在（除了简单的排序之类的东西），我总是会使用更简单的算法，直到它在数据集上“崩溃”。 - mdm

1

我的答案实际上是“是的”。（好吧，我在一篇论文上的合著者做了。）我现在没有代码，所以在实际回复之前我会获取更多信息。然而，从我们的图表来看，我注意到F堆比b堆少进行比较。您使用的是比较便宜的东西吗？ - A. Rex

你可能想看一下这篇论文，它对大量不同的堆进行了很好的比较：https://arxiv.org/pdf/1403.0252.pdf - saolof

5个回答

36

1993年，Knuth在他的书《Stanford Graphbase》中为最小生成树比较了斐波那契堆和二叉堆。他发现，在他测试的图大小（128个不同密度的顶点）下，斐波那契堆比二叉堆慢30%到60%。

源代码（使用CWEB编写，是C、数学和TeX的混合物）在MILES_SPAN部分中，可以在这里找到。

- paperhorse

1

免责声明

我知道结果非常相似，而且“看起来运行时间完全被堆以外的其他因素所支配”（@Alpedar）。但是我在代码中找不到任何证据支持这一点。代码是公开的，如果您能找到任何可能影响测试结果的因素，请告诉我。

也许我做错了什么，但我编写了一个测试，基于A.Rex的答案进行比较：

Fibonacci堆
D-Ary堆（4）
二叉堆
Relaxed堆

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

对于输出不太详细的问题，很抱歉，因为我需要从文本文件构建一些图表。

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

heap result table

- Guilherme Torres Castro

4

每种情况下有多少条边？你确切地运行了什么算法？如果我们不知道正在处理什么，你的结果就毫无意义。 - kokx

正如我所说，所有的图形都是完整的，因此您可以计算每种情况下的边数。你的意思是，“你正在准确地运行吗？”它们位于表格的标题中。 - Guilherme Torres Castro

25

这似乎是运行时间受到堆之外的某些因素的完全控制（可能是图形生成或某些IO操作）。几乎完全相同的结果令人难以置信。 - Alpedar

2

好吧，也许时间被其他事物所占据，但我确定这不是输入输出或图形生成的问题。无论如何，源代码可用，如果有人发现错误并纠正测量结果，我会非常高兴。 - Guilherme Torres Castro

这些测试似乎在测量完全不同的东西。你能评论一下你运行的测试吗？请记住，如果距离是几何/欧几里得的，完全图上的最短路径问题是O(1)。 - Gaminic

我对 C++ 不是很了解，但你真的可以给从另一个模块导入的静态变量赋值吗？你确定你没有在同一堆上运行所有测试吗？ - Thomas Ahle

0

我也用斐波那契堆做了一个小实验。这是详细信息的链接：Experimenting-with-dijkstras-algorithm。我只是谷歌了“Fibonacci heap java”这个词，并尝试了一些现有的开源实现斐波那契堆。看起来，其中一些存在一些性能问题，但也有一些表现相当不错。至少，在我的测试中它们打败了朴素和二叉堆优先队列的性能。也许它们可以帮助实现高效的算法。

- gabormakrai

0

这里有一个相当全面的答案，以及使用斐波那契堆实现的经过测试的Dijkstra算法的C++代码在这里

- Rhyd Lewis

为了进一步阐述我的上面的答案，我写的下面这篇论文使用了高效的斐波那契堆实现Dijkstra算法。它通常发现与使用堆和二叉树相比，速度大致相同，具体取决于输入图的密度。论文中还附有C++源代码的链接。https://arxiv.org/abs/2303.10034 - Rhyd Lewis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- A. Rex · Accepted Answer

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

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

我能够编译 dijkstra_heap_performance.cpp，并使用修改版的 dijkstra_shortest_paths.hpp 进行比较斐波那契堆和二叉堆。(在这一行 typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue 中，将 relaxed 改为 fibonacci。) 我最初忘记进行优化编译，在这种情况下，斐波那契堆和二叉堆的性能大致相同，斐波那契堆通常会略微优于二叉堆。在我进行了非常强的优化编译后，二叉堆得到了巨大的提升。在我的测试中，只有当图形非常大且密集时，例如：斐波那契堆才能优于二叉堆。

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 最小割算法，因为显然它会生成大量的降键，但是让计时比较工作太麻烦了。警告：我可能做错了什么。您可能希望自己尝试重现这些结果。 理论注释：斐波那契堆在降键方面的改进性能对于理论应用非常重要，例如 Dijkstra 的运行时间。斐波那契堆在插入和合并方面也优于二叉堆（对于斐波那契堆来说，这两个操作都是平摊常数时间）。插入基本上是无关紧要的，因为它不影响 Dijkstra 的运行时，并且很容易修改二叉堆以使其具有平摊常数时间的插入。合并在常数时间内完成是很棒的，但与此应用程序无关。 < p > 个人笔记: 我和我的一个朋友曾经写了一篇论文，解释了一个新的优先队列，试图在不增加复杂性的情况下复制斐波那契堆（理论上）的运行时间。该论文从未发表，但我的合著者实现了二叉堆、斐波那契堆和我们自己的优先队列来比较数据结构。实验结果的图表表明，在总比较次数方面，斐波那契堆略优于二叉堆，这表明在比较成本超过开销的情况下，斐波那契堆的表现会更好。不幸的是，我没有可用的代码，并且在您的情况下，比较可能很便宜，因此这些评论是相关的，但并不直接适用。

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