问题描述
有你曾经实行斐波那契堆的人？我这样做了几年前，但它要比使用基于阵列的BinHeaps要慢几个数量级。
Has anyone of you ever implemented a Fibonacci-Heap? I did so a few years back, but it was several orders of magnitude slower than using array-based BinHeaps.
当时，我还以为它是一个宝贵的教训，如何研究并不像宣称的那样好。然而，大量的研究论文，声称他们的算法基于使用斐波那契堆的运行时间。
Back then, I thought of it as a valuable lesson in how research is not always as good as it claims to be. However, a lot of research papers claim the running times of their algorithms based on using a Fibonacci-Heap.
你有没有管理，以产生一个有效的执行？还是你与数据集的工作如此之大，斐波那契堆是更有效？如果是这样，一些细节将AP preciated。
Did you ever manage to produce an efficient implementation? Or did you work with data-sets so large that the Fibonacci-Heap was more efficient? If so, some details would be appreciated.
推荐答案
的 Boost C ++库包括斐波那契数的实现在升压/申请中/ fibonacci_heap.hpp堆。这个文件显然已经在未决/ 多年，我的预测将不会被接受。此外，还有已在该实现，这是固定我的熟人，全方位的很酷的家伙亚伦温莎错误。不幸的是，大多数的文件，我可以在网上找到（和一个在Ubuntu的libboost-dev软件包）的版本仍然有缺陷;我不得不拉从Subversion版本库一个干净的版本。
由于版本 1.49 的对修改后的版本dijkstra_shortest_paths.hpp比较斐波那契堆和二进制堆。 （在该行的typedef relaxed_heap＆LT;顶点，IndirectCmp，IndexMap＆GT; MutableQueue ，将轻松到斐波纳契。）我第一次忘了编译优化，在这种情况下，斐波那契和二进制堆进行大致相同，用斐波那契堆通常由一个微不足道的金额超越。当我用很强烈的优化编译的二进制堆得到了巨大的提升。在我的测试中，斐波那契堆只跑赢二进制堆时，图形是令人难以置信的大而密，如：
I was able to compile dijkstra_heap_performance.cpp against a modified version of dijkstra_shortest_paths.hpp to compare Fibonacci heaps and binary heaps. (In the line typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue, change relaxed to fibonacci.) I first forgot to compile with optimizations, in which case Fibonacci and binary heaps perform about the same, with Fibonacci heaps usually outperforming by an insignificant amount. After I compiled with very strong optimizations, binary heaps got an enormous boost. In my tests, Fibonacci heaps only outperformed binary heaps when the graph was incredibly large and dense, e.g.:
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.
据我了解，这倒是在斐波那契堆和二进制堆之间的根本区别。这两个数据结构之间的唯一真正的理论不同的是，斐波纳契堆支持减少-键（摊销）固定的时间。另一方面，二元堆得到了极大的从它们的实现作为阵列的性能;使用一个明确的指针结构意味着斐波那契堆遭受巨大的性能损失。
As far as I understand, this touches at the fundamental differences between Fibonacci heaps and binary heaps. The only real theoretical difference between the two data structures is that Fibonacci heaps support decrease-key in (amortized) constant time. On the other hand, binary heaps get a great deal of performance from their implementation as an array; using an explicit pointer structure means Fibonacci heaps suffer a huge performance hit.
因此，从斐波那契堆的在实践中受益的，你必须使用他们在decrease_keys是令人难以置信的频繁的应用程序。在Dijkstra算法而言，这意味着该底层的图是致密的。一些应用程序可能是本质decrease_key密集;我想尝试的Nagomochi - 茨城最小切割算法，因为显然它会产生大量的decrease_keys，但它是太多的努力得到定时比较工作。
Therefore, to benefit from Fibonacci heaps in practice, you have to use them in an application where decrease_keys are incredibly frequent. In terms of Dijkstra, this means that the underlying graph is dense. Some applications could be intrinsically decrease_key-intense; I wanted to try the Nagomochi-Ibaraki minimum-cut algorithm because apparently it generates lots of decrease_keys, but it was too much effort to get a timing comparison working.
的警告的：我可能做错事。您不妨试试重现这些结果吧。
Warning: I may have done something wrong. You may wish to try reproducing these results yourself.
理论注释的：斐波堆上decrease_key的改进的性能是对于理论的应用，如Dijkstra的运行非常重要。斐波那契堆也跑赢大市的插入和合并二进制堆（包括分期常量时间的斐波那契堆）。插入基本上是无关的，因为它不会影响Dijkstra的运行时间，并且它很容易修改二进制堆也已经插入在摊销恒定时间。合并在固定时间内是太棒了，但没有相关的这个应用程序。
Theoretical note: The improved performance of Fibonacci heaps on decrease_key is important for theoretical applications, such as Dijkstra's runtime. Fibonacci heaps also outperform binary heaps on insertion and merging (both amortized constant-time for Fibonacci heaps). Insertion is essentially irrelevant, because it doesn't affect Dijkstra's runtime, and it's fairly easy to modify binary heaps to also have insert in amortized constant time. Merge in constant time is fantastic, but not relevant to this application.
个人笔记的：我的一个朋友和我曾经写过论文，解释了新的优先级队列，它试图复制斐波那契堆的（理论），运行时间没有他们的复杂性。该论文没有发表，但我的合着者没有执行二进制堆，斐波那契堆，和我们自己的优先级队列进行比较的数据结构。实验结果的曲线图表明，斐波堆稍微在总的比较方面出执行二进制堆，这表明斐波堆将在一个情况下比较成本超过开销更好的表现。不幸的是，我没有在code可用，presumably在您的情况比较便宜，所以这些评论是有关，但并不直接适用。
Personal note: A friend of mine and I once wrote a paper explaining a new priority queue, which attempted to replicate the (theoretical) running time of Fibonacci heaps without their complexity. The paper was never published, but my coauthor did implement binary heaps, Fibonacci heaps, and our own priority queue to compare the data structures. The graphs of the experimental results indicate that Fibonacci heaps slightly out-performed binary heaps in terms of total comparisons, suggesting that Fibonacci heaps would perform better in a situation where comparison cost exceeds overhead. Unfortunately, I do not have the code available, and presumably in your situation comparison is cheap, so these comments are relevant but not directly applicable.
顺便说一句，我强烈建议想斐波那契堆的运行时间匹配自己的数据结构。我发现我根本改造斐波那契堆自己。之前，我认为所有的斐波那契堆的复杂性，一些随机的想法，但后来我意识到，他们都是自然和相当强。
Incidentally, I highly recommend trying to match the runtime of Fibonacci heaps with your own data structure. I found that I simply reinvented Fibonacci heaps myself. Before I thought that all of the complexities of Fibonacci heaps were some random ideas, but afterward I realized that they were all natural and fairly forced.
这篇关于有没有人真正实现了一个斐波那契堆有效？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！