vecto vs liste push_back() was ist schneller
-
Newbie19 schrieb:
volkard schrieb:
Ich nehme gerne intrinsische Listen.
Was sind intrinsische Listen?
Vielleicht meinte er intrusiv. Bei Boost gibt es zum Beispiel solche Listen:
http://www.boost.org/doc/libs/1_42_0/doc/html/intrusive.htmlGrüssli
-
Dravere schrieb:
Vielleicht meinte er intrusiv.
Ups, klar.
-
Dravere schrieb:
krümelkacker schrieb:
Jetzt frage ich mich aber, wie die Implementierung funktioniert. Weiß das jemand?
Für den Random Access wird ein dynamisches Array im Hintergrund mitgeführt, welches Zeiger auf die Blöcke hält.
Dein dynamisches Array läuft dann aber auch irgendwann über und muss, ähnlich wie ein vector, in einen größeren Speicherbereich umkopiert werden => Worst Case O(n) bei push_back
-
life schrieb:
Dravere schrieb:
krümelkacker schrieb:
Jetzt frage ich mich aber, wie die Implementierung funktioniert. Weiß das jemand?
Für den Random Access wird ein dynamisches Array im Hintergrund mitgeführt, welches Zeiger auf die Blöcke hält.
Dein dynamisches Array läuft dann aber auch irgendwann über und muss, ähnlich wie ein vector, in einen größeren Speicherbereich umkopiert werden => Worst Case O(n) bei push_back
Mit anderen Worten, mit einem Array funktioniert es nicht. Mit einer hash map hingegen funktioniert es.
-
Realistisch betrachtet ginge vermutlich ein B-Baum als "Index" für eine Deque.
Da ein B-Baum für so eine Anwendung immer extrem flach bleiben wird, kann man die Tiefe für die O-Notation IMO durchaus als "konstant" durchgehen lassen.@camper:
Wieso hash-map?
Muss die hash-map nicht komplett neu aufgebaut werden wenn sie zu gross wird?
Jetzt kann man sagen OK, dann halt konstante Grösse für die Hash-Map. Nur wächst dann wieder die Zeit für nen Lookup, da man zu viele Hash-Kollisionen bekommt, was zu längeren Listen pro Bucket führt.
-
Wer sagt dass deque O(1) insert und erase haben muss?
-
@Shade Of Mine:
krümelkacker schrieb:
Ahh, ich habe immer nach
push_backundpush_frontgesucht, aber die interessante Stelle ist deque<>::insert (§23.2.1.3/3): "...Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a copy constructor of T...".
-
Solange die Blöcke der Deque konstante Größe haben, bringt der Ansatz der lineare verketteten Blöcke nicht viel. Denn dann brauch man für den RandomAccess noch eine zusätzliche Datenstruktur, die
- Random Access (in O(1)) erlaubt und
- in die man in O(1) Elemente vor bzw. hinten einfügen kann.Sprich: Man steht vor genau dem gleichen Problem wie vorher.
Ich habe mir übrigens gerade mal die Implementierung der Deque in der STL von VS08 angeschaut. Dort haben die Blöcke konstante Größe und der RandomAccess wird mit Hilfe eines Ringpuffers ermöglicht. Entsprechend ist die Laufzeit von push_back/front nur amortized costant.
-
hustbaer schrieb:
@Shade Of Mine:
krümelkacker schrieb:
Ahh, ich habe immer nach
push_backundpush_frontgesucht, aber die interessante Stelle ist deque<>::insert (§23.2.1.3/3): "...Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a copy constructor of T...".back und front ist ja trivial lösbar. aber insert/erase in der mitte darf O(lenght-index) haben. Ergo ist auch das trivial lösbar.
keine map nötig, kein index-array, kein garnix.
denn ich muss nur wissen wieviele blöcke ich habe und wo ich jeweils im 1. und letzten block stehe.
PS:
ist halt alles eine frage wofür man optimieren will. ich habe mir für einen nur wachsenden container zB was eigenes gebaut, da darf man nicht in der mitte einfügen und löschen, sondern nur back und front pushen/popen.je nachdem kann man natürlich auch das back/front push/pop vernachlässigen und dafür schnelleres insert/erase haben - das geht dann halt auch wieder auf kosten vom op[]. man muss halt definieren was man will.
-
Shade Of Mine schrieb:
hustbaer schrieb:
@Shade Of Mine:
krümelkacker schrieb:
Ahh, ich habe immer nach
push_backundpush_frontgesucht, aber die interessante Stelle ist deque<>::insert (§23.2.1.3/3): "...Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a copy constructor of T...".back und front ist ja trivial lösbar. aber insert/erase in der mitte darf O(lenght-index) haben. Ergo ist auch das trivial lösbar.
keine map nötig, kein index-array, kein garnix.
Den "Index" brauchst du, weil Random-Access in eine Deque IIRC auch O(1) haben muss.
Und genau dieser Index ist nicht trivial, wenn man insert/remove vorne und hinten auch in O(1) haben will.
Amortisiert O(1) ist einfach, da nimmt man (wie es MSVC macht) einfach nen Vektor als Index. Konstant O(1) ist dagegen nicht so einfach.
-
hustbaer schrieb:
Den "Index" brauchst du, weil Random-Access in eine Deque IIRC auch O(1) haben muss.
Und genau dieser Index ist nicht trivial, wenn man insert/remove vorne und hinten auch in O(1) haben will.
Amortisiert O(1) ist einfach, da nimmt man (wie es MSVC macht) einfach nen Vektor als Index. Konstant O(1) ist dagegen nicht so einfach.Wenn ich insert/erase in der mitte O(size()-pos) haben darf, was ich darf, ist es trivial. dann kopiere ich einfach immer alles. dann habe ich keine lücken, ergo keine index-tabelle nötig.
ist halt wie gesagt eine frage was man haben will, der standard erlaubt eine menge.
-
Shade Of Mine schrieb:
Wenn ich insert/erase in der mitte O(size()-pos) haben darf, was ich darf, ist es trivial. dann kopiere ich einfach immer alles. dann habe ich keine lücken, ergo keine index-tabelle nötig.
-
@Shade:
Wenn man push_front/push_back/pop_front/pop_back nur in amortisiert konstanter Zeit braucht, dann geht viel. U.a. auch ein Ringpuffer wie du es meinst wenn ich dich richtig verstehen.Wenn man allerdings konstante Zeit für push_front/push_back/pop_front/pop_back fordert (ohne amortisiert, so richtig konstant eben), dann kann man eben keinen Ringpuffer verwenden.
