有没有人真正有效地实施了斐波纳契堆？

有没有人曾经实施过Fibonacci-Heap？几年前我这样做了,但它比使用基于阵列的BinHeaps要慢几个数量级.

那时候,我认为这是一个很有价值的教训,研究的结果并不像它声称的那样好.然而,许多研究论文声称他们的算法的运行时间基于使用Fibonacci-Heap.

你有没有设法产生有效的实施？或者你使用的数据集如此之大,以至于Fibonacci-Heap效率更高？如果是这样,一些细节将不胜感激.

所述升压C++库包括斐波那契堆在一个实现boost/pending/fibonacci_heap.hpp.这个文件显然已存在pending/多年,我的预测永远不会被接受.此外,该实现中存在一些错误,这些错误由我的熟人和全能酷男Aaron Windsor修复.不幸的是,我在网上找到的那个文件的大多数版本(以及Ubuntu的libboost-dev软件包中的那个版本)仍然存在错误; 我不得不从Subversion存储库中提取一个干净的版本.

从版本1.49 Boost C++库添加了许多新的堆结构,包括fibonacci堆.

我能够编译dijkstra_heap_performance.cpp对修改后的版本dijkstra_shortest_paths.hpp比较斐波那契堆和二进制堆.(在该行中typedef relaxed_heap MutableQueue,更改relaxed为fibonacci.)我首先忘记了使用优化进行编译,在这种情况下,Fibonacci和二进制堆的执行大致相同,而Fibonacci堆通常表现得非常微不足道.经过非常强大的优化编译后,二进制堆得到了巨大的推动.在我的测试中,当图形非常大且密集时,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.

据我所知,这触及了Fibonacci堆和二进制堆之间的根本区别.两个数据结构之间唯一真正的理论差异是Fibonacci堆支持(摊销)恒定时间中的减少键.另一方面,二进制堆从它们作为数组的实现中获得了很大的性能; 使用显式指针结构意味着斐波纳契堆受到巨大的性能影响.

因此,要在实践中受益于Fibonacci堆,您必须在reduce_keys非常频繁的应用程序中使用它们.就Dijkstra而言,这意味着底层图是密集的.一些应用程序可能本质上是reduce_key-intense; 我想尝试使用Nagomochi-Ibaraki最小割算法,因为它显然会产生大量的reduce_keys,但是为了使时序比较工作太费力了.

警告:我可能做错了什么.您可能希望尝试自己复制这些结果.

理论注释:斐波那契堆在减少_键上的改进性能对理论应用很重要,例如Dijkstra的运行时间.Fibonacci堆在插入和合并时也优于二进制堆(对于Fibonacci堆都是平均化的常数时间).插入本质上是不相关的,因为它不会影响Dijkstra的运行时,并且修改二进制堆也很容易插入到分摊的常量时间.恒定时间合并非常棒,但与此应用程序无关.

个人提示:我和我的一位朋友曾写过一篇论文,解释了一个新的优先级队列,试图复制斐波那契堆的(理论上)运行时间,而不会产生复杂性.该论文从未发表过,但我的合着者确实实现了二进制堆,Fibonacci堆和我们自己的优先级队列来比较数据结构.实验结果的图表表明斐波那契在总比较方面略微超出了二进制堆,这表明斐波那契堆在比较成本超过开销的情况下表现更好.不幸的是,我没有可用的代码,并且可能在你的情况下比较便宜,所以这些评论是相关的,但不是直接适用的.

顺便说一句,我强烈建议尝试将Fibonacci堆的运行时与您自己的数据结构相匹配.我发现我自己彻底改造了斐波那契堆.在我认为Fibonacci堆的所有复杂性是一些随机的想法之前,但后来我意识到它们都是自然而且相当强迫.

Knuth在1993年为他的书Stanford Graphbase做了最小生成树的斐波纳契堆和二元堆之间的比较.他发现斐波那契在他测试的图形尺寸上比二进制堆慢30到60%,在不同密度下有128个顶点.

的源代码是在C(或者更确切地说CWEB其是C,数学和TeX的之间的交叉)的部分MILES_SPAN.