Heap und std::vector und das ganze auf Pointern

Max3000

Was meinst du mit fair?

Die decreaseKey Methode ist genau wie du beschreibst, dass der Key verkleinert wird und damit das Element im Heap aufsteigt. push_heap ist doch aber wenn das Element hinten hinzugefügt wird und dann nach oben gepusht wird oder?
Wie mach ich das genau?

Zur zeit hab ich:

headOfCurrentEdge->key = v->key + currentEdge->length; // decrease the key
make_heap(heap.begin(), heap.end(), comp); // order heap

Vielleicht gehts ja auch mit push_heap, wobei das zweite Argument ein pointer auf das zu verkleinernde Objekt im Heap ist, oder was sagt ihr?

drakon

volkard schrieb:

Max3000 schrieb:

Allerdings suche ich bei der decreaseKey Methode, die der Dijkstra-Algo brauch für den binären Heap noch was effizientes. Da mach ich zur Zeit noch ein make_heap auf den kompletten vector.

decreaseKey? Ist es das, was ich mir drunter vorstelle, nämlich ein Element verkleinern und dabi vorrutschen lassen?
Einfach push_heap nehmen, oder? Die Heap-Bedingung, daß das geänderte Element kleinergleich wie seine Kinder ist, bleibt ja bestehen.

Das Problem an push_heap ist denke ich, dass es nicht in konstanter Zeit läuft. Ein decrease_key in einem Fibonacci Heap hingegen ist (amortisiert) konstant.

decrease_key wird ja max. für jede Kante aufgerufen, was dann bei push_heap O(mlogn) ergibt also O(n^2 * logn). Ein F-Heap hat aber O(nlogn + m). Je nach Dichte des Graphen kann das, denke ich schon was ausmachen.

volkard

Max3000 schrieb:

Zur zeit hab ich:
headOfCurrentEdge->key = v->key + currentEdge->length; // decrease the key
make_heap(heap.begin(), heap.end(), comp); // order heap
Vielleicht gehts ja auch mit push_heap, wobei das zweite Argument ein pointer auf das zu verkleinernde Objekt im Heap ist, oder was sagt ihr?

Ja, das meine ich.

Max3000

Verdammt, jetzt hab ich make_heap durch push_heap ersetzt und jetzt ist mein FibonacciHeap den ich selber implementiert habe langsamer als der Binäre Heap.

Ich muss doch bei push_heap dann mit dem End-Pointer auf das Element setzen, was ich verkleinert hab oder?

push_heap(heap.begin(), elementToDecrease);

wie ich an den zweiten Pointer komme weiß ich leider auch noch nicht.
Der wird doch vom std::vector intern verwaltet oder?

life

drakon schrieb:

decrease_key wird ja max. für jede Kante aufgerufen, was dann bei push_heap O(mlogn) ergibt also O(n^2 * logn). Ein F-Heap hat aber O(nlogn + m). Je nach Dichte des Graphen kann das, denke ich schon was ausmachen.

Dijsktra Algorithmus mit binären Heap implementiert hat eine Laufzeit von O(n log n + m log n), wenn n die Anzahl der Knoten und m die Anzahl der Kanten ist.

drakon

life schrieb:

drakon schrieb:

decrease_key wird ja max. für jede Kante aufgerufen, was dann bei push_heap O(mlogn) ergibt also O(n^2 * logn). Ein F-Heap hat aber O(nlogn + m). Je nach Dichte des Graphen kann das, denke ich schon was ausmachen.

Dijsktra Algorithmus mit binären Heap implementiert hat eine Laufzeit von O(n log n + m log n), wenn n die Anzahl der Knoten und m die Anzahl der Kanten ist.

Ich habe nie von einem binärem Heap gesprochen. m wird ja n^2 bei dichten Grpahen (von dünnen müssen wir ja nicht sprechen, da beides sehr effizient ist). Dann hast du mit deiner Laufzeit (wenn die stimmt) O(n^2 * logn), während mit dem F-Heap hast du lediglich O(n^2 + nlogn) = O(n^2).

@Max3000:
Du musst das Element, dass du einfügen willst mit push_back in den vector einfügen und dann push_heap aufrufen, welcher dann den letzten Wert korrekt in den Heap eingliedert (er wird in O(logn) versickert).

life

