Para cuantificar la diferencia en el rendimiento de una matriz tipo C y de vectores en C++, escribí este pequeño programa. https://github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cppC++ Array vs Vector explicación de la prueba de rendimiento
Para compararlas por motivos comunes, decidí probar tanto el acceso aleatorio como el secuencial. Agregué iteradores, solo para compararlos también (pero no es en eso en lo que se enfoca la pregunta).
Los resultados, para una máquina Linux de 64 bits con 7,7 GB de RAM con en un tamaño de matriz/vector de 1 millón son los siguientes: -
- Tiempo requerido para escribir en array. : 12.0378 ms
- Tiempo necesario para leer de la matriz de forma secuencial. : 2.48413 ms
- Tiempo necesario para leer aleatoriamente la matriz. : 37.3931 ms
- Tiempo necesario para escribir en la matriz dinámica. : 11.7458 ms
- Tiempo necesario para leer de la matriz dinámica secuencialmente. : 2.85107 ms
- Tiempo necesario para leer de la matriz dinámica aleatoriamente. : 36.0579 ms
- Tiempo necesario para escribir en el vector usando índices. : 11.3909 ms
- Tiempo necesario para leer el vector usando índices, secuencialmente. : 4.09106 ms
- Tiempo necesario para leer del vector usando índices, al azar. : 39 ms
- Tiempo necesario para escribir en el vector utilizando iteradores. : 24.9949 ms
- Tiempo necesario para leer el vector utilizando iteradores. : 18.8049 ms
El tamaño del vector se establece en el momento de la inicialización y no se altera, lo que no hay cambio de tamaño del vector (la afirmación en el programa de ayuda a verificar que). Los tiempos no incluyen los tiempos de inicialización de ninguna de las matrices asignadas estáticamente, la matriz dinámicamente asignada o el vector.
De acuerdo con las estadísticas, el tiempo para escribir en Vector es menor que el de la matriz, pero el tiempo de lectura del vector es el doble que el de la matriz.
La diferencia es bastante pequeña, pero ¿hay una explicación de por qué hay una diferencia de rendimiento? ¿Hay algo mal con la prueba? Esperaba que ambos actuaran a la misma velocidad. La repetición de esta prueba muestra la misma tendencia.
El código:
#include <vector>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <sys/time.h>
#include <cassert>
#define ARR_SIZE 1000000
using std::string;
void printtime (struct timeval& start, struct timeval& end, string str);
int main (void)
{
int arr[ARR_SIZE];
int tmp;
struct timeval start, stop;
srand (time (NULL));
/* Writing data to array */
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
arr[i] = rand();
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to write to array."));
/* Reading data from array */
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
tmp = arr[i];
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to read from array sequentially."));
/* Reading data from array randomly*/
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
tmp = arr[rand() % ARR_SIZE];
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to read from array randomly."));
int *darr = (int *) calloc (sizeof (int), ARR_SIZE);
/* Writing data to array */
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
darr[i] = rand();
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to write to dynamic array."));
/* Reading data from array */
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
tmp = darr[i];
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to read from dynamic array sequentially."));
/* Reading data from dynamic array randomly*/
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
tmp = darr[rand() % ARR_SIZE];
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to read from dynamic array randomly."));
std::vector<int> v(ARR_SIZE);
assert (v.capacity() == ARR_SIZE);
/* Writing to vector using indices*/
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
v[i] = rand();
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to write to vector using indices."));
assert (v.capacity() == ARR_SIZE);
/* Reading from vector using indices*/
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
tmp = v[i];
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to read from vector using indices, sequentially."));
/* Reading data from dynamic array randomly*/
gettimeofday (&start, NULL);
for (int i = 0; i < ARR_SIZE; i++)
{
tmp = v[rand() % ARR_SIZE];
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to read from vector using indices, randomly."));
std::vector<int> v2(ARR_SIZE);
/* Writing to vector using iterators*/
gettimeofday (&start, NULL);
std::vector<int>::iterator itr, itr_end;
for (itr = v2.begin(), itr_end = v2.end(); itr != itr_end; itr++)
{
*itr = rand();
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to write to vector using iterators."));
/* Reading from vector using iterators*/
gettimeofday (&start, NULL);
for (itr = v2.begin(), itr_end = v2.end(); itr != itr_end; itr++)
{
tmp = *itr;
}
gettimeofday (&stop, NULL);
printtime (start, stop, string ("Time taken to read from vector using iterators."));
return 0;
}
void printtime (struct timeval& start, struct timeval& end, string str)
{
double start_time, end_time, diff;
start_time = ((start.tv_sec) * 1000 + start.tv_usec/1000.0);
end_time = ((end.tv_sec) * 1000 + end.tv_usec/1000.0);
diff = end_time - start_time;
std::cout << str << " : " << diff << " ms" << std::endl;
}
EDITAR
Como se sugiere en los comentarios, aquí es más información: -
- Compilador: - g ++ - 4.5.2
- Banderas: - ninguna (es decir, valores de falla)
- Optimizaciones: - Ninguna (quería probar el comportamiento en una configuración habitual. La optimización podría variar el comportamiento del programa, por ejemplo, dado que la variable tmp nunca se utiliza, el paso de leer el vector/matriz puede omitirse o reducirse a la última asignación.Al menos eso es lo que entiendo).
¿Hay algún cambio si realiza las pruebas en orden aleatorio? – mkb
Al analizar el rendimiento, publique el 1. código y 2. las opciones del compilador. Hay demasiadas variables en juego para comenzar a adivinar, necesitamos esa información como mínimo. Ni siquiera sabemos si su prueba es válida o si tiene un tamaño de muestra lo suficientemente grande como para descartar anomalías. –
¿Está compilando en modo de lanzamiento? Con todas las optimizaciones activadas? Corriendo sin un depurador conectado? – Asik