Hat jemand tatsächlich einen Fibonacci-Heap effizient implementiert?

151

Hat jemand von euch jemals einen Fibonacci-Heap implementiert ? Ich habe dies vor ein paar Jahren getan, aber es war mehrere Größenordnungen langsamer als die Verwendung von Array-basierten BinHeaps.

Damals hielt ich es für eine wertvolle Lektion, wie Forschung nicht immer so gut ist, wie sie behauptet. Viele Forschungsarbeiten behaupten jedoch, dass die Laufzeiten ihrer Algorithmen auf der Verwendung eines Fibonacci-Heaps basieren.

Haben Sie jemals eine effiziente Implementierung erreicht? Oder haben Sie mit Datensätzen gearbeitet, die so groß waren, dass der Fibonacci-Heap effizienter war? Wenn ja, würden einige Details geschätzt.

performance algorithm language-agnostic data-structures fibonacci-heap mdm
quelle
25
Hast du nicht gelernt, dass diese Algorithmus-Typen ihre riesigen Konstanten immer hinter ihrem großen großen Oh verstecken?! :) In der Praxis scheint es meistens so zu sein, dass das "n" -Ding dem "n0" nicht einmal nahe kommt!
Mehrdad Afshari
Ich weiss jetzt. Ich habe es implementiert, als ich meine Kopie von "Introduction to Algorithms" zum ersten Mal bekam. Außerdem habe ich Tarjan nicht für jemanden ausgewählt, der eine nutzlose Datenstruktur erfinden würde, weil seine Splay-Bäume eigentlich ziemlich cool sind.
Mdm
mdm: Natürlich ist es nicht nutzlos, aber genau wie die Einfügungssortierung, die in kleinen Datenmengen die Quicksortierung übertrifft, funktionieren binäre Heaps aufgrund kleinerer Konstanten möglicherweise besser.
Mehrdad Afshari
1
Eigentlich war das Programm, für das ich den Heap brauchte, Steiner-Trees für das Routing in VLSI-Chips zu finden, sodass die Datensätze nicht gerade klein waren. Aber heutzutage (mit Ausnahme von einfachen Dingen wie Sortieren) würde ich immer den einfacheren Algorithmus verwenden, bis er im Datensatz "kaputt geht".
Mdm
1
Meine Antwort darauf lautet eigentlich "Ja". (Nun, mein Mitautor auf einem Papier hat es getan.) Ich habe den Code momentan nicht, daher werde ich weitere Informationen erhalten, bevor ich tatsächlich antworte. Bei Betrachtung unserer Diagramme stelle ich jedoch fest, dass F-Haufen weniger Vergleiche anstellen als b-Haufen. Haben Sie etwas verwendet, bei dem der Vergleich billig war?
A. Rex

Antworten:

136

Die Boost C ++ - Bibliotheken enthalten eine Implementierung von Fibonacci-Heaps in boost/pending/fibonacci_heap.hpp. Diese Datei ist anscheinend seit pending/Jahren in und wird von meinen Projektionen nie akzeptiert. Außerdem gab es Fehler in dieser Implementierung, die von meinem Bekannten und rundum coolen Aaron Windsor behoben wurden. Leider hatten die meisten Versionen dieser Datei, die ich online finden konnte (und die in Ubuntus libboost-dev-Paket), immer noch die Fehler; Ich musste eine saubere Version aus dem Subversion-Repository ziehen.

Seit Version 1.49 haben Boost C ++ - Bibliotheken viele neue Heap-Strukturen hinzugefügt, einschließlich Fibonacci-Heap.

Ich konnte dijkstra_heap_performance.cpp gegen eine modifizierte Version von dijkstra_shortest_paths.hpp kompilieren , um Fibonacci-Heaps und binäre Heaps zu vergleichen. ( typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueueWechseln Sie relaxedin der Zeile zu fibonacci.) Ich habe zuerst vergessen, mit Optimierungen zu kompilieren. In diesem Fall funktionieren Fibonacci-Heaps und binäre Heaps ungefähr gleich, wobei Fibonacci-Heaps normalerweise eine unbedeutende Leistung erbringen. Nachdem ich mit sehr starken Optimierungen kompiliert hatte, erhielten binäre Heaps einen enormen Schub. In meinen Tests übertrafen Fibonacci-Heaps nur dann binäre Heaps, wenn der Graph unglaublich groß und dicht war, z.

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.

Soweit ich weiß, berührt dies die grundlegenden Unterschiede zwischen Fibonacci-Haufen und binären Haufen. Der einzige wirkliche theoretische Unterschied zwischen den beiden Datenstrukturen besteht darin, dass Fibonacci-Haufen die Abnahme des Schlüssels in (amortisierter) konstanter Zeit unterstützen. Auf der anderen Seite erzielen binäre Heaps durch ihre Implementierung als Array eine hohe Leistung. Die Verwendung einer expliziten Zeigerstruktur bedeutet, dass Fibonacci-Haufen einen enormen Leistungseinbruch erleiden.

