Fie*_*nix 5 java heap dijkstra data-structures fibonacci-heap
我最近使用两种数据结构初步比较了Dijkstra算法的运行时间,基于Java的PriorityQueue(基于二进制堆,如果我没有弄错的话)和Fibonacci堆.我使用Java的currentTimeMillis()来进行计算.我最终得到的结果非常有趣.这是我的一个测试用例的输出:
Running Dijkstra's with 8 nodes and 27 links
- Execution time with binary heap: 1 miliseconds
- Execution time with Fibonacci heap: 4 miliseconds
不可否认,我目前在数据集方面很缺乏,上面的图表是我最大的(我计划尽快制作).但这有什么意义吗？我一直认为Fibonacci堆比其他数据结构更快,因为与其他数据结构相比,它们的运行时间分摊了.我不确定这个3毫秒差异来自哪里.(我在Intel Core Ivy Bridge i7-3630M处理器上运行它,如果有帮助的话.)
注意:我偶然发现了这个可能解释这个问题的线程,尽管我仍然不清楚为什么Fibonacci堆版本需要更长的时间.根据该线程,可能是因为我的图形不够密集,因此reduce-Key操作的数量不足以使Fibonacci堆的性能真正发光.这是唯一合理的结论,还是我还缺少其他的东西？
Fibonacci堆比二进制堆(Java的优先级队列中使用的数据结构)渐近地快,因为Dijkstra算法将使用Fibonacci堆获得O(m + n log n)时间,而使用二进制堆获得O(m log n).这意味着对于大而密集的图形,在最坏的情况下,Fibonacci堆将更快.
虽然Fibonacci堆比二进制堆渐近快,但它们具有众所周知的大常数因子,并且Fibonacci堆上的许多基本操作需要很长时间才能完成.从长远来看,它们的性能优于二进制堆,但对于小型图形,常数项可能非常大,以至于Fibonacci堆实际上更慢.
其次,比较渐近运行时间(O(m + n log n)与O(m log n)).如果您使用的图形是稀疏的(即m = O(n)),那么这两个渐近运行时都是相同的(O(n log n)).在这种情况下,Fibonacci堆的理论优势不存在,二进制堆可能是最好的选择.
最后,请注意,大O符号表示在这种情况下的最坏情况行为,而不是平均情况.前面有一篇论文表明,对于某种类型的随机图,Dijkstra的期望算法远低于最坏情况下的减少键和出列操作的数量.在这种情况下,即使在大型图形上,二进制堆也可能胜过斐波纳契堆,因为最坏情况的行为永远不会被触发.
希望这可以帮助!