[解決済み] フィボナッチヒープを実際に効率よく実装した人はいますか？

質問

を実装したことがある方はいらっしゃいますか？ フィボナッチ・ヒープ ? 数年前にそうしましたが、配列ベースのBinHeapを使うより数桁遅かったです。

当時は、「研究というものは、必ずしも主張するほど良いものではない」という貴重な教訓だと思いました。しかし、多くの研究論文では、フィボナッチヒープを使った上でのアルゴリズムの実行時間を主張しています。

効率的な実装を実現できたことはありますか？あるいは、フィボナッチヒープの方が効率的なほど大きなデータセットを扱ったのでしょうか？もしそうなら、詳細を教えてください。

どのように解決するのですか？

<ストライク その 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> MutableQueue を変更します。 relaxed を 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.

私の理解では、これはフィボナッチヒープとバイナリヒープの根本的な違いに触れているように思います。 この2つのデータ構造の理論的な違いは、フィボナッチヒープが（償却された）一定時間内にキーを減少させることをサポートしていることだけです。 一方、バイナリヒープは配列として実装することで大きな性能を得ます。明示的なポインタ構造を使用することは、フィボナッチヒープが大きな性能上の打撃を受けることを意味します。

したがって、フィボナッチ・ヒープの恩恵を受けるには 実際に decrease_keyが非常に頻繁に発生するようなアプリケーションで使用する必要があります。 Dijkstraの観点では、これは基礎となるグラフが密であることを意味します。 いくつかのアプリケーションは本質的にdecrease_keyの頻度が高いかもしれません。 なごもち・いばらきミニマムカットアルゴリズム というのも、どうやらたくさんのdecrease_keyを生成するようなのですが、タイミング比較を動作させるのが面倒だったのです。

警告 : 何か間違ったことをしたのかもしれません。 この結果を自分で再現してみるのもいいかもしれません。

理論的なメモ : decrease_keyにおけるフィボナッチヒープの性能向上は、Dijkstraのランタイムのような理論的応用において重要である。 フィボナッチヒープは、挿入とマージにおいてもバイナリヒープより優れている(フィボナッチヒープでは両方とも償却された定数時間)。 挿入はDijkstraの実行時間に影響を与えないので、本質的に無関係であり、挿入を償却済み定数時間で行うようにバイナリヒープを修正するのはかなり簡単である。 定数時間でのマージは素晴らしいが、このアプリケーションには関係ない。

個人的なメモ : 私の友人と私はかつて、フィボナッチ・ヒープの（理論上の）実行時間をその複雑さなしに再現しようとする、新しい優先キューを説明する論文を書いたことがあります。 その論文は出版されませんでしたが、私の共著者はデータ構造を比較するためにバイナリヒープ、フィボナッチヒープ、そして私たち自身の優先キューを実装しました。 実験結果のグラフを見ると、比較の総量でフィボナッチヒープがバイナリヒープをわずかに上回っており、比較コストがオーバーヘッドを上回る状況ではフィボナッチヒープがより良い性能を発揮することが示唆されています。 残念ながら、私はそのコードを持っておらず、また、おそらくあなたの状況では比較は安価であるため、これらのコメントは関連性があるが、直接適用できない。

ちなみに、フィボナッチ・ヒープの実行時間を自分のデータ構造と合わせてみることを強くお勧めします。 私は、単にフィボナッチ・ヒープを自分で再発明したに過ぎないことに気づきました。 以前は、フィボナッチヒープの複雑さはすべて思いつきだと思っていたのですが、終わってみると、どれも自然で、かなり無理をしていることに気がつきました。