Schnellere Alternative zu push_back (Größe ist bekannt)

Question

Ich habe einen Float-Vektor. Während ich bestimmte Daten verarbeite, schiebe ich sie zurück. Ich weiß immer, wie groß die Größe sein wird, wenn ich den Vektor deklariere.

Für den größten Fall sind es 172.490.752 Schwimmer. Das dauert etwa elf Sekunden, um alles zurückzuschieben.

Gibt es eine schnellere Alternative, wie eine andere Datenstruktur oder etwas?

Answer 1

Wenn Sie die endgültige Größe kennen, dann reserve() diese Größe, nachdem Sie den Vektor deklarieren. Auf diese Weise muss nur einmal Speicher zugewiesen werden.

Außerdem können Sie mit der Verwendung emplace_back() experimentieren, obwohl ich bezweifle es wird keinen Unterschied für einen Vektor von float machen. Aber versuchen Sie es und Benchmark es (mit einem optimierten Build natürlich - Sie sind mit einem optimierten Build - richtig?).

Answer 2

::boost::container::stable_vector Beachten Sie, dass die Zuordnung eines zusammenhängenden Blocks von 172 * 4 MB leicht fehlschlagen kann und ziemlich viel Seitenjoggling erfordert. Der stabile Vektor ist im Wesentlichen eine Liste von kleineren Vektoren oder Arrays von vernünftiger Größe. Sie können es auch parallel füllen.

Answer 3

Ich habe zwei Antworten für Sie:

1. Wie schon in früheren Antworten haben darauf hingewiesen, reserve mit der Lagerung vorher zuzuteilen kann sehr hilfreich sein, aber:
2. push_back (oder emplace_back) selbst eine Leistung hat Strafe, weil sie bei jedem Aufruf prüfen müssen, ob der Vektor neu zugewiesen werden muss. Wenn Sie die Anzahl der Elemente wissen Sie bereits einsetzen wird, können Sie diese Strafe vermeiden, indem sie direkt die Elemente Einstellung der Zugriffsoperator []

So ist die effizienteste Art und Weise verwendet würde ich empfehlen ist:

1. initialisieren Sie den Vektor mit dem ‚fill'-Konstruktor:

   std::vector<float> values(172490752, 0.0f); 
   

2. Stellen Sie die Einträge direkt den Zugang Operator:

   values[i] = some_float; 
   ++i; 
   

Answer 4

Der üblicher Weg zur Beschleunigung ein vector, wenn Sie die Größe vorher wissen, ist vor der Verwendung push_backreserve darauf zu nennen. Dadurch entfällt der Aufwand für die Neuzuweisung von Speicher und das Kopieren der Daten jedes Mal, wenn die vorherige Kapazität belegt ist.

Manchmal wird dies für sehr anspruchsvolle Anwendungen nicht ausreichen. Auch wenn push_back nicht neu zugeordnet wird, muss die Kapazität jedes Mal überprüft werden. Es gibt keine Möglichkeit zu wissen, wie schlecht das ist, ohne Benchmarking, da moderne Prozessoren erstaunlich effizient sind, wenn eine Verzweigung immer/nie genommen wird.

Sie könnten versuchen, resize statt reserve und Array-Indizierung verwenden, aber die resize erzwingt eine Standardinitialisierung jedes Elements; Dies ist eine Verschwendung, wenn Sie wissen, dass Sie in jedem Element einen neuen Wert festlegen werden.Eine Alternative wäre std::unique_ptr<float[]> zu verwenden und den Speicher selbst zuzuordnen.

Answer 5

Der Grund push_back ist langsam, dass es alle Daten mehrmals kopieren muss, wie der Vektor wächst, und selbst wenn es keine Daten kopieren muss, muss es überprüfen. Vektoren wachsen schnell genug, dass dies nicht oft passiert, aber es passiert immer noch. Eine grobe Faustregel besagt, dass jedes Element im Durchschnitt ein- oder zweimal kopiert werden muss. Die früheren Elemente müssen viel mehr kopiert werden, aber fast die Hälfte der Elemente muss überhaupt nicht kopiert werden.

Sie können das Kopieren, nicht aber die Prüfungen vermeiden, indem Sie beim Erstellen des Vektors den Vektor reserve aufrufen und sicherstellen, dass genügend Speicherplatz vorhanden ist. Sie können sowohl das Kopieren als auch die Prüfungen vermeiden, indem Sie sie von Anfang an mit der richtigen Größe erstellen, indem Sie dem Vektorkonstruktor die Anzahl der Elemente geben und dann mit der Indizierung als Tobias suggested; Leider geht das auch durch den Vektor eine extra Zeit, die alles initialisiert.

Wenn Sie die Anzahl der Gleitkommazahlen zur Kompilierzeit und nicht nur zur Laufzeit kennen, können Sie eine std::array verwenden, die all diese Probleme vermeidet. Wenn du nur die Nummer zur Laufzeit kennst, würde ich Mark’s suggestion mit std::unique_ptr<float[]> nachholen. Sie würden es mit

size_t size = /* Number of floats */; 
auto floats = unique_ptr<float[]>{new float[size]}; 

erstellen Sie müssen nichts Besonderes tun, um dies zu löschen; Wenn es den Rahmen verlässt, wird es den Speicher freigeben. In den meisten Fällen können Sie es wie einen Vektor verwenden, aber es wird nicht automatisch die Größe ändern.

Answer 6

Sie konnten eine benutzerdefinierte allocator verwenden, die Standard-Initialisierung aller Elemente vermeidet, wie in this answer diskutiert, in Verbindung mit gewöhnlichem Elemente Zugang:

const size_t N = 172490752; 
std::vector<float, uninitialised_allocator<float> > vec(N); 
for(size_t i=0; i!=N; ++i) 
    vec[i] = the_value_for(i); 

Dies vermeidet (i) standardmäßig alle Elemente zu initialisieren, (ii) Überprüfen der Kapazität bei jedem Drücken und (iii) Neuzuweisung, aber gleichzeitig bewahrt alle Bequemlichkeit der Verwendung std::vector (statt std::unique_ptr<float[]>). Der Vorlagenparameter allocator ist jedoch ungewöhnlich, daher müssen Sie anstelle von std::vectorspezifischen Code generischen Code verwenden.