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

151

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.

mdm
la source
25
N'avez-vous pas appris que ces mecs d'algorithmes cachent toujours leurs énormes constantes derrière leur grand grand oh?! :) Il semble en pratique, la plupart du temps, que la chose "n" ne se rapproche jamais du "n0"!
Mehrdad Afshari le
Je sais maintenant. Je l'ai implémenté lorsque j'ai reçu ma première copie de "Introduction aux algorithmes". De plus, je n'ai pas choisi Tarjan pour quelqu'un qui inventerait une structure de données inutile, parce que ses Splay-Trees sont en fait assez cool.
mdm
mdm: Bien sûr, ce n'est pas inutile, mais tout comme le tri par insertion qui bat le tri rapide dans les petits ensembles de données, les tas binaires pourraient mieux fonctionner en raison de constantes plus petites.
Mehrdad Afshari le
1
En fait, le programme pour lequel j'avais besoin du tas était de trouver des Steiner-Trees pour le routage dans les puces VLSI, donc les ensembles de données n'étaient pas exactement petits. Mais de nos jours (sauf pour des trucs simples comme le tri) j'utiliserais toujours l'algorithme le plus simple jusqu'à ce qu'il "casse" sur l'ensemble de données.
mdm le
1
Ma réponse à cela est en fait «oui». (Eh bien, mon co-auteur sur un papier l'a fait.) Je n'ai pas le code pour le moment, donc je vais obtenir plus d'informations avant de répondre. En regardant nos graphiques, cependant, je constate que les tas F font moins de comparaisons que les tas b. Utilisiez-vous quelque chose où la comparaison était bon marché?
A. Rex

Réponses:

136

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.

A. Rex
la source
Merci! Cette question me préoccupait depuis longtemps. J'ai en fait implémenté Dijkstra en utilisant Fibonacci-Heaps avant d'essayer Steiner-Trees. Cependant, il semble que mes graphiques soient beaucoup moins denses que dans votre exemple. Ils avaient des millions de nœuds, mais un degré moyen de seulement 5-6.
mdm
Les performances du Heap Fib sont prévisibles via la séquence d'opérations. J'ai écrit un algorithme lourd qui s'est terminé plus rapidement avec le Fib Heap (vs Bin Heap). L'astuce consistait à regrouper le travail. Quelle que soit la fréquence des opérations, la différence réside ici: DecreaseKey - ExtractMin - DecreaseKey - ExtractMin versus DecreaseKey - DecreaseKey - ExtractMin - ExtractMin (suite ci-dessous)
Gaminic
Ce dernier sera environ deux fois plus rapide, car le 2nd ExtractMin est presque gratuit. Notre algorithme extrait un lot d'éléments Min dont beaucoup sont rejetés; un déchet sur un tas de bacs, mais mieux sur un tas de fibres. Malheureusement, cela ne se reflète pas clairement dans la complexité du temps que les gens fournissent lorsqu'ils parlent d'algorithmes basés sur Heap. Avec les limites amorties, la complexité totale n'est pas simplement # opérations * complexité de l'opération.
Gaminic
1
Avez-vous également une chance d'essayer d'associer des tas et / ou des tas détendus?
Thomas Ahle
1
Je ne sais pas pourquoi vos résultats sont apparus si proches, j'ai utilisé STL priority_queue contre le tas de fibonacci auto-implémenté et le tas binaire était en retard dans mes tests .
Nicholas Pipitone
33

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.

cheval de papier
la source
1

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):

table de résultats de tas

Guilherme Torres Castro
la source
4
Combien d'arêtes y a-t-il dans chaque cas? Et quel algorithme utilisez-vous exactement? Vos résultats n'ont aucun sens si nous ne savons pas à quoi nous avons affaire.
kokx
Comme je suis triste, tous les graphiques sont complets, vous pouvez donc calculer le nombre d'arêtes pour chaque cas. Ce que vous voulez dire, "courez-vous exactement". Ils sont en tête des tableaux.
Guilherme Torres Castro
22
Il semble que le temps d'exécution soit totalement dominé par autre chose que le tas (il pourrait générer un graphe ou des E / S). Ces résultats presque exactement identiques sont incroyables.
Alpedar
2
Eh bien peut-être que le temps est dominé par autre chose, mais je suis sûr que ce n'est pas l'IO ou la génération des graphiques. Quoi qu'il en soit, le code source est disponible et je serai très heureux si quelqu'un trouve une erreur et corrige la mesure.
Guilherme Torres Castro
Ces tests semblent mesurer quelque chose de complètement différent. Pouvez-vous commenter le test que vous avez effectué? N'oubliez pas que le problème du chemin le plus court sur un graphique complet est O (1) si les distances sont géométriques / euclidiennes.
Gaminic
0

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.

gabormakrai
la source