A maneira mais rápida de redefinir todos os valores de std :: vector <int> para 0

198

Qual é a maneira mais rápida de redefinir todos os valores de a std::vector<int>para 0 e manter o tamanho inicial do vetor?

Um loop for com o operador []?

Matthieu Riegler
fonte
4
std :: fill
Andriy Tylychko
1
"Mais rápido" como no desempenho? Ou como é mais fácil de implementar / manter?
TheGeneral 4/17/17

Respostas:

340
std::fill(v.begin(), v.end(), 0);
Cat Plus Plus
fonte
48
Observando a saída do assembly, o gcc realmente desenrola esse loop no uso dos registradores mmx para despejar em 16 bytes por vez até chegar perto do fim. Eu diria que é muito rápido. A versão do memset pula para o memset, o que eu acho que é tão rápido. Eu usaria seu método.
omniforme
Porém, pular para o memset é uma única instrução, portanto, usá-lo resultará em um tamanho binário menor.
Alexander Shishenko 12/10
2
este não é exatamente o OP pediu, mas simplesmente a reatribuição seu vetor para um novo do mesmo tamanho ( v = std::vector<int>(vec_size,0)) parece um pouco mais rápido do que fillna minha máquina
Yibo Yang
1
Esta é a maneira mais idiomática de fazê-lo, mais idiomática do que usar assign.
AlfC1
1
atribuí-lo a um novo vetor faz alocação de heap? e depois descartar a alocação do vetor existente? Eu pude ver que sendo mais lento que Memset e cols.
Conrad Jones
150

Como sempre, quando você pergunta sobre o mais rápido: meça! Usando os métodos acima (em um Mac usando 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    |

usando 100000 iterações em um vetor de 10000 ints.

Editar: se a alteração desses números altera de maneira plausível os tempos resultantes, você pode ter alguma confiança (não tão boa quanto a inspeção do código de montagem final) de que o benchmark artificial não foi totalmente otimizado. Obviamente, é melhor medir o desempenho em condições reais. end Editar

para referência o código usado:

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

Conclusão: use std::fill(porque, como outros já disseram que é o mais idiomático)!

Fabio Fracassi
fonte
3
+1. Esse benchmark específico não é conclusivo, mas o ponto é absolutamente correto: você deve escrever um teste de desempenho das alternativas, pois elas serão realmente usadas. Se não houver diferença de desempenho, use a fonte mais simples.
21812 Steve Steveop
3
"... não conclusivo ..." Na IMO, essa inconclusividade já é um bom ponto para se fazer benchmarks; na maioria das vezes, o Optimizer já faz um trabalho muito bom para o tipo de situação sobre a qual o OP perguntou. E eu modificar a sua última frase para ler "Se não há significativa diferença de desempenho ..."
Fabio Fracassi
4
ATUALIZAÇÃO Usando Nonius para benchmarks: clang3.6-libc ++ - c ++ 1y-O3 , gcc4.9-c ++ 1y-O3 e gcc5-c ++ 1y-O3 - TL; DR : assigné mais lento, exceto por pequenas capacidades em diante libc++. CODE coliru / paste
veja
2
Além disso, uau, se você se preocupa com a velocidade sem otimizações (o que pode ser plausível se você estiver implantando no modo 'debug', o que algumas equipes fazem), fillparece terrível. São duas ordens de magnitude mais lentas neste teste.
Kyle Strand
5
@KyleStrand: Não é que o preenchimento seja terrível, é um modelo e o código é gerado com -O0 dentro da sua unidade de tradução. Quando você usa o memset, você está usando o código libc que foi compilado com -O3 (mesmo quando você compila seu código com -O0). Se você se preocupa com a velocidade na depuração e usa modelos, precisará usar instanciação explícita de modelos em um arquivo separado, que você compila com -O3
Tic
25

E a assignfunção de membro?

some_vector.assign(some_vector.size(), 0);
fredoverflow
fonte
2
O OP queria redefinir os valores existentes, mas sua resposta é melhor quando você deseja redimensionar e redefinir os valores. Obrigado!
15

Se é apenas um vetor de números inteiros, eu tentaria primeiro:

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

Não é muito C ++, por isso tenho certeza de que alguém fornecerá a maneira correta de fazer isso. :)

descontrair
fonte
3
Como o padrão (2003 TC1) garante que um vetor std :: seja contíguo na memória, isso deve ser bom. Se sua biblioteca c ++ não estiver em conformidade com o TC1 de 2003, não use isso.
Mario
2
@ Mario: Eu não teria postado isso a menos que isso fosse verdade e assumisse ser bem conhecido, é claro. :) Mas obrigado.
desenrole
1
Eu verifiquei a montagem. O ::std::fillmétodo se expande para algo bastante rápido, embora um pouco do lado do código, já que está tudo em linha. Eu ainda o usaria porque é muito melhor ler.
omniforme
4
É melhor adicionar uma verificação se o vetor estiver vazio e não fazer nada nesse caso. Calcular & buf [0] para vetor vazio pode gerar asserções no código STL.
Sergey
4

experimentar

std::fill

e também

std::size siz = vec.size();
//no memory allocating
vec.resize(0);
vec.resize(siz, 0);
nttstar
fonte
redimensionamento é muito agradável
Nick
3

Eu tinha a mesma pergunta, mas bastante curta vector<bool>(depois que o padrão permite implementá-lo internamente de maneira diferente do que apenas uma matriz contínua de elementos booleanos). Por isso, repeti os testes levemente modificados por Fabio Fracassi. Os resultados são os seguintes (tempos, em segundos):

            -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

Então, aparentemente, para esses tamanhos, vector<bool>::assign()é mais rápido. O código usado para testes:

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

Eu usei o compilador GCC 7.2.0 no Ubuntu 17.10. A linha de comando para compilar:

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