Ich habe eine Funktion, die einen Zeiger auf char-Array und Segmentgröße als Eingabeargumente verwendet und eine andere Funktion aufruft, die ein std::array<std::string> benötigt. Die Idee ist, dass das Eingabe-Char-Array in gleiche Teile "unterteilt" und ein String-Array gebildet wird.
Das Eingabe-char-Array-Format besteht aus mehreren kleineren Arrays (oder Strings) mit bestimmter Größe, die miteinander verknüpft sind. Diese werden nicht als nullterminiert angenommen, obwohl sie es sein könnten. Beispiele für Segmentgröße 5 und Anzahl der Elemente 10:
%Vor%Die Länge aller Char-Arrays ist 51 (Segment * Elemente + 1). Mein Ziel ist es, die Funktion Ressourcen effizient zu nutzen, vor allem Ausführungszeit.
Da es viele Möglichkeiten gibt, eine Katze zu häuten, habe ich zwei (oder drei) Möglichkeiten, dies anzugehen, und die Frage ist: Was ist "besser"? Damit meine ich schneller und weniger Ressourcenverschwendung. Ich bin kein Profi, also sei geduldig mit mir.
Hier wird values vorallokiert und dann jeder Zeichenfolge ein Wert zugewiesen.
Hier wird der Vektor nicht zugewiesen, aber bei jeder Wiederholung wird eine neue Zeichenfolge hinzugefügt.
%Vor%Es könnte einen dritten Weg geben, das ist besser. Ich bin nicht so erfahren mit Vektoren, also weiß ich es nicht genau. Machen die Segmentlänge und die Anzahl der Elemente einen Unterschied, wenn sie normalerweise groß (5, 10) oder klein (100, 10000) sind?
Erster Beitrag, großer Fan:)
Bessere Leistung wird erreicht, wenn dynamische Neuzuordnung vermieden wird. Versuchen Sie also, den Vektorspeicher groß genug zu halten, um alle Elemente zu empfangen.
Ihre erste Lösung wird effizienter sein, denn wenn nSize größer als die Standard-Vektorkapazität ist, benötigt der zweite eine Neuzuweisung, um alle Elemente speichern zu können.
Wie von Melkon kommentiert, ist reserve noch besser:
Es gibt mehrere Möglichkeiten, Daten zu einem Vektor hinzuzufügen:
push_back() -Elemente hinein. reserve() , dann push_back() elements zu. n elements, verwenden Sie Indizierung und Kopierzuweisung. emplace_back() -Elemente hinein. reserve() , dann emplace_back() elements zu. Es gibt andere Wege, z.B. Erstellen des Containers mit einem Iteratorpaar oder Füllen mit Standardbibliotheksalgorithmen. Ich werde diese hier nicht berücksichtigen.
Die folgenden zwei Überlegungen sind wichtig für die folgende Analyse:
Andere Faktoren beeinflussen auch die Effizienz der gewählten Lösung, aber dies sind wichtige Faktoren, auf die wir direkte Kontrolle haben. Andere Faktoren können durch das Profilieren Ihres Codes offensichtlich werden.
Jedes push_back() copy - Konstruiert ein Element im Vektor vom Argument zum Aufruf push_back() . Wenn der Vektor size() == capacity() ist, wird eine Neuzuweisung durchgeführt. Dies wird normalerweise (aber möglicherweise nicht immer) die Kapazität verdoppeln und dazu führen, dass alle der vorhandenen Elemente in neuen Speicher kopiert werden.
Die Verwendung von reserve() weist genügend Speicherplatz für die Elemente zu, bevor wir beginnen. Es lohnt sich immer, dies zu tun, wenn Sie die Anzahl der Elemente kennen oder schätzen. Wenn Sie raten, sind Überschätzungen besser als unterschätzt.
Der push_back() Aufruf verwendet immer noch den Kopierkonstruktor des Elementtyps, aber es sollte keine Zuweisung geben, da der Platz bereits vergeben ist. Sie zahlen nur die Kosten für eine einzelne Zuweisung während des Aufrufs reserve() . Wenn Sie die vorhandene Kapazität überschreiten, wird push_back() neu zugewiesen, wodurch die Kapazität häufig verdoppelt wird. Aus diesem Grund ist eine Überschätzung für die Größe besser; Es ist weniger wahrscheinlich, dass Sie eine Neuzuweisung erhalten, während Sie mit einer Unterschätzung nicht nur wahrscheinlich neue Zuweisungen vornehmen, sondern auch Speicherplatz verschwenden, der fast doppelt so viel wie nötig zuweist!
Beachten Sie, dass das Verhalten "Doubling-Kapazität" nicht vom Standard angegeben wird. Es handelt sich jedoch um eine allgemeine Implementierung, die die Häufigkeit der Neuzuweisung verringert, wenn push_back() für Datensätze unbekannter Größe verwendet wird.
Hier erstellen wir einen Vektor mit der korrekten Anzahl der standardmäßig konstruierten Elemente und verwenden dann den Kopierzuweisungsoperator, um sie durch die gewünschten Elemente zu ersetzen. Dies hat nur eine Zuweisung, kann aber langsam sein, wenn die Kopierzuweisung etwas kompliziert macht. Dies funktioniert nicht wirklich für Datensätze von unbekannter (oder nur erratener) Größe; Die Indexierung von Elementen ist nur dann sicher, wenn Sie wissen, dass der Index nie size() überschreitet, und Sie müssen auf push_back() zurückgreifen oder die Größe ändern, wenn Sie mehr benötigen. Dies ist keine gute allgemeine Lösung, aber es kann manchmal funktionieren.
emplace_back() erstellt das Element direkt mit den Argumenten für den emplace_back() -Aufruf. Dies kann oft schneller sein als das Äquivalent push_back() (aber nicht immer). Es reserviert immer noch im selben Muster wie push_back() , reserviert etwas Kapazität, füllt sie und weist sie neu zu, wenn mehr benötigt wird. Ein Großteil des gleichen Arguments gilt, aber Sie können einige Vorteile durch die Konstruktionsmethode erzielen.
Dies sollte Ihre Einstiegsstrategie für C ++ 11 oder spätere Codebasen sein. Sie erhalten die emplace_back() Effizienz (wo möglich) und vermeiden wiederholte Zuteilungen. Von den aufgeführten Mechanismen wird erwartet, dass dies in den meisten Fällen am schnellsten ist.
Effizienz kann auf verschiedene Arten gemessen werden. Die Ausführungszeit ist ein gängiges Maß, aber nicht immer das relevanteste. Allgemeiner Hinweis darüber, welche Strategie zu verwenden ist, basiert auf Erfahrung und im Wesentlichen "im Durchschnitt" der verschiedenen Effekte, um einige vernünftige Aussagen darüber zu geben, was zuerst zu tun ist. Wenn Effizienz für Ihre Anwendung von entscheidender Bedeutung ist, können Sie nur sicher sein, dass Sie den richtigen Ort optimieren, indem Sie Ihren Code profilieren , Änderungen vornehmen und dann profile es erneut zu zeigen, dass die Änderungen die gewünschte Wirkung hatten. Verschiedene Datentypen, Hardware, E / A-Anforderungen usw. können diese Art von Timing beeinflussen, und Sie werden nie wissen, wie diese Effekte in Ihrer speziellen Anwendung kombiniert werden, bis Sie profile .
Live-Beispiel: Ссылка
In diesem Beispiel fülle ich einen Vektor mit 10.000 Strings mit jedem der oben aufgeführten Ansätze. Ich zähle jedes Mal und drucke die Ergebnisse.
Das ist ähnlich wie Ihre Frage, aber nicht identisch. Ihre Ergebnisse werden sich unterscheiden!
Beachten Sie, dass emplace_back() mit reserve() am schnellsten ist, aber die Indizierung & amp; Zuweisung ist auch hier schnell. Dies liegt wahrscheinlich daran, dass std::string ein effizientes swap() hat und sein Standardkonstruktor nicht viel bewirkt. Die anderen Ansätze sind eine Größenordnung langsamer.
Ergebnisse:
%Vor% Bei den meisten neuen Codes sollte die Verwendung von reserve() und emplace_back() (oder push_back() für älteren Code) eine gute erste Annäherung für die Effizienz geben. Wenn es nicht genug ist, profilieren Sie es und finden Sie heraus, wo der Engpass ist. Es wird wahrscheinlich nicht sein, wo du denkst, dass es ist.
Verwenden Sie keine Klammern, um den Standardkonstruktor aufzurufen.
push_back erfordert bei jeder Überschreitung der Kapazität zusätzliche Neuzuweisungen. Daher kann Option 2 verbessert werden, indem ausreichend Speicherplatz reserviert wird, um Neuzuweisungen zu vermeiden. Es ist auch effizienter, die Saite direkt zu drücken, als eine leere Saite zu schieben und später erneut zuzuweisen. Und es gibt einen Konstruktor für std::string , der sehr praktisch für Ihre Bedürfnisse ist: aus der Sequenz (5)
string (const char* s, size_t n);
Zu Option 1: Vorabzuordnen des gesamten Vektors erfordert, dass jedes Element einmal für die Initialisierung und noch einmal für die Zuweisung konstruiert wird. Besser reservieren, ohne Elemente zu konstruieren und direkt push_back , die Sie wirklich wollen.
Dies ist der Code, der diese Verbesserungen verwendet:
%Vor%Machen Sie einfach, was leichter zu lesen und zu pflegen ist. Oft ist es sowieso die schnellste Lösung.
Und selbst wenn es nicht der schnellste ist, wen interessiert das? Vielleicht ist deine App 1% langsamer.