Dijkstra on Java: Interessante Ergebnisse mit einem Fibonacci Heap vs. PriorityQueue

Question

Ich habe kürzlich einen ersten Vergleich der Laufzeit des Dijkstra-Algorithmus mit zwei Datenstrukturen gemacht, der Java-basierten PriorityQueue (basierend auf einem binären Heap, wenn I ' Ich irre mich nicht) und ein Fibonacci-Haufen. Ich habe Javas currentTimeMillis() verwendet, um meine Berechnungen durchzuführen. Die Ergebnisse, mit denen ich endete, sind ziemlich interessant. Dies ist die Ausgabe für einen meines Testfall:

Running Dijkstra's with 8 nodes and 27 links 
- Execution time with binary heap: 1 miliseconds 
- Execution time with Fibonacci heap: 4 miliseconds 

Zugegeben, ich bin kurz auf Datensätze im Moment mit der obigen Grafik meines größten ist (ich plane, bald mehr zu machen). Aber macht das irgendeinen Sinn? Ich habe immer gedacht, Fibonacci Heaps waren schneller als andere Datenstrukturen aufgrund ihrer amortisierten Laufzeit im Vergleich zu den anderen Datenstrukturen. Ich bin mir nicht sicher, woher dieser Unterschied von 3 Millisekunden kommt. (Ich führe es auf einem Intel Core Ivy Bridge i7-3630M Prozessor, wenn das hilft.)

Hinweis: Ich stolperte über this thread, die das Problem erklären könnte, obwohl ich immer noch unklar bin, warum der Fibonacci-Heap Version dauert länger. Diesem Thread zufolge könnte es daran liegen, dass mein Graph nicht dicht genug ist und daher die Anzahl der Verkleinerungs-Key-Operationen nicht groß genug ist, um die Leistung des Fibonacci-Heaps wirklich zu glänzen. Wäre das die einzig plausible Schlussfolgerung, oder fehlt mir noch etwas?

Answer 1

Fibonacci-Heaps sind asymptotisch schneller als binäre Heaps (die Struktur von Daten in Java der Prioritätswarteschlange verwendet wird), in diesem Dijkstra-Algorithmus wird O nehmen (m + n log n) Zeit mit einer Fibonacci-Heap aber O (m log n) mit einem binären Heap. Dies bedeutet, dass für große, dichte Graphen im schlimmsten Fall Fibonacci-Haufen schneller sind.

Obwohl Fibonacci-Haufen asymptotisch schneller als binäre Haufen sind, haben sie notorisch große konstante Faktoren und viele grundlegende Operationen auf Fibonacci-Haufen benötigen eine lange Zeit, um abgeschlossen zu werden. Auf lange Sicht werden sie binäre Haufen übertreffen, aber für kleine Graphen können die konstanten Terme so groß sein, dass der Fibonacci-Haufen tatsächlich langsamer ist.

Zweitens, vergleichen Sie die asymptotischen Laufzeiten (O (m + n log n) gegen O (m log n)). Wenn das verwendete Diagramm spärlich ist (d. H. M = O (n)), sind beide asymptotischen Laufzeiten gleich (O (n log n)). In diesem Fall ist der theoretische Vorteil von Fibonacci-Heaps nicht vorhanden und der binäre Heap könnte die bessere Wahl sein.

Beachten Sie schließlich, dass sich die Groß-O-Notation in diesem Fall auf das Worst-Case-Verhalten bezieht und nicht auf den Durchschnittsfall. Vor einiger Zeit gab es eine Zeitung, die zeigte, dass der Dijkstra-Algorithmus für Zufallsgraphen eines bestimmten Typs weit weniger als die Worst-Case-Anzahl von Sink-Schlüssel- und -Entnahme-Operationen benötigt. In diesem Fall könnte ein binärer Heap sogar in großen Diagrammen einen Fibonacci-Heap übertreffen, da das Worst-Case-Verhalten nie ausgelöst wird.

Hoffe, das hilft!

Answer 2

Fibonacci Haufen haben schneller Asymptotik, aber ihre konstanten Faktoren sind nicht unbedingt groß. Auf lächerlich großen Inputs über eine Million oder so könnten sie schneller sein, aber für kleine Inputs sind binäre Haufen wahrscheinlich merklich schneller.