Perfil de ejecución de un algoritmo

Perfil de ejecución de un algoritmo
Denominamos as’ a la pauta real de crecimiento de los recursos del sistema que demanda un algoritmo a medida que aumenta la complejidad del problema propuesto. Esta pauta habr‡ de ser medida directamente sobre la m‡quina que utilicemos, y requerir‡, por tanto, de un dise–o experimental detenido, acorde al problema que tratamos de resolver. Se definen dos tiposde perfiles: perfil temporal y perfil espacial, el primero referido al tiempo que consume nuestro algoritmo, y el segundo al espacio de memoria que demanda del sistema. Hay que notar que frecuentemente uno y otro coste est‡n relacionados y son intercambiables. As’, por ejemplo, podemos ahorrar memoria utilizando un fichero del sistema como zona de almacenamiento de datos, pero las operaciones delectura-escritura en fichero llevar‡n m‡s tiempo que las mismas operaciones en memoria, con lo que habr’amos cambiado coste espacial por coste temporal. La conclusi—n que podemos extraer de esto es que hay que examinar cuidadosamente los recursos de que disponemos antes de elegir uno u otro algoritmo, tratando siempre de explotar al m‡ximo aquel recurso que optimice alguna especificaci—n delproblema Ðpor ejemplo, que el algoritmo sea r‡pido. Antes de pasar a una prueba experimental, conviene evaluar te—ricamente los costes en tiempo y espacio de nuestro algoritmo, mediante alguna de las tŽcnicas explicadas en clase. La verificaci—n experimental de los costes obtenidos te—ricamente tiene como objetivo primario ver en quŽ medida se ajustan a la realidad las estimaciones te—ricas, perotambiŽn percibir la importancia pr‡ctica de optimizar los algoritmos Ðaœn a costa, en muchas ocasiones, de obtener soluciones aproximadas.

1.

Perfil temporal

Evidentemente, el tiempo real consumido por un programa no s—lo depender‡ de las caracter’sticas del algoritmo, sino tambiŽn de la m‡quina y de las condiciones puntuales de trabajo de la misma, que en determinados casos, debido al repartodel tiempo de c—mputo entre varios procesos, puede significar uno o m‡s grados de magnitud de diferencia entre varias ejecuciones efectuadas en momentos distintos. TambiŽn influir‡, por supuesto, la complejidad del problema, pero este aspecto forma parte del dise–o del experimento, es decir, podremos establecer varios casos Ðde diferente complejidadÐ ante los cuales evaluaremos el rendimiento decada uno de los algoritmos. El sistema operativo dispone de utilidades y funciones de la biblioteca standard que nos permiten obtener el tiempo de microprocesador asignado a la ejecuci—n de un programa o partes de un programa. Ello permitir‡ obtener una pauta m‡s o menos fiable de crecimiento del tiempo consumido en funci—n del par‡metro complejidad, y comparar entre s’ las pautas de distintosalgoritmos.

1.1.

Utilidades del sistema

En este apartado hablaremos œnicamente del comando time, cuyo œnico par‡metro es una l’nea de comando, y que proporciona el tiempo de usuario, el tiempo de sistema y el tiempo real consumidos al ejecutar dicha l’nea de comando. El tiempo de micropocesador asignado al programa es la suma de los tiempos de usuario y de sistema. El mismo

1

comandotambiŽn proporciona el porcentaje que este tiempo significa sobre el tiempo real de la ejecuci—n. A continuaci—n se muestran varios ejemplos:
luisja@sol[~/deposito/Perfiles]: time ejemplo_dinamica 6.0u 7.0s 0:18 69% 0+0k 0+0io 0pf+0w luisja@sol[~/deposito]: time find /home/luisja -name correo -print /home/luisja/correo 0.0u 1.0s 0:07 13% 0+0k 0+0io 0pf+0w luisja@sol[~/deposito/Perfiles]:ejemplo_dinamica & [1] 5995 luisja@sol[~/deposito/Perfiles]: ejemplo_dinamica & [2] 5996 luisja@sol[~/deposito/Perfiles]: time ejemplo_dinamica 5.0u 6.0s 1:27 12% 0+0k 0+0io 0pf+0w [2] + Exit 128 ejemplo_dinamica [1] + Exit 128 ejemplo_dinamica luisja@sol[~/deposito/Perfiles]: time pwd /home/luisja/deposito/Perfiles 0.0u 0.0s 0:00 0% 0+0k 0+0io 0pf+0w luisja@sol[~/deposito/Perfiles]:

El primer dato...