Najszybszy sposób na zresetowanie każdej wartości std :: vector <int> na 0


Odpowiedzi:


340
std::fill(v.begin(), v.end(), 0);

48
Patrząc na dane wyjściowe asemblera, gcc faktycznie rozwija tę pętlę i używa rejestrów mmx do zrzucania 16 bajtów jednocześnie, aż zbliży się do końca. Powiedziałbym, że to dość szybko. Wersja zestawu przeskakuje do zestawu, który, jak sądzę, jest równie szybki. Użyłbym twojej metody.
Wszechobecny

Ale przejście do memset jest pojedynczą instrukcją, więc użycie go spowoduje mniejszy rozmiar pliku binarnego.
Alexander Shishenko,

2
nie jest to dokładnie to, o co poprosił OP, ale po prostu ponowne przypisanie wektora do nowego tego samego rozmiaru ( v = std::vector<int>(vec_size,0)) wydaje się nieco szybsze niż fillna mojej maszynie
Yibo Yang,

1
Jest to najbardziej idiomatyczny sposób robienia tego, bardziej idiomatyczny niż używanie assign.
alfC

1
czy przypisanie go do nowego wektora powoduje alokację sterty? a następnie odrzucić przydział istniejącego wektora? Widziałem, że jest wolniejszy niż memset i wsp.
Conrad Jones

150

Jak zawsze, gdy pytasz o najszybszy: Zmierz! Korzystając z powyższych metod (na Macu z Clangiem):

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    |

przy użyciu 100000 iteracji na wektorze 10000 int.

Edit: Jeśli zmiana spowoduje to zmiany liczby przekonująco wynikające razy można mieć trochę zaufania (nie tak dobre jak inspekcji końcowej kod montaż), że punktem odniesienia sztuczny nie został zoptymalizowany z dala całkowicie. Oczywiście najlepiej zepsuć wydajność w rzeczywistych warunkach. koniec Edytuj

dla odniesienia wykorzystany kod:

#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;
}

Wniosek: użyj std::fill(ponieważ, jak inni powiedzieli, jest najbardziej idiomatyczny)!


3
+1. Ten konkretny test porównawczy nie jest rozstrzygający, ale kwestia jest absolutnie słuszna, powinieneś napisać test wydajności alternatyw, ponieważ będą one faktycznie wykorzystane. Jeśli nie ma różnicy w wydajności, użyj dowolnego z najprostszych źródeł.
Steve Jessop

3
„... nie rozstrzygające ...” IMO ta niejednoznaczność sama w sobie jest już dobrym punktem do robienia testów, częściej niż Optymalizator już wykonuje bardzo dobrą pracę w sytuacjach, o które pytał PO. I zmodyfikowałbym twoje ostatnie zdanie, aby brzmiało „Jeśli nie ma znaczącej różnicy w wydajności ...”
Fabio Fracassi,

4
UPDATE za pomocą noniusza punkty odniesienia: clang3.6-libc ++ - C ++ 1r-O3 , gcc4.9-c ++ 1r-O3 i gcc5-c ++ 1r-O3 - TL, DR : assignwolniej, z wyjątkiem niewielkich pojemnościach na libc++. KOD coliru / paste
patrz

2
Ponadto, wow, jeśli zależy Ci na szybkości bez optymalizacji (co może być prawdopodobne, jeśli wdrażasz w trybie „debugowania”, co robią niektóre zespoły), fillwygląda okropnie. W tym teście jest on o dwa rzędy wielkości wolniejszy.
Kyle Strand

5
@KyleStrand: To nie jest tak, że wypełnienie jest okropne, to szablon, a kod jest generowany z -O0 w twojej jednostce tłumaczeniowej. Kiedy używasz memset, używasz kodu libc, który został skompilowany z -O3 (nawet jeśli kompilujesz swój kod z -O0). Jeśli zależy Ci na szybkości debugowania i korzystasz z szablonów, będziesz musiał użyć jawnej instancji szablonu w osobnym pliku, który skompilujesz z -O3
Tic

25

A co z assignfunkcją członka?

some_vector.assign(some_vector.size(), 0);

2
OP chciał zresetować istniejące wartości, ale twoja odpowiedź jest lepsza, gdy chcesz zmienić rozmiar i zresetować wartości. Dzięki!

15

Jeśli to tylko wektor liczb całkowitych, najpierw spróbuję:

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

To nie jest bardzo C ++, więc jestem pewien, że ktoś zapewni odpowiedni sposób na zrobienie tego. :)


3
Ponieważ standard (2003 TC1) gwarantuje, że std :: wektor jest ciągły w pamięci, to powinno być w porządku. Jeśli twoja biblioteka c ++ nie jest zgodna z TC1 2003, nie używaj jej.
Mario

2
@Mario: Nie opublikowałbym tego, gdyby to nie była prawda i oczywiście założono, że jest dobrze znana. :) Ale dzięki.
odpręż się

1
Sprawdziłem zespół. ::std::fillSposób rozszerza się do czegoś, co jest całkiem cholernie szybko, choć nieco na stronie kodowej bloaty ponieważ wszystko inline. Nadal bym go używał, ponieważ jest o wiele ładniej czytać.
Wszechobecny

4
Lepiej dodaj sprawdzenie, czy wektor jest pusty i nic nie rób w tym przypadku. Obliczanie & buf [0] dla pustego wektora może generować twierdzenia w kodzie STL.
Siergiej

4

próbować

std::fill

i również

std::size siz = vec.size();
//no memory allocating
vec.resize(0);
vec.resize(siz, 0);

zmiana rozmiaru jest bardzo ładna
Nick

3

Miałem to samo pytanie, ale dość krótkie vector<bool>(afaik standard pozwala na implementację go wewnętrznie inaczej niż tylko ciągły zestaw elementów boolowskich). Dlatego powtórzyłem nieco zmodyfikowane testy Fabio Fracassi. Wyniki są następujące (czasy, w sekundach):

            -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

Więc najwyraźniej dla tych rozmiarów vector<bool>::assign()jest szybszy. Kod użyty do testów:

#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;
}

Użyłem kompilatora GCC 7.2.0 na Ubuntu 17.10. Wiersz poleceń do kompilacji:

g++ -std=c++11 -O0 main.cpp
g++ -std=c++11 -O3 main.cpp
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.