vecto vs liste push_back() was ist schneller
-
@asc:
.reserve() braucht man ziemlich selten. Oder ich brauche es nicht. Der
Verdopplungs-Trick ist schon saubillig. Pro Reinkonstruktion durch push_back passieren höchstens zwei Kopierungen durch Wachstum.
Und natürlich ist die Freude groß, wenn man kleine Sachen reinstopft. Aber wer käme auf die Idee, es anders zu machen? Entweder man hat kleine Sachen wie ip-Adressen, 3d-Punkte, integers, oder man hat "große" Sachen wie Zeiger auf Armee, Zeiger auf Buchungssatz oder std::string.
@hustbaer: Ein Knoten-Pool kann sehr wohl schon in der Wachstumsphase beschleunigen. Du denkst nur an eine platte Freispeicherliste. Ich denke daran, bei Leerstand der Freispeicherliste immer 4096/sizeof(Konoten) Knoten auf einmal zu besorgen.
-
VuuRWerK schrieb:
volkard schrieb:
merke: vector ist immer schneller. aber vector ruckelt gelegentlich. daher will der pro-gamer evtl lieber list, er braucht zwar draifach-starke hardware, aber es ruckelt nicht. denn ruckeln ist der tod im gegeneinandernetzwerkspiel. der datenbankkonvertierer will vector, denn er schaufelt dreimal so viel daten durch, das ruckeln kümmert ihn gar nicht, er wartet ja nur kaffetrinkend aufs ende des jobs.
Kommt in meine Signatur, Sehr schön beschrieben, vielen Dank
Das ist nett. Aber ich fürchte, es ist falsch. Der Pro-Gamer will wohl lieber deque, die ruckelt nämlich auch nicht. Und er verwaltet auch nur kleine und "große" Objekte. Nur krümelkacker braucht list "wenn K gegenüber F sehr groß ist".
Ich nehme gerne intrinsische Listen. Aber wozu es std::list gibt, weiß ich gar nicht. Ich habe sie noch niue benutzt.
-
volkard schrieb:
Der Pro-Gamer will wohl lieber deque, die ruckelt nämlich auch nicht.
Bist Du Dir da sicher? Eine deque mit "random access" würde ich auch mit einem Array (so ähnlich wie vector) implementieren. Dann würden push_back und push_front aber nur amortisiert konstante Zeit benötigen und gelegentlich Elemte in ein größeres Array umkopieren.
§23.1/12: "... An implementation shall provide these operations for all container types shown in the container column and shall implement them so as to take amortized constant time... push_front | deque,list ... push_back | deque,list,vector ... a[n] | deque,vector ..."
Eine deque ohne random access ließe sich auch mit einer verketteten Liste implementieren. Aber dafür haben wir ja eigentlich schon std::list.
volkard schrieb:
Nur krümelkacker braucht list "wenn K gegenüber F sehr groß ist".
Woher willst Du das wissen, was ich und andere brauchen?
volkard schrieb:
Ich nehme gerne intrinsische Listen. Aber wozu es std::list gibt, weiß ich gar nicht. Ich habe sie noch niue benutzt.
Listen bieten neben dem effizienten Einfügen und Löschen noch nette Garantien bzgl der Validität von Iteratoren und Referenzen auf Elemente bei diversen Listenoperationen.
-
volkard schrieb:
@hustbaer: Ein Knoten-Pool kann sehr wohl schon in der Wachstumsphase beschleunigen. Du denkst nur an eine platte Freispeicherliste. Ich denke daran, bei Leerstand der Freispeicherliste immer 4096/sizeof(Konoten) Knoten auf einmal zu besorgen.
Das ist möglich, hat aber einen recht lästigen Nachteil.
Nämlich dass du die Knoten dann auch nur in grossen Blöcken zurückgeben kannst.
Wenn du in so eine Liste erst viel reinsteckst, und dann jedes 2. Element wieder rauslöscht, dann wird der Speicherverbrauch nicht sinken.
Nichtmal wenn du nur ein paar wenige Prozent der Elemente drin lässt, wenn die grad so verteilt sind, dass auf jeder Page noch min. ein Element liegt.Von Vektor erwartet man dass er keinen Speicher mehr frei gibt, ist von daher OK. Von List erwartet man das nicht, und daher wäre so eine Implementierung etwas "riskant".
----
Was noch ginge (vielleicht hast du ja auch das gemeint): wenn die Heap-Implementierung eine Funktion "besorg mit N unabhängige Blöcke Speicher auf einmal" hat, dann könnte das evtl. was bringen. N Nodes auf einmal anfordern wird vermutlich schneller sein, als N mal eine Node anfordern, auch wenn die Nodes die auf einmal angefordert werden unabhängige Speicherblöcke sein müssen.
-
krümelkacker schrieb:
volkard schrieb:
Nur krümelkacker braucht list "wenn K gegenüber F sehr groß ist".
Woher willst Du das wissen, was ich und andere brauchen?
vermutlich meint er dass man K immer hübsch klein machen kann indem man nen zeiger verwendet...
-
krümelkacker schrieb:
volkard schrieb:
Der Pro-Gamer will wohl lieber deque, die ruckelt nämlich auch nicht.
Bist Du Dir da sicher? Eine deque mit "random access" würde ich auch mit einem Array (so ähnlich wie vector) implementieren. Dann würden push_back und push_front aber nur amortisiert konstante Zeit benötigen und gelegentlich Elemte in ein größeres Array umkopieren.
Eine Deque darf keine Reallokation durchführen beim Einfügen am Anfang oder am Ende. Abgesehen davon würde diese Argumentation auch gegenüber list funktionieren, wenn diese allgemeine Regel nicht jeweils durch eine speziellere ersetzt würde, was sowohl bei list als auch bei deque der Fall ist.
-
camper schrieb:
Eine Deque darf keine Reallokation durchführen beim Einfügen am Anfang oder am Ende.
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...".Jetzt frage ich mich aber, wie die Implementierung funktioniert. Weiß das jemand?
-
krümelkacker schrieb:
Jetzt frage ich mich aber, wie die Implementierung funktioniert. Weiß das jemand?
Wahrscheinlich über mehrere kleiner Blöcke von konstanter Grösse. Sobald der Block voll ist, wird ein neuer Block konstanter Grösse angelegt. Für den Random Access wird ein dynamisches Array im Hintergrund mitgeführt, welches Zeiger auf die Blöcke hält. Wenn man einen Index übergibt, dividiert man ihn durch die konstante Grösse der Blöcke und weiss somit, in welchem Block sich der Eintrag befindet, danach nimmt man den Rest der Division und geht über Zeigerarithmetik zum entsprechenden Objekt im Block.
Grüssli
-
volkard schrieb:
Ich nehme gerne intrinsische Listen.
Was sind intrinsische Listen?
-
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.
