Lab ExecTime - Tiempo de ejecución y complejidad computacional
Hay muchos factores que pueden afectar el tiempo de ejecución de un programa, tales como el patrón de acceso a memoria, los otros programas que se estén utilizando simultáneamente, el acceso a dispositivos de entrada y salida y hasta la versión y fabricante del compilador que se utilizó para generar el ejecutable. Sin embargo la mayoría de las veces el factor dominante es la complejidad en tiempo del algoritmo implementado.
En este laboratorio implementaremos algunos algoritmos y los ejecutaremos para diferentes tamaños de input para observar el efecto que tiene el tamaño del input en el tiempo de ejecución.
Midiendo tiempo de ejecución
El siguiente código muestra una manera simple de medir el tiempo transcurrido en una función en C++.
double elapsed_secs;
clock_t begin, end;
begin = clock();
foo(); //función a la que queremos medir tiempo ejecución
end = clock();
elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
La función clock() devuelve la cantidad de periodos de reloj que han transcurrido desde el comienzo del programa. Nota que en la variables begin y end estamos guardando la cantidad de períodos antes y después de la ejecución de la función foo(). Por lo tanto la resta de end - begin nos dice cuántos periodos transcurrieron durante la ejecución de foo. La constante CLOCKS_PER_SEC es el número de periodos del reloj por segundo (los GHz del procesador). Al dividir la diferencia de end y begin entre la constante CLOCKS_PER_SEC obtenemos el tiempo transcurrido.
Disclaimer: En este laboratorio mediremos tiempo de ejecución una sola vez por cada input y lo aceptamos como bueno. Sin embargo, si estuviéramos haciendo un estudio serio sobre tiempos de ejecución lo recomendable sería tomar múltiples medidas y promediar.
Todos los programas de este experimento están en https://git.ccom.uprrp.edu/rarce/ccom3034-labExecutionTime. Puedes descargarlos así:
git clone https://git.ccom.uprrp.edu/rarce/ccom3034-labExecutionTime
Al descargarlos notarás que se creó un directorio llamado ccom3034-labExecutionTime. El directorio contiene archivos de código fuente y un archivo llamado Makefile. Para compilar todos los programas y crear sus ejecutables simplemente debes dar el comando make en la línea de comando linux.
Entregables: Escribe los resultados de las diferentes pruebas y contestaciones a preguntas en un archivo. Asegúrate de escribir tu nombre y de tu compañero al principio del archivo. Genera un PDF de ese archivo y somételo a online.uprrp.edu.
Ejercicio 1:
El programa sorting.cpp crea un vector de enteros aleatorios y luego mide los tiempos de ejecución de dos algoritmos de sorting: bubble sort (que tiene complejidad ) vs. el algoritmo de sorting que provee la librería STL (que es una mezcla de quicksort y heapsort, dos de los algoritmos de sorting O( ). El tamaño del vector debe ser especificado por el usuario al ejecutar el programa así:
./sorting <tamaño del vector>.
Por ejemplo, ./sorting 10000, corre el programa y muestra cuántos segundos le tomó ordenar un vector de tamaño 10000 a bubble sort y al sort de STL.
Corre el programa para los siguientes tamaños y observa el crecimiento de ambas implementaciones. Explica cómo tus resultados evidencian la complejidad en tiempo de los dos algoritmos.
| Tamaño | Tiempo para bubblesort | Tiempo para STL sort |
|---|---|---|
| 4,000 | ||
| 8,000 | ||
| 16,000 | ||
| 32,000 |
Ejercicio 2
El programa insert.cpp compara el tiempo que toma insertar elementos al principio de un vector vs. insertar al final.
El programa requiere que pases como "command line argument" el número de elementos que deseas añadir al vector. Por ejemplo, ./insert 1000 insertará 1000 elementos a un vector originalmente vacío.
Corre el programa para los siguientes tamaños y observa el crecimiento de ambas implementaciones. Según los tiempos que obtuviste, ¿la complejidad de insertar n elementos al principio es la misma que añadir n elementos al final? Usando los resultados explica cuáles crees que son las complejidades.
| Número de inserciones | Tiempo de insertar al principio del vector | Tiempo de insertar al final del vector |
|---|---|---|
| 40,000 | ||
| 80,000 | ||
| 160,000 | ||
| 320,000 |
Ejercicio 3
El ejercicio matrix.cpp compara el tiempo de ejecución de multiplicar una matriz por un vector vs. multiplicar una matriz por otra. Para esto crea matrices y vectores del tamaño especificado y mide el tiempo necesario para multiplicarlas.
Corre el programa para los siguientes tamaños y observa el crecimiento de ambas implementaciones. La complejidad de la multiplicación matriz-vector es de orden O() mientras que la multiplicación matriz-matriz es O(). ¿Los resultados que obtuviste para los tiempos de ejecución coinciden con esos órdenes de complejidad? Explica.
| N: Tamaño de vector. Matriz es N x N. | Tiempo para multiplicación matriz - vector | Tiempo para multiplicación matriz - matriz |
|---|---|---|
| 100 | ||
| 200 | ||
| 400 | ||
| 800 |
Ejercicio 4:
El programa nHighest.cpp compara dos algoritmos para encontrar los n elementos mayores de una lista:
El primer algoritmo ordena los elementos en orden ascendente usando STL sort y luego escoge los últimos 10.
El segundo algoritmo utiliza una cola de prioridades que es un estructura de datos que tiene complejidad O() para insertar / borrar
El programa requiere que pases como "command line argument" el tamaño del vector al que hallaremos los 10 elementos mayores.
Corre el programa para los siguientes tamaños y observa el crecimiento de ambas implementaciones. Usando los resultados explica cuáles crees que son las complejidades de los algoritmos.
| Tamaño del vector | Tiempo usando sort | Tiempo usando priority queue |
|---|---|---|
| 125,000 | ||
| 250,000 | ||
| 500,000 | ||
| 1,000,000 |
Ejercicio 5
El programa search.cpp compara dos algoritmos para encontrar un elemento dentro de una lista ordenada: binary search vs. linear search.
El programa requiere que pases como "command line argument" el tamaño del vector en el que realizaremos la búsqueda.
Corre el programa para los siguientes tamaños y observa el crecimiento de ambas implementaciones. ¿Los tiempos que obtuviste, confirman que el tiempo de binary search crece de forma logarítmica y que linear search crece de forma lineal?
| Tamaño del vector | Tiempo usando binary search | Tiempo usando linear search |
|---|---|---|
| 10,000 | ||
| 20,000 | ||
| 40,000 | ||
| 80,000 |
Pregunta 1: Un programa cuya complejidad es cuadrática tomó 3 segundos para un input de tamaño 1,000.
- ¿Aproximadamente cuánto tomaría si para un input de tamaño 2,000?
- ¿Aproximadamente cuánto tomaría si para un input de tamaño 10,000?
Pregunta 2: Un programa cuya complejidad es lineal tomó 30 milisegundos para un input de tamaño 1,000.
- ¿Aproximadamente qué tamaño de input podría procesar en 120 milisegundos?
- ¿Aproximadamente qué tamaño de input podría procesar en 15 milisegundos?