std::vector-Wachstum

Mr. N

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.

hustbaer

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").

Sei $X \in \mathbb{R}^+$ und $c_k = X^k$

$D\_k = X^{-k} \left(A X^k + A \sum\_{n=1}^k X^n \right)$
$= A + A X^{-k} \frac{X^{k+1}-1}{X-1}$
$= A + \frac{A}{X-1} \left( X - X^{-k} \right)$
$\leq A + \frac{A X}{X-1}$
$= \Theta(1)$

Bouncer

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.

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

Bouncer

thomas001 schrieb:

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

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

hmmm.....nein :p

Bleib lieber bei deinen Standard Trollereien Bouncer...

Badestrand

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.

Ponto

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.

pumuckl

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)

Mr. N

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?

pumuckl

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.

ChrisM

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

Mr. N

ChrisM schrieb:

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

Er darf. Muss aber nicht. Und tuts auch üblicherweise nicht.

Bouncer

Ponto schrieb:

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.

jo, das sehe ich ja ein. je grösser so ein vektor wird, desto seltener musser 'realloc' machen und hat demzufolge im durchschnitt eine bessere laufzeit als einer, der in regelmässigen abständen 'realloct'. dafür verbrät er eben mehr speicher. geschenkt gibt's nix. 'there ain't no such thing as a free lunch';)

ghorst

da es gerade so halb zum thema passt. ich las gerade hier: Qt Quarterly - Issue 19 · Q3 2006 - Inside the Qt 4 Containers das die trolle sich für problemlos verschiebbare objekte/datentypen bewusst für eine variante mit konstanter vergrößerung des arrays entschieden, da diese ein besseres laufzeitverhalten hat, da realloc bei modernen systemen nicht immer eine kopie erzeugt, sondern häufig das os lediglich die zuordnung zwischen physikalischen und logischen speicherbereichen ändert.
wenn der inhalt nicht problemlos kopierbar ist, verwenden sie nebenbei eine vergrößerung auf das 1,5fache.

stellt sich hier die frage: geht die komplexitätsbetrachtung an der realität vorbei oder haben die trolle es schlicht falsch gemacht?

hustbaer

Die trolle haben es schlicht falsch gemacht würde ich sagen

ghorst

na ohne begründung kann ich das leider nicht akzeptieren.

hustbaer

ghorst schrieb:

na ohne begründung kann ich das leider nicht akzeptieren.

Weil das Statement:

This makes sense because modern operating systems don't copy the entire data when reallocating a buffer; the physical memory pages are simply reordered, and only the data on the first and last pages need to be copied.

IMO völliger Quatsch ist.
Mit Windows geht das auf jeden Fall nicht (zumindest nicht mit realloc, wenn dann müsste man da schon die Win32 API bemühen, und nichtmal da wüsste wie man es macht bzw. ob es überhaupt geht).

Es mag sein dass es für Linux einen Allocator gibt der das kann, aber z.B. tcmalloc kann es auch nicht (und bei ptmalloc würde es mich auch sehr wundern).

Davon abgesehen finde is es etwas brutal einfach 4K anzufordern - was wenn ich bloss 10 oder 20 longs brauche? Dann verscchwendet Qt fast 4K pro Vektor. Hm...