Bei der einen Laufzeitangabe |E|=|V|^2 vorauszusetzen und bei der anderen nicht, ist jedenfalls nicht ganz fair.

Ob |E|=|V|^2 der typische Fall ist, hängt dann wohl von deiner Anwendung ab. Normalerweise würde ich aber erwarten, dass die Implementierung mittels binären Heap effizienter ist als eine Implementierung mit fib Heap. Fib. heaps sind nämlich ihmo eher nur von theoretischen Interesse ;).

Ergänzung zu @Max3000: Also z.B. push_heap(&heap[0], (&elementToDecrease)+1);

Max3000

@ drakon:
Beim Einfügen in den Heap hab ich das so gemacht. Aber ich will ja ein Element verkleinern, was schon im Heap drin ist.

Also mein einfügen sieht so aus:

heap.push_back(headOfCurrentEdge);
push_heap(heap.begin(), heap.end(), comp);

und mein decreaseKey jetzt so:

headOfCurrentEdge->key = v->key + currentEdge->length;
push_heap(heap.begin(), heap.end(), comp);

wobei ich denke dass es nicht mal nötig ist bei heap.end() anzufangen. Man kann sicherlich auch ab der stelle pushen, wo headOfCurrentEdge liegt, aber an die komm ich leider nicht. Zumindest weiß ich noch nicht wie.

Wo wir grad beim FibonacciHeap sind, ich hab rausgefunden was meinen so ausbremst. Beim deleteMin muss man ja das minimale Element löschen und alle Kinder in die root Liste einfügen und dann verlinken, wenn 2 Elemente den selben Rang haben.
Dazu fügt man einfach alle Elemente in einen Liste an die x-te Stelle, wobei x der Rang ist. Ist da schon eins wird gelinkt, ansonsten nur eingefügt.
Zur zeit habe ich ein Array aus 100 Elementen (bitte verspottet mich jetzt nicht) und resette das vor jedem deleteMin. Welche Datenstruktur ist dafür am besten geeignet?
-std::vector ist mist, weil es sein kann dass ich erst rootList[5], dann rootList[2] u.s.w. zum Beispiel schreiben will.
-std::map sieht ganz gut aus aber damit hab ich mich noch nicht näher befasst.

Irgendwelche Empfehlungen?

Grüße

Max

drakon

life schrieb:

Bei der einen Laufzeitangabe |E|=|V|^2 vorauszusetzen und bei der anderen nicht, ist jedenfalls nicht ganz fair.

Verstehe ich nicht. Wo habe ich das gemacht? - Ich hatte |E|=|V|^2 in dem von dir gequoteten Ausschnitt, wie auch in meiner Antwort darauf..

Ob |E|=|V|^2 der typische Fall ist, hängt dann wohl von deiner Anwendung ab. Normalerweise würde ich aber erwarten, dass die Implementierung mittels binären Heap effizienter ist als eine Implementierung mit fib Heap. Fib. heaps sind nämlich ihmo eher nur von theoretischen Interesse ;).

Das stimmt schon. Ein F-Heap ist nicht unbedingt besser. Bei sehr dichten Graphen ist der normale Algorithmus von Dijkstra ohne das explizite Speichern des Randes sogar effizienter.
Ich denke mal (ohne jeglichen Beweis liefern zu können), dass bei Fällen, wo der der Algortihmus ohne expl. Rand schlechter ist, als einer mit Rand (aber dennoch recht dicht und gross ist), wird ein F-Heap schon besser sein, aber wie du sagst ist das wohl eher nur in Ausnahmefällen der Fall.

Max3000

Das mit der Map hab ich grad ausprobiert und das ist ja noch langsamer als die mit dem array. Ich glaub ich brauch wirklich hilfe ^^.

life

drakon schrieb:

Verstehe ich nicht. Wo habe ich das gemacht? - Ich hatte |E|=|V|^2 in dem von dir gequoteten Ausschnitt, wie auch in meiner Antwort darauf..

"Ein F-Heap hat aber O(nlogn + m)"

@Max3000:

headOfCurrentEdge->key = v->key + currentEdge->length;
push_heap(&heap[0], (&headOfCurrentEdge)+1, comp);

volkard

Max3000 schrieb:

@ drakon:
Beim Einfügen in den Heap hab ich das so gemacht. Aber ich will ja ein Element verkleinern, was schon im Heap drin ist.

