for - c++ vector or array

Problema de rendimiento para vector:: tamaño() en un bucle

Question

Hola cuando tengo un vector<int> var; for(int i=0; i< var.size();i++) , ¿se llama a la función size() cada vez o solo una vez?

de las respuestas, supongo que es mejor usar iteradores, o simplemente tener variables antes del ciclo

Answer 1

Como otros han dicho

• la semántica debe ser como si se llamara cada vez
• probablemente esté en línea, y probablemente sea una función simple

encima de los cuales

• un optimizador suficientemente inteligente puede deducir que es un bucle invariante sin efectos secundarios y eludirlo por completo (esto es más fácil si el código está en línea, pero puede ser posible incluso si no lo es si el compilador realiza la optimización global)

Answer 2

La función de miembro size() se invoca cada vez, pero sería una implementación realmente mala que no se alinearía, y una extraña en la que no sería un acceso simple de un dato fijo o una resta de dos punteros.
De todos modos, no debe preocuparse con tales trivialidades hasta que haya perfilado su aplicación y descubra que esto es un cuello de botella.

Sin embargo, a lo que debes prestarle atención es a lo siguiente:

1. El tipo correcto para el índice de un vector es std::vector<T>::size_type .
2. Hay tipos (algunos iteradores, por ejemplo) donde i++ puede ser más lento que ++i .

Por lo tanto, el ciclo debería ser:

for(vector<int>::size_type i=0; i<var.size(); ++i)
  ...

Answer 3

Pero podría hacerse de esta manera (siempre que este ciclo solo tenga la intención de leer / escribir sin cambiar realmente el tamaño de un vector):

for(vector<int>::size_type i=0, size = var.size(); i < size; ++i) 
{
//do something
}

En el ciclo anterior, solo tiene una llamada para clasificar independientemente del tamaño que tenga o no.

Answer 4

Probado para 900k iteraciones Su tiempo toma 43 segundos para el tamaño pre-calculado y 42 segundos para usar la llamada size ().

Si el tamaño del vector garantizado no cambia en el ciclo, mejor utilizar el tamaño precalculado; de lo contrario, no hay otra opción y debe usar size ().

#include <iostream>
#include <vector>

using namespace std;

int main() {
vector<int> v;

for (int i = 0; i < 30000; i++)
        v.push_back(i);

const size_t v_size = v.size();
for(int i = 0; i < v_size; i++)
        for(int j = 0; j < v_size; j++)
                cout << "";

//for(int i = 0; i < v.size(); i++)
//      for(int j = 0; j < v.size(); j++)
//              cout << "";
}

Answer 5

Se ''llama'' cada vez, pero puse el llamado en comillas porque realmente es solo una llamada al método en línea, por lo que no tiene que preocuparse por su rendimiento.

¿Por qué no usar vector<int>::iterator lugar?

Answer 6

Se debe invocar cada vez porque size () puede devolver un valor diferente cada vez.

Por lo tanto, no hay una gran elección, simplemente debe ser.

Answer 7

como otros dijeron, el compilador decidirá qué hacer con el código real escrito. La cifra clave es que se llama cada vez. Pero si desea obtener un impulso en el rendimiento, es mejor escribir su código con algunas consideraciones. Tu caso es uno de ellos, hay otros también, como la diferencia entre estos dos códigos:

for (int i = 0 ; i < n ; ++i)
{
   for ( int j = 0 ; j < n ; ++j)
       printf("%d ", arr[i][j]);
   printf("/n");
}
for (int j = 0 ; j < n ; ++j)
{
   for ( int i = 0 ; i < n ; ++i)
       printf("%d ", arr[i][j]);
   printf("/n");
}

La diferencia es que el primero no cambiará demasiado la página de ram por referencias, pero el otro agotará su caché y TLB y otras cosas.

¡También en línea no ayudará tanto! porque el orden de la función de llamada permanecerá como n (tamaño del vector) veces. Sin embargo, ayuda en algunos lugares, pero lo mejor es reescribir el código.

¡Pero! si quieres dejar que un compilador haga sus optimizaciones sobre tu código, NUNCA lo pongas volátil, así:

for(volatile int i = 0 ; i < 100; ++i)

Impide que el compilador optimice. Si necesita otra pista para el uso del rendimiento, regístrese en lugar de volátil.

for(register int i = 0 ; i < 100; ++i)

El compilador intentará no mover i de los registros de la CPU a la RAM. No está garantizado que pueda hacerlo, pero lo hará lo mejor;)

Answer 8

En teoría , se llama cada vez, desde un ciclo for:

for(initialization; condition; increment)
    body;

se expande a algo así como

{
    initialization;
    while(condition)
    {
        body;
        increment;
    }
}

(observe las llaves, porque la inicialización ya está en un alcance interno)

En la práctica , si el compilador comprende que una parte de su condición es invariable durante toda la duración del ciclo y no tiene efectos secundarios , puede ser lo suficientemente inteligente como para sacarlo. Esto se realiza rutinariamente con strlen y cosas por el estilo (que el compilador conoce bien) en bucles donde su argumento no está escrito.

Sin embargo, debe tenerse en cuenta que esta última condición no siempre es trivial para probar; en general, es fácil si el contenedor es local para la función y nunca pasa a funciones externas; si el contenedor no es local (por ejemplo, se pasa por referencia, incluso si es const ) y el cuerpo del bucle contiene llamadas a otras funciones, el compilador a menudo tiene que suponer que tales funciones pueden alterarlo, bloqueando el cálculo del largo.

Hacer esa optimización a mano es útil si sabes que una parte de tu condición es "costosa" de evaluar (y esa condición por lo general no lo es, ya que generalmente se reduce a una resta del puntero, que seguramente está en línea).

Editar: como dijeron otros, en general con contenedores es mejor usar iteradores, pero para el vector s no es tan importante, porque se garantiza que el acceso aleatorio a los elementos a través del operator[] es O (1); de hecho, con vectores, generalmente es una suma de puntero (vector base + índice) y desreferencia frente al incremento de puntero (elemento anterior + 1) y desreferencia de iteradores. Dado que la dirección de destino sigue siendo la misma, no creo que pueda obtener algo de los iteradores en términos de localidad de caché (y aun si es así, si no está caminando grandes arreglos en bucles apretados ni siquiera debería notar tales tipo de mejoras).

Para las listas y otros contenedores, en cambio, usar iteradores en lugar de acceso aleatorio puede ser realmente importante, ya que usar el acceso aleatorio puede significar andar cada vez que la lista, mientras que incrementar un iterador es solo una referencia del puntero.

Answer 9

Creo que si el compilador puede deducir concluyentemente que la variable var no se modifica dentro del "cuerpo del ciclo"

for(int i=0; i< var.size();i++) { 
    // loop body
}

entonces lo anterior puede transponerse a algo equivalente a

const size_t var_size = var.size();
for( int i = 0; i < var_size; i++ ) { 
    // loop body
}

Sin embargo, no estoy absolutamente seguro, así que los comentarios son bienvenidos :)

También,

• En la mayoría de las situaciones, la función miembro de size() está en línea, por lo que el problema no justifica preocuparse

• La preocupación es quizás igualmente aplicable al end() que siempre se usa para el bucle basado en iteradores, es decir, it != container.end()

• Considere usar size_t o vector<int>::size_type para el tipo de i [Vea el comentario de Steve Jessop a continuación.]