El Bibliothèques C++ Boost incluent une implémentation des tas de Fibonacci en boost/pending/fibonacci_heap.hpp . Ce dossier a apparemment été dans pending/ depuis des années et, selon mes prévisions, ne sera jamais accepté. De plus, il y a eu des bogues dans cette implémentation, qui ont été corrigés par ma connaissance et mon ami Aaron Windsor. Malheureusement, la plupart des versions de ce fichier que j'ai pu trouver en ligne (et celle qui se trouve dans le paquet libboost-dev d'Ubuntu) comportaient encore des bogues ; j'ai donc dû retirer une version propre à partir du dépôt de Subversion.
Depuis la version 1.49 Bibliothèques C++ Boost Ajout d'un grand nombre de nouvelles structures de tas, y compris le tas de fibonacci.
J'ai pu compiler dijkstra_heap_performance.cpp contre une version modifiée de dijkstra_shortest_paths.hpp pour comparer les tas de Fibonacci et les tas binaires. (Dans la ligne typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue le changement relaxed a fibonacci .) J'ai d'abord oublié de compiler avec des optimisations, auquel cas les tas Fibonacci et binaires ont des performances à peu près identiques, les tas Fibonacci étant généralement supérieurs d'une quantité insignifiante. Après avoir compilé avec de très fortes optimisations, les tas binaires ont reçu un énorme coup de pouce. Dans mes tests, les tas de Fibonacci n'ont surpassé les tas binaires que lorsque le graphe était incroyablement grand et dense, par ex :
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.
D'après ce que je comprends, cela touche aux différences fondamentales entre les tas de Fibonacci et les tas binaires. La seule différence théorique réelle entre les deux structures de données est que les tas Fibonacci permettent de diminuer la clé en temps constant (amorti). D'autre part, les tas binaires tirent une grande partie de leurs performances de leur implémentation en tant que tableau ; l'utilisation d'une structure de pointeurs explicite signifie que les tas de Fibonacci subissent une énorme perte de performances.
Par conséquent, pour bénéficier des tas de Fibonacci en pratique si vous devez les utiliser dans une application où les clés de diminution sont très fréquentes. En termes de Dijkstra, cela signifie que le graphe sous-jacent est dense. Certaines applications pourraient être intrinsèquement intenses en clefs décroissantes ; je voulais essayer l'algorithme de coupe minimale de Nagomochi-Ibaraki parce qu'apparemment il génère beaucoup de decrease_keys, mais c'était trop d'efforts pour faire fonctionner une comparaison de temps.
Avertissement : J'ai peut-être fait quelque chose de mal. Vous pouvez essayer de reproduire ces résultats vous-même.
Note théorique : L'amélioration des performances des tas de Fibonacci sur decrease_key est importante pour les applications théoriques, comme le runtime de Dijkstra. Les tas Fibonacci sont également plus performants que les tas binaires sur l'insertion et la fusion (tous deux amortis en temps constant pour les tas Fibonacci). L'insertion n'est pas pertinente, car elle n'affecte pas le temps d'exécution de Dijkstra, et il est assez facile de modifier les tas binaires pour que l'insertion se fasse également en temps constant amorti. La fusion en temps constant est fantastique, mais n'est pas pertinente pour cette application.
Note personnelle : Un de mes amis et moi avons écrit un article expliquant une nouvelle file d'attente prioritaire, qui tentait de reproduire le temps d'exécution (théorique) des tas de Fibonacci sans leur complexité. L'article n'a jamais été publié, mais mon co-auteur a implémenté des tas binaires, des tas de Fibonacci et notre propre file prioritaire pour comparer les structures de données. Les graphiques des résultats expérimentaux indiquent que les tas de Fibonacci sont légèrement plus performants que les tas binaires en termes de comparaisons totales, ce qui suggère que les tas de Fibonacci seraient plus performants dans une situation où le coût de la comparaison dépasse l'overhead. Malheureusement, je n'ai pas le code disponible, et vraisemblablement dans votre situation la comparaison est bon marché, donc ces commentaires sont pertinents mais pas directement applicables.
Au passage, je vous recommande vivement d'essayer de faire correspondre le temps d'exécution des tas de Fibonacci avec votre propre structure de données. J'ai découvert que j'ai simplement réinventé les tas de Fibonacci moi-même. Avant, je pensais que toutes les complexités des tas de Fibonacci étaient des idées aléatoires, mais après coup, j'ai réalisé qu'elles étaient toutes naturelles et assez forcées.
