Fibonacci Heap: Implementation
-
Hallo zusammen,
Kennt jemand eine saubere schnelle Implementation eines Fibonacci Heaps? Wenn möglich Templatebasierend wie die STL-Priorityqueue. Habe auch nach langer Googlelei nichts vernünftiges gefunden.
http://www.physi.uni-heidelberg.de/~knopf/FibonacciHeap.html
Die Implementation von obigem Link ist nicht wirklich brauchbar, leider ist das die einzige die ich fand.
Vielen Dank und liebe Grüsse.
-
Wenn du jemals eine Implementierung findest, die schneller ist als ein normaler Binärheap, sag bescheid. Alles was ich bisher gesehen habe war wesentlich langsamer. Fibonacci Heaps sind zwar theoretisch schneller aber praktisch hat das noch niemand beobachtet.
-
Hmm...
Denkst Du der Overhead ist so gross, dass auch bei ca. 1 Million Nodes der Binärheap noch schneller ist?
edit: Um mein Problem genauer zu beschreiben:
Ich füge zu Beginn 1 Million Nodes in die Queue ein. Danach wird nichts mehr eingefügt. Danach entferne ich im Durchschnitt 660'000 Nodes wieder mit getMin().
Wäre es da schneller die Nodes in ein Array zu stecken und dieses zu sortieren, und dann nach und nach durch das Array zu gehen?
-
pasti schrieb:
Hmm...
Denkst Du der Overhead ist so gross, dass auch bei ca. 1 Million Nodes der Binärheap noch schneller ist?
Die schnellste Fibonacci Heap Implementierung, die ich gesehen habe, war selbst bei ein paar Milliarden Nodes noch langsamer. Aber mehr als 10GB an Hauptspeicher haben wir nicht getestet.
-
Okey, vielen Dank für deine wertvollen Erfahrungen.
Hast Du meinen obigen geänderten Post gelesen? Was würdest Du mir für einen Ansatz raten?
Vielen Dank für deine Hilfe.
-
Wenn du im voraus weisst wieviel elemente du brauchst, wäre eventuell std::partial_sort interssant. Ansonsten würde ich im voraus ganz sortieren und kein Heap verwenden.
-
Ich weiss eben leider nicht wieviele Einträge ich brauche.
Aber ich habe nun einen Vector mit sort verwendet. Das geht, wie Du gesagt hast, etwa um den Faktor 2-3 schneller.
Vielen Dank nochmals.