Quelqu'un a-t-il réellement mis en œuvre un Fibonacci-Heap de manière efficace?

Quelqu'un d'entre vous a-t-il déjà implémenté un Fibonacci-Heap ? Je l'ai fait il y a quelques années, mais c'était plusieurs ordres de grandeur plus lent que d'utiliser des BinHeaps basés sur des tableaux.

À l'époque, je pensais que c'était une leçon précieuse sur le fait que la recherche n'est pas toujours aussi bonne qu'elle le prétend. Cependant, de nombreux articles de recherche revendiquent les temps de fonctionnement de leurs algorithmes basés sur l'utilisation d'un Fibonacci-Heap.

Avez-vous déjà réussi à produire une implémentation efficace? Ou avez-vous travaillé avec des ensembles de données si volumineux que le Fibonacci-Heap était plus efficace? Dans l'affirmative, certains détails seraient appréciés.

Les bibliothèques Boost C ++ incluent une implémentation des tas de Fibonacci dans boost/pending/fibonacci_heap.hpp. Ce dossier existe apparemment depuis pending/des années et d'après mes projections, il ne sera jamais accepté. De plus, il y a eu des bugs dans cette implémentation, qui ont été corrigés par ma connaissance et mon gars sympa, Aaron Windsor. Malheureusement, la plupart des versions de ce fichier que j'ai pu trouver en ligne (et celle du paquet libboost-dev d'Ubuntu) contenaient encore des bogues; J'ai dû extraire une version propre du référentiel Subversion.

Depuis la version 1.49, les bibliothèques Boost C ++ ont ajouté de nombreuses nouvelles structures de tas, y compris le tas 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, remplacez relaxedpar fibonacci.) J'ai d'abord oublié de compiler avec des optimisations, auquel cas Fibonacci et les tas binaires fonctionnent à peu près de la même manière, les tas de Fibonacci surpassant généralement d'un montant insignifiant. 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 ne surpassaient les tas binaires que lorsque le graphique était incroyablement grand et dense, par exemple:

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.

Pour autant que je sache, cela touche aux différences fondamentales entre les tas de Fibonacci et les tas binaires. La seule vraie différence théorique entre les deux structures de données est que les tas de Fibonacci prennent en charge la décroissance en temps constant (amorti). D'un autre côté, les tas binaires tirent beaucoup de performances de leur implémentation en tant que tableau; l'utilisation d'une structure de pointeur explicite signifie que les tas de Fibonacci souffrent d'un énorme impact sur les performances.

Par conséquent, pour bénéficier des tas de Fibonacci dans la pratique , vous devez les utiliser dans une application où les diminutions_keys sont incroyablement fréquentes. En termes de Dijkstra, cela signifie que le graphique sous-jacent est dense. Certaines applications peuvent être intrinsèquement intensives en diminution_ touches; Je voulais essayer l'algorithme de coupe minimum de Nagomochi-Ibaraki parce qu'apparemment, il génère beaucoup de touches de diminution, mais c'était trop d'effort pour faire fonctionner une comparaison de temps.

Attention : j'ai peut-être fait quelque chose de mal. Vous voudrez peut-être essayer de reproduire vous-même ces résultats.

Note théorique : L'amélioration des performances des tas de Fibonacci sur diminution_key est importante pour les applications théoriques, telles que le runtime de Dijkstra. Les tas de Fibonacci surpassent également les tas binaires lors de l'insertion et de la fusion (tous deux amortis à temps constant pour les tas de Fibonacci). L'insertion n'est essentiellement pas pertinente, car elle n'affecte pas le temps d'exécution de Dijkstra, et il est assez facile de modifier des tas binaires pour avoir également une insertion en temps constant amorti. Fusionner en temps constant est fantastique, mais pas pertinent pour cette application.

Note personnelle : Un de mes amis et moi avons écrit un jour un article expliquant une nouvelle file d'attente prioritaire, qui tentait de reproduire le temps de fonctionnement (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 d'attente prioritaire pour comparer les structures de données. Les graphiques des résultats expérimentaux indiquent que les tas de Fibonacci surpassent légèrement les tas binaires en termes de comparaisons totales, suggérant que les tas de Fibonacci fonctionneraient mieux dans une situation où le coût de comparaison dépasse les frais généraux. Malheureusement, je n'ai pas le code disponible, et probablement dans votre situation, la comparaison est bon marché, donc ces commentaires sont pertinents mais pas directement applicables.

Incidemment, je recommande fortement 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'avais 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 j'ai réalisé qu'elles étaient toutes naturelles et assez forcées.

Knuth a fait une comparaison entre le tas de fibonacci et les tas binaires pour les arbres couvrant minimum en 1993 pour son livre Stanford Graphbase . Il a trouvé que fibonacci était 30 à 60% plus lent que les tas binaires aux tailles de graphe qu'il testait, 128 sommets à des densités différentes.

Le code source est en C (ou plutôt CWEB qui est un croisement entre C, math et TeX) dans la section MILES_SPAN.

Avertissement

Je sais que les résultats sont assez similaires et "on dirait que le temps d'exécution est totalement dominé par autre chose que le tas" (@Alpedar). Mais je n'ai rien trouvé de preuve dans le code. Le code est ouvert, donc si vous pouvez trouver quelque chose qui peut affecter le résultat du test, veuillez me le dire.

Peut-être que j'ai fait quelque chose de mal, mais j'ai écrit un test , basé sur A.Rex anwser comparant:

• Fibonacci-Heap
• D-Ary-tas (4)
• Tas binaire
• Tas détendu

Les temps d'exécution (pour les graphiques complets uniquement) pour tous les tas étaient très proches. Le test a été fait pour des graphiques complets avec 1000,2000,3000,4000,5000,6000,7000 et 8000 sommets. Pour chaque test, 50 graphiques aléatoires ont été générés et le résultat est le temps moyen de chaque tas:

Désolé pour la sortie, ce n'est pas très détaillé car j'en avais besoin pour créer des graphiques à partir de fichiers texte.

Voici les résultats (en secondes):

J'ai également fait une petite expérience avec le tas de Fibonacci. Voici le lien pour les détails: Expérimenter avec l'algorithme dijkstras . Je viens de googler les termes "Fibonacci heap java" et j'ai essayé quelques implémentations open-source existantes du tas Fibonacci. Il semble que certains d'entre eux ont des problèmes de performances, mais il y en a qui sont assez bons. Au moins, ils battent les performances naïves et binaires du tas PQ dans mon test. Peut-être qu'ils peuvent aider à mettre en œuvre le plus efficace.