Warum wird push_back in C ++ - Vektoren konstant amortisiert?

Ich lerne C ++ und habe festgestellt, dass die Laufzeit für die push_back-Funktion für Vektoren konstant "amortisiert" ist. In der Dokumentation wird außerdem Folgendes angegeben: "Wenn eine Neuzuweisung erfolgt, ist die Neuzuweisung selbst in der gesamten Größe bis zu linear."

Sollte dies nicht bedeuten, dass die push_back-Funktion , wobei die Länge des Vektors ist? Schließlich interessiert uns die Worst-Case-Analyse, oder?$O(n)$$n$

Entscheidend ist, dass ich nicht verstehe, wie das Adjektiv "amortisiert" die Laufzeit verändert.

Das wichtige Wort ist hier "abgeschrieben". Amortisierte Analyse ist eine Analysetechnik, die eine Folge von Operationen untersucht. Wenn die gesamte Sequenz in läuft, läuft jede Operation in der Sequenz in . Die Idee ist, dass einige Operationen in der Sequenz zwar kostspielig sein können, jedoch nicht häufig genug, um das Programm zu beschweren. Es ist wichtig zu beachten, dass sich dies von einer durchschnittlichen Fallanalyse über eine Eingabeverteilung oder eine randomisierte Analyse unterscheidet. Die amortisierte Analyse ergab den ungünstigsten Fall für die Leistung eines Algorithmus, unabhängig von den Eingaben. Es wird am häufigsten zum Analysieren von Datenstrukturen verwendet, die im gesamten Programm einen dauerhaften Status haben.T ( n ) T ( n ) /$n$$T(n)$$T(n)/n$

