Der schnellste Weg, um jeden Wert von std :: vector <int> auf 0 zurückzusetzen

198

Was ist der schnellste Weg, um jeden Wert von a std::vector<int>auf 0 zurückzusetzen und die anfängliche Größe der Vektoren beizubehalten?

Eine for-Schleife mit dem Operator []?

Matthieu Riegler
quelle
4
std :: fill
Andriy Tylychko
1
"Am schnellsten" wie in der Leistung? Oder wie am einfachsten zu implementieren / zu warten?
TheGeneral

Antworten:

340
std::fill(v.begin(), v.end(), 0);
Cat Plus Plus
quelle
48
Mit Blick auf die Assembly-Ausgabe rollt gcc diese Schleife tatsächlich in die Verwendung der mmx-Register ab, um jeweils 16 Byte zu sichern, bis sie sich dem Ende nähert. Ich würde sagen, das geht ziemlich schnell. Die Memset-Version springt zu Memset, was meiner Meinung nach ungefähr genauso schnell ist. Ich würde deine Methode anwenden.
Omnifarious
Das Springen zum Memset ist jedoch eine einzelne Anweisung, sodass die Verwendung zu einer kleineren Binärgröße führt.
Alexander Shishenko
2
Dies ist nicht genau das, wonach OP gefragt hat, aber die einfache Neuzuweisung Ihres Vektors zu einem neuen Vektor derselben Größe ( v = std::vector<int>(vec_size,0)) scheint etwas schneller zu sein als fillauf meinem Computer
Yibo Yang
1
Dies ist die idiomatischste Art, dies zu tun, idiomatischer als die Verwendung assign.
alfC
1
Hat die Zuweisung zu einem neuen Vektor eine Heap-Zuordnung? und dann die Zuordnung des vorhandenen Vektors verwerfen? Ich konnte sehen, dass es langsamer war als memset et al.
Conrad Jones
150

Wie immer, wenn Sie nach dem schnellsten fragen: Messen! Verwenden der oben genannten Methoden (auf einem Mac mit Clang):

Method      |  executable size  |  Time Taken (in sec) |
            |  -O0    |  -O3    |  -O0      |  -O3     |  
------------|---------|---------|-----------|----------|
1. memset   | 17 kB   | 8.6 kB  | 0.125     | 0.124    |
2. fill     | 19 kB   | 8.6 kB  | 13.4      | 0.124    |
3. manual   | 19 kB   | 8.6 kB  | 14.5      | 0.124    |
4. assign   | 24 kB   | 9.0 kB  | 1.9       | 0.591    |

Verwenden von 100000 Iterationen auf einem Vektor von 10000 Ints.

Edit: Wenn changeing diese Zahlen plausibel die resultierenden Zeiten ändert können Sie etwas Vertrauen (nicht so gut wie die Endmontage Code Inspektion) , dass die künstliche Benchmark nicht optimiert wurde entfernt vollständig. Natürlich ist es am besten, die Leistung unter realen Bedingungen zu beeinträchtigen. Ende Bearbeiten

als Referenz den verwendeten Code:

#include <vector>

#define TEST_METHOD 1
const size_t TEST_ITERATIONS = 100000;
const size_t TEST_ARRAY_SIZE = 10000;

int main(int argc, char** argv) {

   std::vector<int> v(TEST_ARRAY_SIZE, 0);

   for(size_t i = 0; i < TEST_ITERATIONS; ++i) {
   #if TEST_METHOD == 1 
      memset(&v[0], 0, v.size() * sizeof v[0]);
   #elif TEST_METHOD == 2
      std::fill(v.begin(), v.end(), 0);
   #elif TEST_METHOD == 3
      for (std::vector<int>::iterator it=v.begin(), end=v.end(); it!=end; ++it) {
         *it = 0;
      }
   #elif TEST_METHOD == 4
      v.assign(v.size(),0);
   #endif
   }

   return EXIT_SUCCESS;
}

Fazit: verwenden std::fill(weil, wie andere gesagt haben, es am idiomatischsten ist)!

