Fibonacci-Heapを実装したことがある人はいますか? 私は数年前にそうしましたが、配列ベースの BinHeaps を使用するよりも数桁遅かったです。
当時、私はそれが、研究が必ずしも主張されているほど優れているとは限らないことについての貴重な教訓だと考えていました. ただし、多くの研究論文は、フィボナッチ ヒープの使用に基づくアルゴリズムの実行時間を主張しています。
効率的な実装を作成できたことがありますか? それとも、フィボナッチ ヒープがより効率的になるほど大きなデータセットを扱っていましたか? もしそうなら、いくつかの詳細をいただければ幸いです。
Boost C++ ライブラリには、フィボナッチ ヒープの実装が含まれていますboost/pending/fibonacci_heap.hpp。このファイルはどうやら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> MutableQueuerelaxedfibonacci
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.
私が理解している限りでは、これはフィボナッチ ヒープとバイナリ ヒープの根本的な違いに触れています。2 つのデータ構造の唯一の実際の理論上の違いは、フィボナッチ ヒープが (償却された) 定数時間で減少キーをサポートすることです。一方、バイナリ ヒープは、配列として実装することで大きなパフォーマンスを得ることができます。明示的なポインター構造を使用すると、フィボナッチ ヒープのパフォーマンスが大幅に低下します。
したがって、実際にフィボナッチ ヒープの恩恵を受けるには、recrease_keysが非常に頻繁に発生するアプリケーションでそれらを使用する必要があります。ダイクストラに関しては、これは基になるグラフが密であることを意味します。一部のアプリケーションは、本質的にrecrease_key-intensである可能性があります。ナゴモチ・茨木ミニマムカットアルゴリズムはrecrease_keyが大量に生成されるらしいので試してみたかったのですが、タイミング比較がうまくいかず大変でした。
警告: 何か間違ったことをした可能性があります。これらの結果を自分で再現してみてください。
理論上の注意: ダイクストラのランタイムなどの理論上のアプリケーションでは、recrease_key でのフィボナッチ ヒープのパフォーマンスの向上が重要です。フィボナッチ ヒープは、挿入とマージでもバイナリ ヒープよりも優れています (フィボナッチ ヒープでは、どちらも一定時間償却されます)。挿入は Dijkstra の実行時間に影響を与えないため、本質的に無関係です。バイナリ ヒープを変更して、償却された定数時間でも挿入できるようにするのはかなり簡単です。一定時間でのマージは素晴らしいですが、このアプリケーションには関係ありません。
個人的なメモ: 私の友人と私はかつて、フィボナッチ ヒープの (理論上の) 実行時間を複雑さなしに複製しようとした新しい優先度キューについて説明する論文を書きました。論文は公開されませんでしたが、共著者はデータ構造を比較するためにバイナリ ヒープ、フィボナッチ ヒープ、および独自の優先キューを実装しました。実験結果のグラフは、フィボナッチ ヒープが合計比較に関してバイナリ ヒープよりわずかに優れていることを示しており、比較コストがオーバーヘッドを超える状況ではフィボナッチ ヒープのパフォーマンスが向上することを示唆しています。残念ながら、私は利用可能なコードを持っていません.おそらくあなたの状況では比較は安いので、これらのコメントは関連していますが、直接適用することはできません.
ちなみに、フィボナッチ ヒープの実行時間を独自のデータ構造と一致させることを強くお勧めします。フィボナッチヒープを自分で再発明しただけだということがわかりました。以前は、フィボナッチ ヒープの複雑さはすべてランダムなアイデアだと思っていましたが、後になって、それらはすべて自然でかなり強制的なものであることに気付きました。
Knuth は、1993 年に彼の著書Stanford Graphbaseで、最小スパニング ツリーのフィボナッチ ヒープとバイナリ ヒープを比較しました。彼は、さまざまな密度で 128 個の頂点をテストしたグラフ サイズで、フィボナッチがバイナリ ヒープよりも 30 ～ 60% 遅いことを発見しました。
ソース コードは C (または 、C、数学、TeX のクロスである CWEB) のセクション MILES_SPAN にあります。
免責事項
結果は非常に似ており、「実行時間はヒープ以外の何かによって完全に支配されているようです」(@Alpedar)。しかし、コード内にその証拠を見つけることができませんでした。コードは公開されているので、テストの結果に影響を与える可能性のあるものを見つけたら教えてください。
たぶん私は何か間違ったことをしましたが、A.Rex anwser の比較に基づいてテストを書きました:
すべてのヒープの実行時間 (完全なグラフのみ) は非常に近いものでした。テストは、1000、2000、3000、4000、5000、6000、7000、および 8000 個の頂点を持つ完全なグラフに対して行われました。テストごとに 50 個のランダム グラフが生成され、出力は各ヒープの平均時間です。
出力については申し訳ありませんが、テキスト ファイルからいくつかのグラフを作成するために必要だったため、あまり詳細ではありません。
結果は次のとおりです（秒単位）：
また、フィボナッチ ヒープを使った小さな実験も行いました。詳細のリンクは次のとおりです: Experimenting-with-dijkstras-algorithm。「フィボナッチ ヒープ Java」という用語をググって、フィボナッチ ヒープの既存のオープン ソース実装をいくつか試してみました。それらのいくつかはパフォーマンスに問題があるようですが、かなり良いものもあります。少なくとも、私のテストではナイーブおよびバイナリ ヒープの PQ パフォーマンスを上回っています。多分彼らは効率的なものを実装するのを助けることができます.