Um von Fibonacci-Haufen in der Praxis zu profitieren , müssen Sie sie daher in einer Anwendung verwenden, in der Abnahmeschlüssel unglaublich häufig sind. In Bezug auf Dijkstra bedeutet dies, dass der zugrunde liegende Graph dicht ist. Einige Anwendungen können von Natur aus abnehmungsintensiv sein. Ich wollte den Nagomochi-Ibaraki-Minimum-Cut-Algorithmus ausprobieren, da er anscheinend viele Abnahmeschlüssel generiert, aber es war zu aufwendig , einen Timing-Vergleich zum Laufen zu bringen.

Warnung : Ich habe möglicherweise etwas falsch gemacht. Möglicherweise möchten Sie versuchen, diese Ergebnisse selbst zu reproduzieren.

Theoretischer Hinweis : Die verbesserte Leistung von Fibonacci-Heaps auf minus_key ist wichtig für theoretische Anwendungen wie die Laufzeit von Dijkstra. Fibonacci-Heaps übertreffen auch binäre Heaps beim Einfügen und Zusammenführen (beide amortisierte konstante Zeit für Fibonacci-Heaps). Das Einfügen ist im Wesentlichen irrelevant, da es die Laufzeit von Dijkstra nicht beeinflusst und es ziemlich einfach ist, binäre Heaps so zu ändern, dass sie auch in einer amortisierten konstanten Zeit eingefügt werden. Das Zusammenführen in konstanter Zeit ist fantastisch, aber für diese Anwendung nicht relevant.

Persönliche Anmerkung : Ein Freund von mir und ich haben einmal ein Papier geschrieben, in dem eine neue Prioritätswarteschlange erklärt wurde, in der versucht wurde, die (theoretische) Laufzeit von Fibonacci-Haufen ohne deren Komplexität zu replizieren. Das Papier wurde nie veröffentlicht, aber mein Co-Autor hat binäre Heaps, Fibonacci-Heaps und unsere eigene Prioritätswarteschlange implementiert, um die Datenstrukturen zu vergleichen. Die Grafiken der experimentellen Ergebnisse zeigen, dass Fibonacci-Heaps die binären Heaps in Bezug auf Gesamtvergleiche leicht übertrafen, was darauf hindeutet, dass Fibonacci-Heaps in einer Situation, in der die Vergleichskosten den Overhead übersteigen, eine bessere Leistung erbringen würden. Leider habe ich den Code nicht zur Verfügung und vermutlich ist der Vergleich in Ihrer Situation billig, daher sind diese Kommentare relevant, aber nicht direkt anwendbar.

Im Übrigen empfehle ich dringend, die Laufzeit von Fibonacci-Heaps mit Ihrer eigenen Datenstruktur abzugleichen. Ich fand heraus, dass ich Fibonacci-Haufen einfach neu erfunden habe. Früher dachte ich, dass alle Komplexitäten von Fibonacci-Haufen zufällige Ideen waren, aber danach wurde mir klar, dass sie alle natürlich und ziemlich erzwungen waren.

A. Rex
quelle
Vielen Dank! Diese Frage hatte mich schon lange beschäftigt. Ich habe Dijkstra's tatsächlich mit Fibonacci-Heaps implementiert, bevor ich Steiner-Trees versuchte. Es scheint jedoch, dass meine Grafiken viel weniger dicht waren als in Ihrem Beispiel. Sie hatten Millionen von Knoten, aber einen durchschnittlichen Grad von nur 5-6.
Mdm
Die Leistung von Fib Heap ist über die Abfolge der Operationen vorhersehbar. Ich habe einen Heap-lastigen Algorithmus geschrieben, der mit dem Fib Heap (vs. Bin Heap) schneller endete. Der Trick bestand darin, die Arbeit zu stapeln. Unabhängig von der Häufigkeit einer Operation liegt der Unterschied hier: DecreaseKey - ExtractMin - DecreaseKey - ExtractMin versus DecreaseKey - DecreaseKey - ExtractMin - ExtractMin (Fortsetzung unten)
Gaminic
Letzteres ist ungefähr doppelt so schnell, da der 2. ExtractMin fast kostenlos ist. Unser Algorithmus extrahiert einen Stapel von Min-Elementen, von denen viele verworfen werden. eine Verschwendung auf einem Müllhaufen, aber besser auf einem Fibhaufen. Leider spiegelt sich dies nicht eindeutig in der zeitlichen Komplexität wider, die Menschen bei Heap-basierten Algorithmen bereitstellen. Bei amortisierten Grenzen ist die Gesamtkomplexität nicht einfach die Komplexität der Operationen.
Gaminic
1
Gibt es eine Chance, auch Haufen und / oder entspannte Haufen zu paaren?
Thomas Ahle
1
Ich bin mir nicht sicher, warum Ihre Ergebnisse so nahe beieinander lagen. Ich habe STL priority_queue gegen den selbst implementierten Fibonacci-Heap verwendet, und der binäre Heap lag in meinen Tests mit großem Abstand zurück .
Nicholas Pipitone
33

