3. std::vector-Wachstum

std::vector-Wachstum

  • B

    finix schrieb:

    ChrisM schrieb:

    Was man vielleicht noch machen könnte, ist eine Mindestmenge an Bytes vorzugeben, die allokiert werden muss, z.B. 4k.

    Und was soll das bringen?

    unter windoofs z.b. arbeitet der memory-manager mit 4k-pages. dann könnte so'n vector direkt systemfunktionen aufrufen, um sich speicher zu holen und bräuchte kein malloc/realloc für kleinerer stückchen zu benutzen.
    🙂

    0
  • C

    Hallo,

    finix schrieb:

    ChrisM schrieb:

    Meistens ist der Vektor aber sowieso ein schlechter Container und eine Map oder eine (Double Linked) List besser geeignet.

    Dir ist schon klar dass eine Liste andere Stärken und Schwächen als ein Vektor hat? Und was soll das mit der Map? "Benutz lieber keine Säge, nimm den Hammer"?

    Ja, du kannst schon davon ausgehen, dass ich den Unterschied zwischen einer verketteten Liste (std::list), einem besseren Array (std::vector) und einem Red-Black-Baum (std::map) kenne. Nur weil ich im C++-Forum kaum noch was frage, heißt das nicht, dass ich nicht mehr entwickle. Ganz im Gegenteil.

    Ich sage nur, dass zumindest in den Codes, die ich so sehe, viele Programmierer einen Vektor verwenden, wo er nicht nur unnötig ist, sondern auch schlechter als die Alternativen. Also wo beispielsweise regelmäßig Elemente (in der Mitte) eingefügt oder gelöscht werden oder locker mal der ganze Vektor in einer Schleife durchlaufen wird, um was zu suchen (wonach man auch eine Map befüllen könnte).

    Der Abschuss war z.B. eine Liste in einem Netzwerkstacks (UDP, ein Computerspiel), in dem Pakete mit ID vermerkt werden sollten, auf die noch ein ACK aussteht. Also sozusagen prädestiniert für eine Map (viele Einträge, sortierbar und es wird dauernd eingefügt/gelöscht, Größe ist schlecht vorherzusagen und ändert sich dauernd). Welcher Container aber wurde genommen? Vektor.

    Wenn man diese Fälle mal aussortiert, wird man merken, dass die Allokationsstrategie des Vektors zunehmend unwichtig wird, weil man Vektoren in der Regel sowieso eher selten befüllt und danach die Daten nur noch vorhält.

    ChrisM schrieb:

    Was man vielleicht noch machen könnte, ist eine Mindestmenge an Bytes vorzugeben, die allokiert werden muss, z.B. 4k.

    Und was soll das bringen?[/quote]

    Hab ich doch geschrieben:

    Für den Fall, dass ein Programm den Vektor befüllt und vorher kein reserve() aufruft, weil er noch nicht weiß, wie viel Elemente im Ladevorgang kommen werden.

    Wenn du tausend Integers ohne reserve() einfügst, wird der Speicher nur einmal vergrößert und nicht, je nach Startgröße, bis zu zwölf mal. Wo ist da das Verständnisproblem?

    Bevor jetzt die Nachfrage kommt: 4k mindestens zu holen ist vielleicht zu viel und war nur ein Beispiel. Im Endeffekt muss man für den durchschnittlichen Anwendungsfall ein Optimum ermitteln- einen Kompromiss zwischen Speicherbenutzung und Allokierungsaufrufen.

    ChrisM

    0
  • M

    @ChrisM: Wir gehen hier doch bitte nicht von Idioten aus, die nicht in der Lage sind, zu sehen, wann std::vector unangebracht ist. Auch wenn es die in der Realität geben mag.

    Bouncer schrieb:

    ich bin für punkt 3, c*a(n), aber so, dass der benutzer c einstellen kann.

    Als float oder wie?

    0
  • B

    Mr. N schrieb:

    Wir gehen hier doch bitte nicht von Idioten aus, die nicht in der Lage sind, zu sehen, wann std::vector unangebracht ist. Auch wenn es die in der Realität geben mag.

    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.

    0
  • B

    Mr. N schrieb:

    Bouncer schrieb:

    ich bin für punkt 3, c*a(n), aber so, dass der benutzer c einstellen kann.

    Als float oder wie?

    hmmm?? stimmt. das geht ja gar nicht so richtig ganzzahlig. ich meinte mehr a(n+1)=a(n)+x, also wenn die momentane kapazität erschöpft ist, dann kommt ein fester betrag dazu und der soll einstellbar sein. verdoppeln ist echt manchmal fies: http://www.mathekiste.de/neu2000/schachbrett.htm
    🙂

    0
  • M

    Bouncer schrieb:

    Mr. N schrieb:

    Bouncer schrieb:

    ich bin für punkt 3, c*a(n), aber so, dass der benutzer c einstellen kann.

    Als float oder wie?

    hmmm?? stimmt. das geht ja gar nicht so richtig ganzzahlig. ich meinte mehr a(n+1)=a(n)+x, also wenn die momentane kapazität erschöpft ist, dann kommt ein fester betrag dazu und der soll einstellbar sein.

    Dann wäre push_back nicht mehr amortisiert O(1).

    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? 😮

    Ob man immer die optimale Struktur verwendet ist ne andere Frage. Z.B. wird wohl std::deque seltener verwendet als das sinnvoll wäre.

    0
  • B

    Mr. N schrieb:

    Bouncer schrieb:

    Mr. N schrieb:

    Bouncer schrieb:

    ich bin für punkt 3, c*a(n), aber so, dass der benutzer c einstellen kann.

    Als float oder wie?

    hmmm?? stimmt. das geht ja gar nicht so richtig ganzzahlig. ich meinte mehr a(n+1)=a(n)+x, also wenn die momentane kapazität erschöpft ist, dann kommt ein fester betrag dazu und der soll einstellbar sein.

    Dann wäre push_back nicht mehr amortisiert O(1).

    O(1) ist ja nicht O(const). aber falls dem so wäre, was macht push_back, wenn es mal keinen neuen speicher vom system anfordern muss? ein delay?
    🙂

    0
  • M

    Bouncer schrieb:

    Mr. N schrieb:

    Bouncer schrieb:

    Mr. N schrieb:

    Bouncer schrieb:

    ich bin für punkt 3, c*a(n), aber so, dass der benutzer c einstellen kann.

    Als float oder wie?

    hmmm?? stimmt. das geht ja gar nicht so richtig ganzzahlig. ich meinte mehr a(n+1)=a(n)+x, also wenn die momentane kapazität erschöpft ist, dann kommt ein fester betrag dazu und der soll einstellbar sein.

    Dann wäre push_back nicht mehr amortisiert O(1).

    O(1) ist ja nicht O(const). aber falls dem so wäre, was macht push_back, wenn es mal keinen neuen speicher vom system anfordern muss? ein delay?
    🙂

    Amortisiertes O(1) erlaubt durchaus Unterschiede in der Laufzeit. Muss es auch für push_back.

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

    0
  • B

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

    0
  • 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
Anmelden zum Antworten