std::vector-Wachstum
-
Umfrage: Welche ist die beste std::vector-Wachstumsfolge?
Auswahl Stimmen Prozent a(n+1)=2*a(n) [verdoppeln] 17 58.6% a(n+1)=a(n)+a(n-2) [MSVC 2005] 6 20.7% a(n+1)=c*a(n), 1<c<2 5 17.2% andere, werde ich posten 1 3.4% Wie ihr sicher wisst, wächst der Speicher in vector (capacity) schneller als die Anzahl der Elemente (size). Der Standard verlangt ja nur, dass push_back() amortisiert O(1) benötigt. Die üblichste Folge, mit der die Capacity wächst, ist sicherlich a(n+1)=2*a(n) [verdoppeln], aber es gibt auch noch andere.
Welche ist (im Allgemeinen) die beste?
-
Die "beste" ist sicherlich eine dem Spezialfall angepasste Methode. Im allgemeinen (also für ein "general purpose" Element wie std::vector) finde ich das schnöde verdoppeln gut. KISS.
-
Hallo,
verdoppeln ist für den durchschnittlich Anwendungsfall sicherlich okay, wenn man bedenkt, dass Vektoren in der Regel eher klein gehalten werden und Speicher heut zutage nicht mehr das Problem ist. Meistens ist der Vektor aber sowieso ein schlechter Container und eine Map oder eine (Double Linked) List besser geeignet.
Was man vielleicht noch machen könnte, ist eine Mindestmenge an Bytes vorzugeben, die allokiert werden muss, z.B. 4k. 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.
ChrisM
-
für gewöhnlich ist irgendwas um verdoppeln ganz gut geeignet (was auch üblich ist)
im spezialfall weis man bereits vorher wieviel man brauchtvon daher recht irelevant, hauptsache es passiert nicht allzu oft
-
Dieser Thread wurde von Moderator/in Marc++us aus dem Forum Neuigkeiten aus der realen Welt in das Forum C++ verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
ich bin für punkt 3, c*a(n), aber so, dass der benutzer c einstellen kann.
-
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"?
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?
-
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.
-
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
-
@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?
-
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.
-
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
-
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.
-
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?
-
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.
-
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.
-
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.
-
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).
-
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.
-
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.