Dijkstra on Java：フィボナッチヒープとPriorityQueueを使用した面白い結果の取得

Question

最近、私はDijkstraのアルゴリズムの実行時間をJavaベースのPriorityQueue（バイナリヒープに基づいて、私は間違っていない）、フィボナッチヒープ。私は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 

確かに私は、上のグラフは、（私はもっとすぐにする予定）私の最大のもので、現時点ではデータセットに短いです。しかし、これは意味をなさないでしょうか？フィボナッチヒープは、他のデータ構造と比較して実行時間が償却されるため、他のデータ構造よりも速いと私は常に考えてきました。私はこの3ミリ秒の違いがどこから来ているのか本当に分かりません。

注：フィボナッチヒープの理由についてはまだわかりませんが、私はthis threadを見つけました。バージョンが長くかかります。そのスレッドによれば、私のグラフは十分に密ではないので、フィボナッチヒープのパフォーマンスが実際に輝くためには、キー操作の減少回数が十分ではないためです。これは唯一のもっともらしい結論ですか、それとも私が行方不明のものがありますか？

Answer 1

フィボナッチヒープがそのダイクストラのアルゴリズムは、フィボナッチヒープとO（M + N Nログ）は、時間がかかりますで、バイナリヒープ（Javaのプライオリティキューに使用されるデータ構造）よりも漸近速いであるが、O（MログN ）をバイナリヒープで置き換えます。これは、大規模で高密度のグラフの場合、最悪の場合、フィボナッチヒープがより高速になることを意味します。

フィボナッチヒープはバイナリヒープよりも漸進的に高速ですが、フィボナッチヒープの多くの基本的な操作は非常に長い定数ファクターを持ち、多くの基本操作は完了に時間がかかります。長期的には、バイナリヒープを上回りますが、小さなグラフの場合、定数項が非常に大きく、フィボナッチヒープが実際より遅くなることがあります。

次に、漸近ランタイム（O（m + n log n）対O（m log n））を比較してください。使用しているグラフがまばらな場合（つまりm = O（n））、これらの漸近ランタイムは同じです（O（n log n））。その場合、フィボナッチヒープの理論上の利点は存在せず、バイナリヒープが優れた選択肢になる可能性があります。

最後に、big-O表記は、平均的な場合ではなく、この場合の最悪の場合の動作を示します。ある種のランダムグラフでは、Dijkstraのアルゴリズムの期待値が、最悪ケースの減少キーとデキュー操作よりもはるかに低いことが示されています。その場合、バイナリヒープは、ワーストケースの動作が決して引き起こされないため、大きなグラフであってもフィボナッチヒープを上回る可能性があります。

希望すると便利です。

Answer 2

フィボナッチヒープは、より速く漸近線を持っていますが、それらの定数係数は必ずしも大きいとは限りません。百万人以上の非常に巨大な入力では、より速いかもしれませんが、小さな入力の場合、バイナリヒープは目立って高速になる可能性があります。