Komplexität von Priority Queue - seltsam?

Hi

Kann es sein, dass die STL Priority Queue eine seltsame Zeitkomplexität hat?
Das pushen dauert immer länger, je mehr Elemente hinzukommen. Ist ja noch logisch.
Aber beim poppen (sry) wird es gegen Ende immer schneller.
Ich finde das komisch, ich dachte die Reihenfolge wird beim pushen festgelegt, und danach wäre der Zugriff konstant.

Ist das normal, oder ist die Implementierung von vc8 so lahm?

grüsse

ps: habe eine dequeue als Container für die pq verwendet.

volkard

das ist ganz normal.
schau mal nach, was ein heap ist.

Konrad Rudolph

Hmm, also laut SGI-Doku sollten sowohl push_heap als auch pop_heap logarithmische Laufzeit haben. Klingt logisch. Es sollte aber in jedem Fall abhängig von der Heap-Größe sein, damit sollte auch das Poppen bei größeren Heaps länger dauern.

Oh ja interessant.
Dann hätt ich doch gern ein Fibonacci- oder ein Soft Heap

Hm schade, ist wohl nur mit eigener Implementierung möglich, oder gibts etwas bei Boost?

Bräucht halt ziemlich schnelles push und pop von bis zu 500 Zahlen, und das dauert mit STLs pq schon mit 255 Elementen ewig.

volkard

afair gabs bei codeguru nen fertigen fibonacci heap.
aber das mit dem ewig-dauern bei 255 elems halte ich für seltsam. haste riesenobjektre, die zu kopieren zu teuer ist?

Konrad Rudolph

Hi Fish schrieb:

Dann hätt ich doch gern ein Fibonacci- oder ein Soft Heap

[...]

Bräucht halt ziemlich schnelles push und pop von bis zu 500 Zahlen.

Da wärst Du mit einem Fibonacci-Heap sehr schlecht bedient. Gerade beim Poppen mit wenigen Zahlen ist der nämlich langsamer als ein Binomial- oder Binär-Heap.

Ne, übergebe nur ints.
Vielleicht liegts an meinem Comparator, siehe den Thread hier ( ich war der l00ser ).
Aber das sind eigentlich auch nur zwei Zugriffe auf ein Array von ints.
Weis auch nicht, wo der soviel rechnet.

...hm ok
im release build gehts schneller, aber auch nicht wirklich hui.
lass jetzt mal CodeAnalyst drüber...

Hat sich erledigt, die Matrix wurde bei jedem Vergleich kopiert als Member des Comparator Objekts. Hat jetzt statt dessen nur einen Zeiger und jetzt flutscht es richtig gut.

Danke für eure Hilfe

Ponto

Theoretisch hat ein Fibonacci Heap bessere Laufzeiten als ein normaler Heap. Aber ich hab noch keinen gesehen, der nicht wesentlich langsamer als ein normaler war.