Also mein einfügen sieht so aus:
heap.push_back(headOfCurrentEdge);
push_heap(heap.begin(), heap.end(), comp);
und mein decreaseKey jetzt so:
headOfCurrentEdge->key = v->key + currentEdge->length;
push_heap(heap.begin(), heap.end(), comp);
wobei ich denke dass es nicht mal nötig ist bei heap.end() anzufangen. Man kann sicherlich auch ab der stelle pushen, wo headOfCurrentEdge liegt, aber an die komm ich leider nicht. Zumindest weiß ich noch nicht wie.

Darf nicht! heap.end() ist falsch.
Mußt &(dingWasVersickernSoll)+1 nehmen.

drakon

life schrieb:

drakon schrieb:

Verstehe ich nicht. Wo habe ich das gemacht? - Ich hatte |E|=|V|^2 in dem von dir gequoteten Ausschnitt, wie auch in meiner Antwort darauf..

"Ein F-Heap hat aber O(nlogn + m)"

Ok, hätte das m noch substituieren sollen. Aber das ändert nichts an meiner Aussage. O(n^2) ist besser, als O(n^2 * logn).

@volkard
Imo stimmt das schon. Du fügst zuerst mit push_back was ein und dann rufst du die Funktion auf. Das sollte schon hinhauen oder verstehe ich deinen Einwand falsch?

volkard

drakon schrieb:

Imo stimmt das schon. Du fügst zuerst mit push_back was ein und dann rufst du die Funktion auf. Das sollte schon hinhauen oder verstehe ich deinen Einwand falsch?

Ja, Einfügen geht so.
Aber decreaseKey eines igendwo in der Mitte liegenden Elements nicht.

drakon

Achso. Das meintest du. Ja dort stimme ich dir zu.

Max3000

headOfCurrentEdge->key = v->key + currentEdge->length;
push_heap(&heap[0], (&headOfCurrentEdge)+1, comp);

Das geht leider nicht.
heap ist ein std::vector und das push_heap und alle anderen heap-funktionen wollen einen iterator über meinen vector als argument.
statt &heap[0] sollte also heap.begin() sein.
statt (&headOfCurrentEdge)+1 brauch ich doch sowas wie heap.begin()+positionOfHeadOfEdge+1, oder nicht?

Hab sowieso grad mit diesen Iteratoren zu kämpfen und ich nie weiß an welcher stelle mein Element in der Liste ist.
Das selbe versuch ich grad mit erase, also als kleines Beispiel:

Node<T> *minRoot;
  std::vector<Node<T>*> roots;

  // ...

  roots.erase(minRoot); // wie mach ich sowas?

Also minRoot ist dann in der roots-Liste, aber ich weiß später nicht mehr wo weil ich zuviel hinzufüge.
Der Aufruf erase ist natürlich falsch, weil die Funktion einen Iterator benötigt.

life

Doch das geht so. Probiers doch einfach mal aus.

Abgesehen davon, dass es kompiliert, ist es sogar korrekt: Es ist garantiert, dass die Elemente des vectors direkt hintereinander im Speicher stehen.

Entsprechend kannst du auch die Position eines Elements folgendermaßen erhalten: std::size_t pos = &my_element - &my_vector[0] .

Max3000

Das minRoot ist aber auch ein Pointer. Könnte es daran liegen?
Ich bekomme den Fehler:

error: no matching function for call to ‘std::vector<Node<Vertex>, std::allocator<Node<Vertex>> >::erase(Node<Vertex>**)’

life

Ich bezog mich auf push_heap . erase benötigt tatsächlich einen Iterator.

volkard

life schrieb:

Doch das geht so. Probiers doch einfach mal aus.

Abgesehen davon, dass es kompiliert, ist es sogar korrekt: Es ist garantiert, dass die Elemente des vectors direkt hintereinander im Speicher stehen.

Entsprechend kannst du auch die Position eines Elements folgendermaßen erhalten: std::size_t pos = &my_element - &my_vector[0] .

Wenn ich recht verstanden habe, kommt er deswegen nicht dran:

Node* hierGuck=vec[0];
pop_heap(vec.begin(),vec.end(),comp);vec.pop_back();
for each Node* dortMach in hierGuck.getNeighbors(){
   dortMach->neuBewert();
   push_heap(vec.begin(),/*mistWoLiegtDennDortMach?*/);
}