3. std::vector-Wachstum

std::vector-Wachstum

  • M

    Bouncer schrieb:

    Mr. N schrieb:

    Wenn du keine Ahnung hast, mach dir doch bitte die Mühe, wenigstens zu versuchen, zu verstehen, worum es geht.

    sei doch nicht gleich beleidigt. erklär' mir lieber, was es für einen unterschied macht, ob dein toller 'std::vector' hin und wieder 'malloc(2*x)' oder 'malloc(x+a) macht. klar, letzteres muss er im durchschnitt öfter machen, aber es amortisiert sich ja auch.
    🙂

    Nein, bei x+a amortisiert es sich nicht.

    0
  • B

    Mr. N schrieb:

    Nein, bei x+a amortisiert es sich nicht.

    doch, aber etwas schlecher als die '*2' methode. dafür spart es massiv speicher (denn wir wollen ja kein benzin in's feuer derjenigen kippen, die C++ für resourcenschwache systeme verteufeln).
    🙂

    0
  • M

    Bouncer schrieb:

    Mr. N schrieb:

    Nein, bei x+a amortisiert es sich nicht.

    doch, aber etwas schlecher als die '*2' methode. dafür spart es massiv speicher (denn wir wollen ja kein benzin in's feuer derjenigen kippen, die C++ für resourcenschwache systeme verteufeln).
    🙂

    Nein, es amortisiert nicht.

    0
  • B

    Mr. N schrieb:

    Nein, es amortisiert nicht.

    dann erkläre es mir bitte. (ja, ich versuche es zu verstehen, das nur mal zu deinem vorwurf weiter oben 😉 ). unter 'amortisiertem O(1)' verstehe ich 'durchschnittlich gesehen konstante laufzeit' wobei hin und wieder ausreisser erlaubt sind. ob die nun regelmässig oder quadratisch auftreten, sollte egal sein.
    🙂

    0
  • ?

    also bouncer....
    Sei X∈NX \in \mathbb{N} und ck=k⋅Xc_k = k \cdot X
    dann ist die mittlere zeit zum Einfuegen eines Wertes nach ckc_k Schritten (also nach k vergroesserungen):
    D_k=1c_k(Ac_k+A∑_n=1kcn)D\_k = \frac{1}{c\_k} \left( A c\_k + A \sum\_{n=1}^k c_n \right)
    da in jeder vergroesserung jeweils alle elemente kopiert werden muessen. Hierbei ist A≥0A \geq 0 eine Konstante,die die Kosten zum kopieren wiederspiegelt.
    Es gilt also:

    Dk=A+AXkXk(k+1)2=A+A2k2+kk=Θ(k)D_k = A + \frac{A}{X k} X \frac{k (k+1)}{2} = A + \frac{A}{2} \frac{ k^2 + k } {k} = \Theta(k)

    damit also echt nicht O(1) [Anm. = O(c) fuer jedes c>0].

    PS: eigentlich wird erst nach ck+1c_k+1 schritten vergroessert,das macht aber die rechnung nur haesslicher und aendert nix am resultat.

    0
  • B

    thomas001 schrieb:

    also bouncer....

    ok, dann eben O(k), -aber- mach die rechnung mal für die verdopplungs-methode. da kommt bestimmt auch kein O(1) raus, eher sowas wie O(sqrt(k)).
    🙂

    0
  • M

    Bouncer schrieb:

    thomas001 schrieb:

    also bouncer....

    ok, dann eben O(k), -aber- mach die rechnung mal für die verdopplungs-methode. da kommt bestimmt auch kein O(1) raus, eher sowas wie O(sqrt(k)).
    🙂

    Nein, da kommt O(1) raus, wenn die Rechnung stimmt.

    0

  • Bouncer schrieb:

    Mr. N schrieb:

    Nein, es amortisiert nicht.

    dann erkläre es mir bitte. (ja, ich versuche es zu verstehen, das nur mal zu deinem vorwurf weiter oben 😉 ). unter 'amortisiertem O(1)' verstehe ich 'durchschnittlich gesehen konstante laufzeit' wobei hin und wieder ausreisser erlaubt sind. ob die nun regelmässig oder quadratisch auftreten, sollte egal sein.
    🙂

    Amortisiert O(1) heisst einfach gesagt dass die Gesamtzeit die zum Einfügen von n Elementen gebraucht wird ca. k*n ist.

    Fix um 10 Elemente vergrössern kann das nicht erfüllen, da die Zeit die zum Kopieren von n Elementen gebraucht wird immer grösser wird (die "Grösse" der "Ausreisser"), die Intervalle in denen kopiert werden muss aber nicht mitwachsen (die Häufigkeit der "Ausreisser").

    0
  • ?

    Sei X∈R+X \in \mathbb{R}^+ und ck=Xkc_k = X^k

    D_k=X−k(AXk+A∑_n=1kXn)D\_k = X^{-k} \left(A X^k + A \sum\_{n=1}^k X^n \right)
    =A+AX−kXk+1−1X−1= A + A X^{-k} \frac{X^{k+1}-1}{X-1}
    =A+AX−1(X−X−k)= A + \frac{A}{X-1} \left( X - X^{-k} \right)
    ≤A+AXX−1\leq A + \frac{A X}{X-1}
    =Θ(1)= \Theta(1)

    0
  • B

    Mr. N schrieb:

    Nein, da kommt O(1) raus, wenn die Rechnung stimmt.

    sieht eigentlich ganz gut aus, so weit ich das überblicken kann (mathe war noch nie meine stärke). aber ich kann mir kaum vorstellen, dass man in einer korrekten, mathematischen darstellung das gelegentliche allozieren und umkopieren, bei der 'mal 2' version, komplett unter den tisch kehren kann.
    🙂

    0
  • ?

    tut man ja auch nicht,rat mal was die summe darstellt 😉

    0
  • B

    thomas001 schrieb:

    tut man ja auch nicht,rat mal was die summe darstellt 😉

    1/2 + 1/4 + 1/8 + 1/16 + .... = 1 ?
    🙂

    0
  • ?

    hmmm.....nein :p

    0
  • ?

    Bleib lieber bei deinen Standard Trollereien Bouncer...

    0
  • B

    Mr. N schrieb:

    Badestrand schrieb:

    Das passiert nicht nur Idioten, das sieht man auch öfters in größeren Projekten von nicht unbedingt ganz unerfahrenen Programmierern. Passiert mir im Nachhinein auch ab und zu, dass ich sehe, dass ein vector irgendwo unangebracht ist und tausche noch die Datenstruktur aus - bin zwar kein Profi aber programmiere auch schon ne Weile.

    Du verwendest nen std::vector wo eine std::map richtig wäre? 😮

    Du interpretierst gern irgendwo was rein, he? 😉 Nix map, map finde ich immer recht eindeutig, ich meine eher list oder dequeue. Wenn man das Projekt nicht fertig durchgestylt hat, weil man einfach noch nicht genau weiß, was das Programm wann wo genau machen soll, kann (mir) das schonmal leicht passieren. Da brauche ich am Anfang nen vector, irgendwann/-wo komme ich dann an einen Punkt, wo evtl doch was anderes angebracht wäre - passiert nicht oft, aber ab und zu schon mal.

    0
  • P

    Bouncer schrieb:

    Mr. N schrieb:

    Nein, da kommt O(1) raus, wenn die Rechnung stimmt.

    sieht eigentlich ganz gut aus, so weit ich das überblicken kann (mathe war noch nie meine stärke). aber ich kann mir kaum vorstellen, dass man in einer korrekten, mathematischen darstellung das gelegentliche allozieren und umkopieren, bei der 'mal 2' version, komplett unter den tisch kehren kann.
    🙂

    In einem Vector werden die Elemente am Anfang öfter kopiert als die Elemente am Ende. Für die Laufzeit verteilt man aber alle Kopieraktionen auf alle Elemente und man sieht, dass bei einer Verdopplung jedes Element durchschnittlich weniger als 2 mal kopiert wurde. Daraus ergibt sich die amortisiert konstante Arbeit pro Einfügeoperation. Man kann amortisierte Laufzeit mit durchschnittlicher Laufzeit gleichsetzen.

    0
  • P

    Ich weiss nicht genau in welchem, aber ein einem seiner Artikel schreibt Herb Sutter, dass ohne weitere Annahmen ein Faktor von ca. 1.5 am guenstigsten ist. Dabei wird natuerlich die Anzahl der alloziierten Bytes gerundet auf ein ganzzahliges Vielfaches von 8 byte (oder 16, 32 byte... systemabhaengig)

    0
  • M

    pumuckl schrieb:

    Ich weiss nicht genau in welchem, aber ein einem seiner Artikel schreibt Herb Sutter, dass ohne weitere Annahmen ein Faktor von ca. 1.5 am guenstigsten ist. Dabei wird natuerlich die Anzahl der alloziierten Bytes gerundet auf ein ganzzahliges Vielfaches von 8 byte (oder 16, 32 byte... systemabhaengig)

    Bytes? Du meinst Elemente? 🙂

    Ich kann mir durchaus vorstellen, dass 1.5 gut wäre. Vermutlich würde das die Benchmarks für kleine Vektoren kaputt machen, weswegen man lieber 2 nimmt?

    0
  • P

    Vergiss meinen Satz mit den 8 byte - war noch nicht ganz wach, hab da was durcheinander gebracht. Was das Thema kleinere vector<>en angeht, kann ich mir vorstellen, dass die erste Allokation ueberhaupt gleich einen groesseren Batzen reserviert, eventuell abhaengig von sizeof(T), sprich, bei vector<char> wird gleich Speicher fuer 50 chars geholt, bei vector<MonsterClass> mit sizeof(MonsterClass) = 10000 dann doch nicht ganz so viel.

    0
  • C

    Hi,

    wie, ein frischer Vektor mit einem gepushten Element allokiert mehr Platz als für dieses eine Element?

    Dann ist mein Vorschlag vom Anfang ja sogar schon umgesetzt... 😮

    ChrisM

    0
Anmelden zum Antworten