3. vecto vs liste push_back() was ist schneller

vecto vs liste push_back() was ist schneller

  • I

    Vor allem muss bei List mehr kopiert werden.

    Bei vector wird der Wert in das interne Array kopiert & der interne Pointer inkrementiert.

    Eine List ist double-linked, also muss ein Zeiger auf das vorhergehende Element kopiert werden, der next-element-pointer des vorhergehenden Elements angepasst werden sowie der next-element pointer des neuen Elements genullt werden.

    0

  • @drakon:
    Ich kenne keine Möglichkeit eine list so zu optimieren, dass nicht für jedes neu eingefügte Element wieder Speicher angefordert werden muss.
    OK, man kann einen Knoten-Pool verwenden, aber den kann man auch erst sinnvoll verwenden wenn die ersten Knoten wieder entfernt wurden.
    So lange man also immer nur an die Liste anhängt, bringt das nix.

    0
  • ?

    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.

    Geil beschrieben.. Danke :D.
    rya.

    0
  • ?

    volkard schrieb:

    merke: vector ist immer schneller. aber vector ruckelt gelegentlich.

    Sollte man einschränken: Es geht hier nur um's "push_back" und es gilt auch nur in den Fällen, in denen das Erzeugen einer Kopie eines Elements "billig" ist.

    Angenommen, das Reservieren und Freigeben von Freispeicher kostet jeweils konstant F Sekunden. Angenommen, das Erzeugen einer Kopie eines Elements kostet K Sekunden. Angenommen, die vector<>-Implementierung verdoppelt die Kapazität immer dann, wenn nicht genug Platz ist. Dann komme ich bei einer Serie von n push_backs auf ungefähr folgende Kosten:

    vector<>: F * (2+log2(n)) + K * 3n (obere Grenze für den worst case)
    list<>: F * n + K * n

    Wenn K gegenüber F sehr groß ist, kann list<> effizienter sein als vector<>.

    0
  • ?

    krümelkacker schrieb:

    vector<>: F * (2+log2(n)) + K * 3n (obere Grenze für den worst case)
    list<>: F * n + K * n

    Eigentlich ist eine untere Grenze für den vector<> Fall interessanter, wenn's darum geht, zu zeigen, list<> kann schneller sein:

    vector<>: F * (1+log2(n)) + K * 2n (untere Grenze)

    (wenn ich mich nicht vertan habe)

    kk

    0
  • A

    krümelkacker schrieb:

    ...

    Wobei das eh hinfällig ist, wenn man auch nur im entferntesten die Größen abschätzen kann (und dem vector entsprechend viel Speicher reservieren lässt).

    Ich habe in der Praxis bislang keinen Fall bewusst erlebt, in dem der std::vector (sofern man sich auch nur grundsätzliche Gedanken zu seiner Verwendung macht) beim Anhängen langsamer als eine std::list war. Wenn man jedoch häufig einfügt, oder mittendrin löscht, sieht es natürlich anders aus.

    0
  • V

    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 👍

    btw: Als Entscheidungshilfe welche Container man nun nehmen soll schau ich gelegentlich auch mal hier nach.

    Gut Schuß
    VuuRWerK 😉

    [edit]Musste Signatur aber aufgrund des Limits leider etwas einkürzen ...[/edit]

    0
  • V

    @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.

    0
  • V

    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.

    0
  • ?

    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.

    0

  • 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.

    0

  • 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...

    0
  • C
    Mod

    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.

    0
  • ?

    camper schrieb:

    Eine Deque darf keine Reallokation durchführen beim Einfügen am Anfang oder am Ende.

    Ahh, ich habe immer nach push_back und push_front gesucht, 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?

    0
  • Administrator

    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

    0
  • ?

    volkard schrieb:

    Ich nehme gerne intrinsische Listen.

    Was sind intrinsische Listen?

    0
  • Administrator

    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.html

    Grüssli

    0
  • V

    Dravere schrieb:

    Vielleicht meinte er intrusiv.

    Ups, klar.

    0
  • L

    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

    0
  • C
    Mod

    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.

    0
Anmelden zum Antworten