¿Cuál es la manera más rápida para restablecer todos los valores de un std::vector<int> a 0 y de mantenimiento de los vectores de tamaño inicial ?

Un bucle for con el operador []?

  • std::relleno
  • «Más rápido», como en el rendimiento? O como en las más fáciles de implementar y mantener?

6 Comentarios

  1. 298
    std::fill(v.begin(), v.end(), 0);
    • Buscando en la asamblea de salida, gcc en realidad se desenrolla este bucle en el uso de los registros mmx para volcar en 16 bytes al mismo tiempo hasta que se pone cerca de la final. Yo diría que es bastante rápido. El memset versión salta a memset, que supongo que es tan rápido. Me gustaría utilizar su método.
    • Pero, al saltar a memset es una sola instrucción, de modo que se traducirá en un menor tamaño del binario.
    • esto no es exactamente lo OP que se piden, pero simplemente reasignación de su vector de uno nuevo del mismo tamaño (v = std::vector<int>(vec_size,0)) parece ligeramente más rápido que fill en mi máquina
    • Este es el más idiomáticas forma de hacerlo, más idiomáticas de uso de assign.
    • ¿de asignar a un nuevo vector de hacer la asignación del montón ? y luego descartar la asignación de los existentes vector ? Pude ver que ser más lenta que memset et al
  2. 139

    Como siempre cuando te preguntan acerca de forma más rápida: Medir! El uso de los Métodos de arriba (en un Mac con 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    |

    el uso de 100000 iteraciones en un vector de 10000 ints.

    Edición: Si el cambiar este número de posibilidades de cambios de la resultante de las veces usted puede tener algunos confianza (no tan buena como la inspección de la final de la asamblea de código) que la referencia artificial no ha sido optimizado del todo. Por supuesto que es mejor para messure el rendimiento bajo condiciones reales.
    final de Edición

    para hacer referencia al código utilizado:

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

    Conclusión: uso std::fill (porque, como han dicho otros de sus más idiomáticas)!

    • +1. Este particular punto de referencia no es concluyente, pero el punto es absolutamente correcto, usted debe escribir una prueba de rendimiento de las alternativas que en realidad va a ser utilizado. Si no hay diferencia de rendimiento, a continuación, el uso de lo que es el más simple de origen.
    • «… no es concluyente …» IMO esta inconclusión. en sí ya es un buen punto para hacer puntos de referencia, más a menudo que no, el Optimizador ya hace un trabajo muy bueno para el tipo de situaciones que el OP se le preguntó acerca. Y me gustaría modificar la última frase «Si no hay importante diferencia de rendimiento …»
    • Por «no concluyente» quiero decir que sólo porque eran todos la misma velocidad en este programa no necesariamente significa que todos sean de la misma velocidad en el interrogador del programa. Aparte de cualquier otra cosa, usted necesita estar seguro de que la memoria era en realidad el cero – que podría ser el optimizador era lo suficientemente inteligente para engañar a la prueba. Pero ya que usted no tiene el interrogador del programa, que no es una falta de esta respuesta 🙂 Y tienes toda la razón, es muy fácil pasar el tiempo agonizando por una elección que en realidad no hace ninguna diferencia en absoluto (o una insignificante diferencia) una vez optimizado.
    • +1: editado la respuesta a la dirección de su muy observaciones pertinentes.
    • donde la vector.assign, que existe expresamente para este propósito?
    • ACTUALIZACIÓN Con Nonius para puntos de referencia: clang3.6-libc++-c++1y-O3, gcc4.9-c++1y-O3 y gcc5-c++1y-O3TL;DR: assign es más lento, excepto para pequeñas capacidades en libc++. CÓDIGO coliru/pegar
    • ¿Qué acerca de la nueva «para cada» sintaxis? for (auto& elem : v) elem = 0; Mi entendimiento es que los compiladores pueden tomar los extremos de las libertades en la optimización de este tipo de bucles, es todavía muy idiomático, y que no se basa en std::fill (de hecho, ya que puede ser implementado en una plantilla para alguna de escritura de la iterable clase, ni siquiera se basan en el estándar de la biblioteca).
    • También, wow, si te preocupa la velocidad sin optimizaciones (que podría ser plausible si se va a implementar en el modo «debug», que algunos equipos lo hacen), fill ve terrible. Es dos órdenes de magnitud más lento en esta prueba.
    • assign me parece más significativo de la API y no hay ninguna razón debe ser más lento que fill, así que voy a considerar la posibilidad de que un problema en la aplicación. Y también es más rápido que el fill de depuración así que prefiero de todos modos.
    • tal vez .assign es más lento debido a que se contempla (a través de las oraciones condicionales) si para cambiar el tamaño del vector. En ese sentido std::fill es más idiomático porque no toma un argumento con el tamaño. Debe haber un .assign(Value) función.
    • un enlace de verificación no puede costar casi el 0,5 segundos en comparación con los otros métodos, y por supuesto, el no cambiar el tamaño de caso debe ser favorecida en la aplicación.
    • en el gcc implementación de STL, assign consiste en dos condicionales (comparando a size y capacity) y si el caso es favorable, se llama std::fill_n y e internos erase_at_end (lo que sin duda implica un adicional condicional).
    • No es que el relleno es terrible, es una plantilla y se genera el código con -O0 dentro de su unidad de traducción. Cuando se utiliza memset, usted está utilizando la libc de código que se compila con -O3 (incluso cuando se compila el código con -O0). Si te preocupa la velocidad en la depuración y el uso de plantillas, usted tendrá que utilizar explícita de ejecución de plantilla en un archivo separado que compilar con -O3
    • Eso es una gran ayuda de insight. Gracias.

  3. 24

    Cómo sobre la assign función de miembro?

    some_vector.assign(some_vector.size(), 0);
    • El OP quería restablecer los valores existentes, pero su respuesta es mejor cuando se quiere cambiar el tamaño de y restablecer los valores. Gracias!
  4. 12

    Si es sólo un vector de enteros, me gustaría probar primero:

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

    No es muy C++, así que estoy seguro de que alguien va a proporcionar la forma adecuada de hacerlo. 🙂

    • Dado que la norma (2003 TC1) garantiza que un std::vector es contiguas en la memoria, este debe estar bien. Si su biblioteca de c++ no se ajusta a la de 2003 TC1, a continuación, no hacen uso de esta.
    • Yo no hubiera publicado esta a menos de que era cierto y que se supone conocido, por supuesto. 🙂 Pero gracias.
    • He comprobado la asamblea. El ::std::fill método se expande a algo que es bastante darned rápido, aunque un poco en el código bloaty lado ya que todo está en línea. Me gustaría usarlo, porque aunque es mucho más agradable de leer.
    • Es mejor añadir comprobar si el vector está vacío y no hacer nada en este caso. El cálculo de &buf[0] para el vector vacío puede generar aseveraciones en STL código.
  5. 4

    intentar

    std::fill

    y también

    std::size siz = vec.size();
    //no memory allocating
    vec.resize(0);
    vec.resize(siz, 0);
    • cambiar el tamaño es muy bonito
  6. 2

    Tenía la misma pregunta pero se acerca bastante corto vector<bool> (afaik el estándar permite implementar internamente de manera diferente que un continuo matriz de booleanos de los elementos). Por lo tanto he repetido el modificado ligeramente las pruebas por Fabio Fracassi. Los resultados son como sigue (los tiempos, en 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

    Así que al parecer para estos tamaños, vector<bool>::assign() es más rápido. El código utilizado para las pruebas:

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

    He utilizado GCC 7.2.0 compilador en Ubuntu 17.10. La línea de comandos para compilar:

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

Dejar respuesta

Please enter your comment!
Please enter your name here