Knuth führte 1993 für sein Buch Stanford Graphbase einen Vergleich zwischen Fibonacci-Haufen und binären Haufen für minimale Spannbäume durch . Er fand, dass Fibonacci bei den von ihm getesteten Graphengrößen 30 bis 60 Prozent langsamer sind als binäre Haufen, 128 Eckpunkte bei verschiedenen Dichten.

Der Quellcode befindet sich in C (oder besser CWEB, eine Kreuzung zwischen C, Mathe und TeX) im Abschnitt MILES_SPAN.

Papierpferd
quelle
1

Haftungsausschluss

Ich weiß, dass die Ergebnisse ziemlich ähnlich sind und "die Laufzeit anscheinend völlig von etwas anderem als dem Haufen dominiert wird" (@Alpedar). Aber ich konnte im Code keine Beweise dafür finden. Der Code ist offen. Wenn Sie also etwas finden, das das Testergebnis beeinflussen kann, sagen Sie es mir bitte.

Vielleicht habe ich etwas falsch gemacht, aber ich habe einen Test geschrieben , der auf dem Vergleich von A.Rex antwortet basiert :

  • Fibonacci-Haufen
  • D-Ary-Haufen (4)
  • Binärhaufen
  • Entspannter Haufen

Die Ausführungszeiten (nur für vollständige Diagramme) für alle Heaps waren sehr eng. Der Test wurde für vollständige Diagramme mit 1000,2000,3000,4000,5000,6000,7000 und 8000 Eckpunkten durchgeführt. Für jeden Test wurden 50 zufällige Diagramme erstellt und die Ausgabe ist die durchschnittliche Zeit jedes Heaps:

Entschuldigung für die Ausgabe, sie ist nicht sehr ausführlich, da ich sie brauchte, um einige Diagramme aus Textdateien zu erstellen.

Hier sind die Ergebnisse (in Sekunden):

Heap-Ergebnistabelle

Guilherme Torres Castro
quelle
4
Wie viele Kanten gibt es jeweils? Und welchen Algorithmus führen Sie genau aus? Ihre Ergebnisse sind nicht sinnvoll, wenn wir nicht wissen, womit wir es zu tun haben.
Kokx
Leider sind alle Grafiken vollständig, sodass Sie die Anzahl der Kanten für jeden Fall berechnen können. Was du meinst, "rennst du genau". Sie stehen im Kopf der Tische.
Guilherme Torres Castro
22
Dies sieht so aus, als ob die Laufzeit vollständig von etwas anderem als dem Heap dominiert wird (es könnte sich um eine Grafik oder eine E / A handeln). Diese fast genau gleichen Ergebnisse sind unglaublich.
Alpedar
2
Nun, vielleicht wird die Zeit von etwas anderem dominiert, aber ich bin sicher, dass dies nicht die E / A oder die Erzeugung der Graphen ist. Auf jeden Fall ist der Quellcode verfügbar und ich werde mich sehr freuen, wenn jemand einen Fehler findet und die Meldung korrigiert.
Guilherme Torres Castro
Diese Tests scheinen etwas ganz anderes zu messen. Könnten Sie den Test kommentieren, den Sie durchgeführt haben? Denken Sie daran, dass das Problem des kürzesten Pfades in einem vollständigen Diagramm O (1) ist, wenn die Abstände geometrisch / euklidisch sind.
Gaminic
0

Ich habe auch ein kleines Experiment mit Fibonacci-Haufen gemacht. Hier ist der Link für die Details: Experimentieren mit dem Dijkstras-Algorithmus . Ich habe gerade die Begriffe "Fibonacci-Heap-Java" gegoogelt und einige vorhandene Open-Source-Implementierungen des Fibonacci-Heaps ausprobiert. Es scheint, dass einige von ihnen Leistungsprobleme haben, aber es gibt einige, die ziemlich gut sind. Zumindest übertreffen sie in meinem Test die naive und die binäre Heap-PQ-Leistung. Vielleicht können sie helfen, die effiziente umzusetzen.

gabormakrai
quelle