Eines der häufigsten Beispiele ist die Analyse eines Stapels mit Multipop-Operationen, die Elemente platzieren. Eine naive Analyse von Multipop würde sagen, dass Multipop im schlimmsten Fall 0 Zeit in Anspruch nehmen muss, da möglicherweise alle Elemente des Stapels entfernt werden müssen. Wenn Sie sich jedoch eine Abfolge von Operationen ansehen, werden Sie feststellen, dass die Anzahl der Pops die Anzahl der Pushs nicht überschreiten kann. Daher kann die Anzahl der Pops in einer Folge von Operationen nicht überschreiten , sodass Multipop in der amortisierten -Zeit ausgeführt wird , obwohl gelegentlich ein einzelner Aufruf mehr Zeit in Anspruch nimmt.O ( n ) n O ( n ) O ( 1 $k$$O(n)$$n$$O(n)$$O(1)$

Wie hängt das nun mit C ++ - Vektoren zusammen? Vektoren werden mit Arrays implementiert. Um die Größe eines Vektors zu erhöhen, müssen Sie den Speicher neu zuweisen und das gesamte Array kopieren. Offensichtlich würden wir das nicht sehr oft tun wollen. Wenn Sie also eine push_back-Operation ausführen und der Vektor mehr Speicherplatz zuweisen muss, wird die Größe um den Faktor erhöht . Dies benötigt nun mehr Speicher, den Sie möglicherweise nicht vollständig nutzen, aber die nächsten push_back-Vorgänge werden alle in konstanter Zeit ausgeführt.$m$

Wenn wir nun die amortisierte Analyse der push_back-Operation durchführen (die ich hier gefunden habe ), werden wir feststellen, dass sie in einer konstanten amortisierten Zeit ausgeführt wird. Angenommen, Sie haben Elemente und Ihr Multiplikationsfaktor ist . Dann ist die Anzahl der Umzüge ungefähr . Die te Neuzuweisung kostet proportional zu etwa die Größe des aktuellen Arrays. Somit ist die Gesamtzeit für Zurückschieben , da es sich um eine geometrische Reihe handelt. Teilen Sie dies durch Operationen und wir erhalten, dass jede Operation$n$$m$i m i n ≤ log m ( n ) i = 1 m i ≤ n $\log_m(n)$$i$$m^i$$n$ n$\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$$n$ m1m$\frac{m}{m-1}$, eine Konstante. Zuletzt müssen Sie bei der Auswahl Ihres Faktors vorsichtig sein . Wenn es zu nahe an ist, wird diese Konstante für praktische Anwendungen zu groß, aber wenn zu groß ist, sagen wir 2, dann verschwenden Sie viel Speicher. Die ideale Wachstumsrate variiert je nach Anwendung, aber ich denke, dass einige Implementierungen .$m$$1$$m$$1.5$

Obwohl @Marc eine ausgezeichnete Analyse geliefert hat (was ich denke), ziehen es manche Leute möglicherweise vor, die Dinge aus einem etwas anderen Blickwinkel zu betrachten.

Eine Möglichkeit besteht darin, eine etwas andere Art der Neuzuweisung in Betracht zu ziehen. Anstatt alle Elemente sofort aus dem alten Speicher in den neuen Speicher zu kopieren, sollten Sie immer nur ein Element gleichzeitig kopieren. Wenn Sie also ein push_back ausführen, wird das neue Element dem neuen Bereich hinzugefügt und genau ein vorhandenes kopiert Element aus dem alten Raum in den neuen Raum. Unter der Annahme eines Wachstumsfaktors von 2 ist es ziemlich offensichtlich, dass, wenn der neue Raum voll ist, wir alle Elemente aus dem alten Raum in den neuen Raum kopiert haben und jeder push_back genau eine konstante Zeit war. Zu diesem Zeitpunkt verwerfen wir den alten Speicherplatz, weisen einen neuen Speicherblock zu, der doppelt so groß ist, und wiederholen den Vorgang.

Ziemlich klar, wir können dies auf unbestimmte Zeit fortsetzen (oder so lange Speicher verfügbar ist) und jeder Push_back würde das Hinzufügen eines neuen Elements und das Kopieren eines alten Elements beinhalten.

Eine typische Implementierung hat immer noch genau die gleiche Anzahl an Kopien - aber anstatt die Kopien einzeln zu erstellen, werden alle vorhandenen Elemente auf einmal kopiert. Einerseits haben Sie Recht: Wenn Sie sich einzelne Aufrufe von push_back ansehen, sind einige wesentlich langsamer als andere. Wenn wir uns jedoch einen langfristigen Durchschnitt ansehen, bleibt der Kopieraufwand pro Aufruf von push_back konstant, unabhängig von der Größe des Vektors.

Obwohl es für die Komplexität der Berechnung irrelevant ist, ist es meiner Meinung nach erwähnenswert, warum es vorteilhaft ist, die Dinge so zu machen, wie sie sind, anstatt ein Element pro push_back zu kopieren, damit die Zeit pro push_back konstant bleibt. Es gibt mindestens drei Gründe zu berücksichtigen.

Das erste ist einfach die Speicherverfügbarkeit. Der alte Speicher kann erst nach Abschluss des Kopiervorgangs für andere Zwecke freigegeben werden. Wenn Sie jeweils nur ein Objekt kopieren, bleibt der alte Speicherblock viel länger reserviert. In der Tat würden Sie einen alten Block und einen neuen Block im Wesentlichen die ganze Zeit zugewiesen haben. Wenn Sie sich für einen Wachstumsfaktor entscheiden, der kleiner als zwei ist (was normalerweise gewünscht wird), benötigen Sie immer noch mehr zugewiesenen Speicher.

Zweitens, wenn Sie immer nur ein altes Element kopieren würden, wäre die Indizierung in das Array etwas komplizierter. Bei jeder Indizierungsoperation müsste herausgefunden werden, ob sich das Element am angegebenen Index derzeit im alten Speicherblock oder im Speicher befindet ein neues. Das ist keineswegs besonders komplex, aber für eine elementare Operation wie das Indizieren in ein Array kann fast jede Verlangsamung von Bedeutung sein.

Drittens können Sie durch gleichzeitiges Kopieren das Caching viel besser nutzen. Wenn Sie alles auf einmal kopieren, können Sie in den meisten Fällen davon ausgehen, dass sich sowohl die Quelle als auch das Ziel im Cache befinden. Die Kosten für einen Cache-Fehler werden daher über die Anzahl der Elemente, die in eine Cache-Zeile passen, amortisiert. Wenn Sie jeweils ein Element kopieren, kann es leicht vorkommen, dass für jedes Element, das Sie kopieren, ein Cache-Fehler auftritt. Das ändert nur den konstanten Faktor, nicht die Komplexität, kann aber dennoch ziemlich bedeutend sein - für eine typische Maschine kann man leicht einen Faktor von 10 bis 20 erwarten.

Es lohnt sich wahrscheinlich auch, einen Moment über die andere Richtung nachzudenken: Wenn Sie ein System mit Echtzeitanforderungen entwerfen, ist es möglicherweise sinnvoll, immer nur ein Element anstatt aller Elemente gleichzeitig zu kopieren. Obwohl die Gesamtgeschwindigkeit möglicherweise niedriger ist (oder auch nicht), ist die Zeit, die für eine einzelne Ausführung von push_back benötigt wird, nach wie vor stark begrenzt - vorausgesetzt, Sie haben einen Echtzeit-Allokator (obwohl natürlich viele in Echtzeit) Systeme verbieten lediglich die dynamische Zuweisung von Speicher, zumindest in Teilen mit Echtzeitanforderungen.