Fabio Fracassi
quelle
3
+1. Dieser spezielle Benchmark ist nicht schlüssig, aber der Punkt ist absolut richtig. Sie sollten einen Leistungstest der Alternativen schreiben, da diese tatsächlich verwendet werden. Wenn es keinen Leistungsunterschied gibt, verwenden Sie die einfachste Quelle.
Steve Jessop
3
"... nicht schlüssig ..." IMO ist diese Unschlüssigkeit an sich schon ein guter Punkt für Benchmarks. Meistens leistet der Optimierer bereits sehr gute Arbeit für die Art von Situationen, nach denen das OP gefragt hat. Und ich würde Ihren letzten Satz dahingehend ändern, dass er lautet: "Wenn es keinen signifikanten Leistungsunterschied gibt ..."
Fabio Fracassi,
4
UPDATE Verwenden von Nonius für Benchmarks: clang3.6-libc ++ - c ++ 1y-O3 , gcc4.9-c ++ 1y-O3 und gcc5-c ++ 1y-O3 - TL; DR : assignist langsamer, mit Ausnahme kleiner Kapazitäten auf libc++. CODE coliru / paste
sehe
2
Wow, wenn Sie Wert auf Geschwindigkeit ohne Optimierungen legen (was plausibel sein kann, wenn Sie im Debug-Modus bereitstellen, was einige Teams tun), fillsieht das schrecklich aus. In diesem Test ist es zwei Größenordnungen langsamer.
Kyle Strand
5
@KyleStrand: Es ist nicht so, dass das Füllen schrecklich ist, es ist eine Vorlage und der Code wird mit -O0 in Ihrer Übersetzungseinheit generiert. Wenn Sie memset verwenden, verwenden Sie den libc-Code, der mit -O3 kompiliert wurde (auch wenn Sie Ihren Code mit -O0 kompilieren). Wenn Sie Wert auf Geschwindigkeit beim Debuggen legen und Vorlagen verwenden, müssen Sie die explizite Vorlageninstanziierung in einer separaten Datei verwenden, die Sie mit -O3
Tic
25

Wie wäre es mit der assignMitgliedsfunktion?

some_vector.assign(some_vector.size(), 0);
Fredoverflow
quelle
2
Das OP wollte vorhandene Werte zurücksetzen, aber Ihre Antwort ist besser, wenn Sie die Größe ändern und die Werte zurücksetzen möchten . Vielen Dank!
15

Wenn es nur ein Vektor von ganzen Zahlen ist, würde ich zuerst versuchen:

memset(&my_vector[0], 0, my_vector.size() * sizeof my_vector[0]);

Es ist nicht sehr C ++, daher bin ich sicher, dass jemand den richtigen Weg dafür finden wird. :) :)

entspannen
quelle
3
Da der Standard (2003 TC1) garantiert, dass ein std :: vector im Speicher zusammenhängend ist, sollte dies in Ordnung sein. Wenn Ihre c ++ - Bibliothek nicht mit dem 2003 TC1 übereinstimmt, verwenden Sie diese nicht.
Mario
2
@Mario: Ich hätte das nicht gepostet, wenn das nicht wahr wäre und natürlich als bekannt angenommen worden wäre. :) Aber danke.
Entspannen Sie am
1
Ich habe die Baugruppe überprüft. Die ::std::fillMethode erweitert sich zu etwas, das verdammt schnell ist, wenn auch etwas Code-aufgebläht, da alles inline ist. Ich würde es trotzdem benutzen, weil es viel schöner zu lesen ist.
Omnifarious
4
Sie sollten besser hinzufügen, ob der Vektor leer ist, und in diesem Fall nichts tun. Das Berechnen von & buf [0] für einen leeren Vektor kann Zusicherungen im STL-Code erzeugen.
Sergey
4

Versuchen

std::fill

und auch

std::size siz = vec.size();
//no memory allocating
vec.resize(0);
vec.resize(siz, 0);
nttstar
quelle
Größe ändern ist sehr schön
Nick
3

Ich hatte die gleiche Frage, aber ziemlich kurz vector<bool>(afaik erlaubt der Standard, sie intern anders zu implementieren als nur ein kontinuierliches Array von booleschen Elementen). Daher wiederholte ich die leicht modifizierten Tests von Fabio Fracassi. Die Ergebnisse sind wie folgt (Zeiten in Sekunden):

            -O0       -O3
         --------  --------
memset     0.666     1.045
fill      19.357     1.066
iterator  67.368     1.043
assign    17.975     0.530
for i     22.610     1.004

Also anscheinend für diese Größen vector<bool>::assign()ist schneller. Der für Tests verwendete Code:

#include <vector>
#include <cstring>
#include <cstdlib>

#define TEST_METHOD 5
const size_t TEST_ITERATIONS = 34359738;
const size_t TEST_ARRAY_SIZE = 200;

using namespace std;

int main(int argc, char** argv) {

    std::vector<int> v(TEST_ARRAY_SIZE, 0);

    for(size_t i = 0; i < TEST_ITERATIONS; ++i) {
#if TEST_METHOD == 1
        memset(&v[0], false, v.size() * sizeof v[0]);
#elif TEST_METHOD == 2
        std::fill(v.begin(), v.end(), false);
   #elif TEST_METHOD == 3
        for (std::vector<int>::iterator it=v.begin(), end=v.end(); it!=end; ++it) {
            *it = 0;
        }
   #elif TEST_METHOD == 4
      v.assign(v.size(),false);
   #elif TEST_METHOD == 5
      for (size_t i = 0; i < TEST_ARRAY_SIZE; i++) {
          v[i] = false;
      }
#endif
    }

    return EXIT_SUCCESS;
}

Ich habe den GCC 7.2.0-Compiler unter Ubuntu 17.10 verwendet. Die Befehlszeile zum Kompilieren:

g++ -std=c++11 -O0 main.cpp
g++ -std=c++11 -O3 main.cpp
Yauhen Yakimenka
quelle