reserva vectorial C++

Question

Tengo un vector multidimensional muy grande que cambia de tamaño todo el tiempo. ¿Hay algún punto para usar la función vector.reserve() cuando solo conozco una buena aproximación de los tamaños?

Así que básicamente tienen un vector

A[256*256][x][y]

donde x va de 0 a 50 para cada iteración en el programa y luego de vuelta a 0 de nuevo. Los valores y pueden variar cada vez, lo que significa que para cada uno de los elementos [256*256][y], el vector y puede ser de un tamaño diferente pero aún más pequeño que 256;

Así que para aclarar mi problema esto es lo que tengo:

vector<vector<vector<int>>> A; 
for(int i =0;i<256*256;i++){ 
    A.push_back(vector<vector<int>>()); 
    A[i].push_back(vector<int>()); 
    A[i][0].push_back(SOME_VALUE); 
} 

añadir elementos al vector ...

A.clear(); 

Y después de esto hacer lo mismo otra vez desde la parte superior.

Cuándo y cómo debo reservar espacio para los vectores. Si lo he entendido correctamente, ahorraría mucho tiempo si utilizara la reserva ya que cambio los tamaños todo el tiempo.

¿Cuál sería el lado negativo/positivo de reservar el tamaño máximo que mi vector puede tener que sería [256*256][50][256] en algunos casos.

BTW. Soy consciente de las diferentes plantillas de la matriz y Boost, pero he decidido ir con vectores en éste ...

EDIT: También me preguntaba cómo utilizar la función de reserva en matrices multidimensionales. Si solo reservo el vector en dos dimensiones, ¿se copiará todo si supero su capacidad en la tercera dimensión?

Answer 1

Para ayudar con la discusión se puede considerar los siguientes typedefs:

typedef std::vector<int> int_t; // internal vector 
typedef std::vector<int_t> mid_t; // intermediate 
typedef std::vector<mid_t> ext_t; // external 

El coste de crecimiento (aumento de la capacidad del vector) int_t sólo afectará a los contenidos de este vector en particular y no afectará a ningún otro elemento. El costo de crecer mid_t requiere copiar todos los elementos almacenados en ese vector, es decir, requerirá todo el vector int_t, que es bastante más costoso. El costo de crecer ext_t es enorme: se requerirá copiar todos los elementos ya almacenados en el contenedor.

Ahora, para aumentar el rendimiento, sería mucho más importante obtener el tamaño correcto de ext_t (parece fijo 256 * 256 en su pregunta). Luego obtenga el tamaño intermedio mid_t correcto para que las reasignaciones costosas sean poco frecuentes.

La cantidad de memoria que está hablando es enorme, por lo que es posible que desee considerar formas menos estándar para resolver su problema. Lo primero que viene a la mente es agregar un nivel extra de indirección. Si en lugar de mantener los vectores reales, tienes punteros inteligentes en los vectores, puedes reducir el costo de hacer crecer los vectores mid_t y ext_t (si el tamaño de ext_t es fijo, solo usa un vector de mid_t). Ahora, esto implicará que el código que usa su estructura de datos será más complejo (o mejor, agregue un contenedor que se encargue de las indirecciones). Cada vector int_t se asignará una vez en la memoria y nunca se moverá en las reasignaciones mid_t o ext_t. El costo de reasignar mid_t es proporcional al número de vectores asignados int_t, no a la cantidad real de enteros insertados.

using std::tr1::shared_ptr; // or boost::shared_ptr 
typedef std::vector<int> int_t; 
typedef std::vector< shared_ptr<int_t> > mid_t; 
typedef std::vector< shared_ptr<mid_t> > ext_t; 

Otra cosa que se debe tener en cuenta es que std::vector::clear() no libera el espacio interno asignado en el vector, sólo destruye los objetos contenidos y establece el tamaño a 0. Es decir, llamando clear() nunca va a liberar la memoria . El patrón para liberar realmente la memoria asignada en un vector es:

typedef std::vector<...> myvector_type; 
myvector_type myvector; 
... 
myvector.swap(myvector_type()); // swap with a default constructed vector 

Answer 2

Tiene una implementación en funcionamiento pero le preocupa el rendimiento. Si su perfil muestra que es un cuello de botella, puede considerar el uso de una matriz de números enteros desnuda en lugar de vectores de vectores.

Ver how-do-i-work-with-dynamic-multi-dimensional-arrays-in-c para un ejemplo

Se puede volver a utilizar la misma asignación cada vez, realloc ing según sea necesario y, finalmente, manteniéndola en la marca de la marea alta de uso.

Si, de hecho, los vectores son el cuello de botella, el rendimiento más allá de evitar las operaciones de dimensionamiento en los vectores cada iteración de bucle será dominada por su patrón de acceso en la matriz. Intenta acceder a las órdenes más altas de forma secuencial.

Answer 3

Cada vez que se presiona un vector en otro vector, ajustar el tamaño de los vectores empujado constructor:

A.push_back(vector<vector<int>>(somesize)); 

Answer 4

Si se conoce el tamaño de un vector en el momento de la construcción, pase el tamaño y la c'tor asignar utilizando operator[] en lugar de push_back. Si no está completamente seguro sobre el tamaño final, adivine (tal vez agregue un poco más) y use reserve para que el vector reserve suficiente memoria por adelantado.

¿Cuál sería el lado negativo/positivo de reservar el tamaño máximo que mi vector puede tener que sería [256 * 256] [50] [256] en algunos casos.

Lado negativo: pérdida potencial de memoria. Lado positivo: menos tiempo de CPU, menos fragmentación de montón. Es una compensación memoria/CPU, la elección óptima depende de su aplicación. Si no tiene memoria (en la mayoría de las máquinas de consumo hay suficiente RAM), considere reservar por adelantado.

para decidir la cantidad de memoria de reserva, mirar el consumo medio de memoria, no en el pico (la reserva de 256 * 256 * 50 * 256 no es una buena idea a menos que se necesitan tales dimensiones regularmente)