UNIVERSIDAD DE GRANADA ´ E.T.S. DE INGENIER´IAS INFORMATICA y DE ´ TELECOMUNICACION
Departamento de Ciencias de la Computaci´ on e Inteligencia Artificial
Teor´ıa de Algoritmos Manual de Eficiencia
Curso 2008-2009 Segundo Curso de Ingeniero T´ecnico en Inform´atica de Gesti´on Segundo Curso de Ingeniero T´ecnico en Inform´atica de Sistemas
Cap´ıtulo 1 EFICIENCIA 1.
Objetivo
El objetivo de estas sesiones es que el/la alumno/a comprenda la importancia de analizar la eficiencia de los algoritmos y se familiarice con las formas de llevarlo a cabo. Para ello se mostrar´a c´omo realizar un estudio te´orico y emp´ırico de un algoritmo. Este estudio ser´a requerido en el resto de pr´acticas de la asignatura.
2.
C´ alculo del Tiempo Te´ orico
A partir de la expresi´on del algoritmo, se aplicar´an las reglas conocidas para contar el n´ umero de operaciones que realiza un algoritmo. Este valor ser´a expresado como una funci´on de T (n) que dar´a el n´ umero de operaciones requeridas para un caso concreto del problema caracterizado por tener un tama˜ no n. En los casos de algoritmos recursivos aparecer´a una expresi´on del tiempo de ejecuci´on con forma recursiva, que habr´a de resolver con las t´ecnicas estudiadas (por ejemplo, resoluci´on de recurrencias por el m´etodo de la ecuaci´on caracter´ıstica). El an´alisis que nos interesa ser´a el del peor caso. As´ı, tras obtener la expresi´on anal´ıtica de T (n), calcularemos el orden de eficiencia del algoritmo empleando la notaci´on O(·). A continuaci´on se muestran algunos ejemplos. Su implementaci´on, junto con m´as algoritmos de ejemplo, se encuentra en la p´agina web de la asignatura.
2.1.
Ejemplo 1: Algoritmo de Ordenaci´ on Burbuja
Vamos a obtener la eficiencia te´orica del algoritmo de ordenaci´on burbuja. Para ello vamos a considerar el siguiente c´odigo que implementa la ordenaci´on de un vector de enteros, desde la posici´on inicial a final de ´este, mediante el m´etodo burbuja. La mayor parte del tiempo de ejecuci´on se emplea en el cuerpo del bucle interno. Esta porci´on de c´odigo lo podemos acotar por una constante a. Por lo tanto las l´ıneas de 8-12 se ejecutan exactamente un n´ umero de veces de (final-1)-(i+1)+1, es decir, final-i-1. A su vez el bucle interno se ejecuta una serie de veces indicado por el bucle externo. En
1
2 C´alculo del Tiempo Te´orico
2
1 void burbuja ( int T [ ] , int i n i c i a l , int f i n a l ) 2 { 3 int i , j ; 4 int aux ; 5 6 for ( i = i n i c i a l ; i < f i n a l − 1 ; i ++) 7 for ( j = f i n a l − 1 ; j > i ; j −−) 8 i f (T[ j ] < T[ j −1]) { 9 aux = T[ j ] ; 10 T[ j ] = T[ j − 1 ] ; 11 T[ j −1] = aux ; 12 } 13 } definitiva tendr´ıamos una f´ormula como la siguiente: f inal−2 f inal−1
X
X
a
(1.1)
i=inicial j=i+1
Renombrando en la ecuaci´on (1.1) f inal como n e inicial como 1, pasamos a resolver la siguiente ecuaci´on: n−2 X n−1 X
a
(1.2)
i=1 j=i+1
Realizando la sumatoria interior en (1.2) obtenemos: n−2 X
a(n − i − 1)
(1.3)
i=1
Y finalmente tenemos:
a 2 3a n − n+a (1.4) 2 2 n + a ∈ O(n2 ) Claramente a2 n2 − 3a 2 Diremos por tanto que el m´etodo de ordenaci´on burbuja es de orden O(n2 ) o cuadr´atico.
2.2.
Ejemplo 2: Algoritmo de Ordenaci´ on Mergesort
En este ejemplo vamos a calcular la eficiencia del algoritmo de ordenaci´on Mergesort que ser´a aplicado siempre y cuando tengamos un n´ umero de enteros en el vector mayor de UMBRAL_MS a ser ordenado, en otro caso se aplicar´a el algoritmo de ordenaci´on burbuja. El algoritmo Mergesort divide en dos partes iguales el vector y aplica el algoritmo Mergesort recurrente a cada una de estas partes, una vez hecho esto fusionar´a los dos vectores sobre el vector original de manera que esta parte ya queda ordenada. Como
2 C´alculo del Tiempo Te´orico
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
void f u s i o n ( int T [ ] , int i n i c i a l , int f i n a l , int U [ ] , int V [ ] ) { int j = 0 ; int k = 0 ; for ( int i = i f (U[ j ] T[ i ] j ++; } else { T[ i ] k++; }
i n i c i a l ; i < f i n a l ; i ++) < V[ k ] ) { = U[ j ] ;
= V[ k ] ;
} void m e r g e s o r t ( int T [ ] , int i n i c i a l , int f i n a l ) { i f ( f i n a l − i n i c i a l < UMBRAL MS) burbuja (T, i n i c i a l , f i n a l ) ; else { int k = ( f i n a l − i n i c i a l ) / 2 ; int ∗ U = new int [ k − i n i c i a l + 1 ] ; a s s e r t (U==0); int l , l 2 ; for ( l = 0 , l 2 = i n i c i a l ; l < k ; l ++, l 2 ++) U[ l ] = T[ l 2 ] ; U[ l ] = INT MAX ; int ∗ V = new int [ f i n a l − k + 1 ] ; a s s e r t (V==0); for ( l = 0 , l 2 = k ; l < f i n a l − k ; l ++, l 2 ++) V[ l ] = T[ l 2 ] ; V[ l ] = INT MAX ; m e r g e s o r t (U, 0 , k ) ; m e r g e s o r t (V, 0 , f i n a l − k ) ; f u s i o n (T, i n i c i a l , f i n a l , U, V ) ; delete [ ] U; delete [ ] V; } }
3
2 C´alculo del Tiempo Te´orico
4
hemos dicho antes, si el n´ umero de elementos del vector que se est´a tratando en cada momento de la recursi´on es menor que UMBRAL_MS se ordenar´a mediante el algoritmo burbuja. Una vez entendido el procedimiento Mergesort vamos a pasar a obtener la eficiencia te´orica de ´este. Suponiendo que entramos por la rama else (l´ınea 21) podemos acotar la secuencia de instrucciones de las l´ıneas 22-25 por una constante. Sin perder generalidad, vamos a tomar esta constante como c. El bucle for de la l´ınea 27 se ejecuta un n´ umero de veces igual a n (en la primera llamada de mergesort tomaremos inicial como 0 y final como n), por lo 2 tanto la eficiencia hasta aqu´ı ser´ıa O(n). Este mismo razonamiento lo tenemos para las instrucciones desde la l´ınea 30 hasta 37. Aplicando la regla del m´aximo obtendr´ıamos hasta la l´ınea 37 un orden de O(n). A continuaci´on, se hacen dos llamadas de forma recursiva a mergesort (l´ıneas 38 y 39) con los dos nuevos vectores construidos para ordenar en cada uno de ellos n2 elementos. En la l´ınea 40 se llama al procedimiento fusion que como se puede observar tiene una eficiencia de O(n). Por lo tanto, para averiguar la eficiencia de mergesort podemos formular la siguiente ecuaci´on: ½ 2T ( n2 ) + n si n ≥ U M BRAL M S (1.5) T (n) = n2 si n < U M BRAL M S Vamos a resolver la recurrencia en (1.5): n T (n) = 2T ( ) + n si n ≥ U M BRAL M S 2 Haciendo en (1.6) el cambio de variable n = 2m obtenemos lo siguiente: T (2m ) = 2T (2m−1 ) + 2m
si
m ≥ log2 (U M BRAL M S)
T (2m ) − 2T (2m−1 ) = 2m
(1.6)
(1.7) (1.8)
notando T (2m ) = tm obtenemos tm − 2tm−1 = 2m
(1.9)
La ecuaci´on de recurrencia que se deduce de (1.9) es: (x − 2)2 = 0
(1.10)
Por lo tanto, la soluci´on general ser´a: tm = c1 2m + c2 m2m
(1.11)
deshaciendo el cambio de variable que hicimos en (1.6) obtenemos: tn = c1 n + c2 n log2 n Por lo tanto tn ∈ O(n log2 n).
(1.12)
3 C´alculo de la Eficiencia Emp´ırica
5
En este ejemplo cabe preguntarse por qu´e hemos hecho uso de un algoritmo de ordenaci´on de orden cuadr´atico (l´ınea 20), como es la eficiencia del algoritmo burbuja de ordenaci´on, para el caso base cuando el algoritmo Mergesort es m´as eficiente. La respuesta se ver´a cuando se exponga la t´ecnica de resoluci´on de problemas “Divide y Vencer´as”. De momento solamente indicar que el algoritmo de ordenaci´on burbuja a pesar “de ser cuadr´atico” es lo suficientemente eficiente para aplicarlo sobre un vector con pocos elementos, como se da en este caso con un valor de UMBRAL_MS lo suficientemente peque˜ no. Tambi´en apreciar´eis que los algoritmos recursivos a igual orden de eficiencia son menos eficientes que los algoritmos iterativos (hacen uso de llamadas recursivas donde internamente se debe gestionar una pila para guardar los valores de las variables en cada recursi´on).
3.
C´ alculo de la Eficiencia Emp´ırica
Se trata de llevar a cabo un estudio puramente emp´ırico. Es decir, estudiar experimentalmente el comportamiento del algoritmo. Para ello mediremos los recursos empleados (tiempo) para cada tama˜ no dado de las entradas. En el caso de los algoritmos de ordenaci´on el tama˜ no viene dado por el n´ umero de componentes del vector a ordenar. En otro tipo de problemas, como es el caso del algoritmo para obtener el factorial de un n´ umero o la sucesi´on de fibonacci, la eficiencia depender´a del valor del entero. Para obtener el tiempo emp´ırico de una ejecuci´on de un algoritmo lo que vamos a hacer es definir en el c´odigo dos variables como las siguientes: c l o c k t tantes , tdespues ; De esta forma, en la variable tantes capturamos el valor del reloj antes de la ejecuci´on del algoritmo al que queremos medir el tiempo. La variable tdespues contendr´a el valor del reloj despu´es de la ejecuci´on del algoritmo en cuesti´on. As´ı, si deseamos obtener el tiempo del algoritmo de ordenaci´on burbuja tendremos que poner algo parecido a lo siguiente: // Captura e l v a l o r d e l r e l o j a n t e s de l a l l a m a d a a b u r b u j a t a n t e s=c l o c k ( ) ; // Llama a l a l g o r i t m o de o r d e n a c i o n b u r b u j a burbuja (T, 0 , n ) ; // Captura e l v a l o r d e l r e l o j d e s p u e s de l a e j e c u c i o n de b u r b u j a t d e s p u e s=c l o c k ( ) ; Para obtener el n´ umero de segundos simplemente emitiremos un mensaje como ´este: cout <<((double ) ( t d e s p u e s −t a n t e s ) ) /CLOCKS PER SEC<<e n d l ; Con esta instrucci´on lo que hacemos es obtener la diferencia entre los dos instantes y pasarlo a segundos mediante la constante CLOCKS_PER_SEC. Para hacer uso de estas sentencias ten´eis que usar la biblioteca ctime.
3 C´alculo de la Eficiencia Emp´ırica
6
Para casos muy peque˜ nos, el tiempo medido es muy peque˜ no, por lo que el resultado ser´a 0 segundos. Estos tiempos tan peque˜ nos se pueden medir de forma indirecta ejecutando la sentencia que nos interesa muchas veces y despu´es dividiendo el tiempo total por el n´ umero de veces que se ha ejecutado. Por ejemplo: #include ... c l o c k t tantes , tdespues ; double t i e m p o t r a n s c u r r i d o ; const int NUM VECES=10000; int i ; tantes = clock ( ) ; for ( i =0; i burbuja.dat while ($i < 10000) echo -n "$i " >> burbuja.dat ./burbuja $i >> burbuja.dat @ i += 100 end As´ı en esta macro se va a escribir en el fichero burbuja.dat el tiempo en segundos que tarda el algoritmo de ordenaci´on en ordenar vectores de 10 a 10000 elementos. Las muestras se han tomado de 100 en 100. Para poder ejecutar esta macro deb´eis de darle a ´esta permisos de ejecuci´on. Por ejemplo, mediante la siguiente sentencia: chmod +x macro y a continuaci´on ejecutar la macro como
4 C´omo Mostrar los Datos
7
./macro NOTA: Cuando redact´eis un informe sobre la eficiencia emp´ırica de un algoritmo deber´an aparecer todos los detalles relevantes al proceso de medida: tipo de ordenador utilizado, compilador empleado, opciones de compilaci´on, etc.
4.
C´ omo Mostrar los Datos
Para mostrar la eficiencia emp´ırica haremos uso de tablas que recojan el tiempo invertido para cada caso o bien podemos hacer uso de gr´aficas. Para mostrar los datos en gr´afica pondremos en el eje X (abscisa) el tama˜ no de los casos y en el eje Y (ordenada) el tiempo, medido en segundos, requerido por la implementaci´on del algoritmo. Para hacer esta representaci´on de los datos podemos hacer uso del software grace (xmgrace). Este software trabaja sobre LINUX aunque ha sido exportado a plataformas como Windows 2000/NT/XP. Pod´eis encontrarlo en http://plasma-gate.weizmann. ac.il/Grace/.
4.1.
XMGRACE
El programa se inicia mediante xmgrace. Al ejecutar el programa os debe aparecer una ventana como la que se muestra en la figura 1.1. (Todas las im´agenes que se muestran a continuaci´on fueron obtenidas con la versi´on de xmgrace 5.1).
Figura 1.1: Inicio de xmgrace
4 C´omo Mostrar los Datos
8
A continuaci´on debemos introducir el fichero donde tenemos almacenados los datos emp´ıricos. Esto se puede ver c´omo se realiza en las figuras 1.2 y 1.3.
Figura 1.2: Abrir un fichero ASCII La gr´afica se podr´a representar como se muestra en la figura 1.4. Para salvar el plot debemos irnos a File>Print Setup como se muestra en la figura 1.5. A continuaci´on le damos el nombre al fichero de salida y el formato de imagen en que queremos salvarlo. En la figura 1.6 se ha salvado la gr´afica sobre el fichero burbuja.jpg en formato JPEG. Finalmente debemos pulsar FILE>Print.
4.2.
C´ alculo de la Eficiencia H´ıbrida
El c´alculo te´orico del tiempo de ejecuci´on de un algoritmo nos da mucha informaci´on. Es suficiente para comparar dos algoritmos cuando los suponemos aplicados a casos de tama˜ no arbitrariamente grande. Sin embargo, cuando se va a aplicar el algoritmo en una situaci´on concreta, es decir, especificadas la implementaci´on, el compilador utilizado, el ordenador sobre el que se ejecuta, etc., nos interesa conocer de la forma m´as exacta posible la ecuaci´on del tiempo. As´ı, el c´alculo te´orico nos da la expresi´on general, pero asociada a cada t´ermino de esta expresi´on aparece una constante de valor desconocido. Para describir completamente la ecuaci´on del tiempo, necesitamos conocer el valor de esas constantes. La forma de averiguar estos valores es ajustar la funci´on a un conjunto de puntos. En nuestro caso, la funci´on es la que resulta del c´alculo te´orico, el conjunto de puntos lo forman los resultados del an´alisis emp´ırico y para el ajuste emplearemos regresi´on por
4 C´omo Mostrar los Datos
9
Figura 1.3: Seleccionar y representar gr´aficamente los datos m´ınimos cuadrados. Por ejemplo en el algoritmo de ordenaci´on la funci´on que vamos a ajustar a los puntos obtenidos en el c´alculo de la eficiencia emp´ırica ser´a: T (n) = ao · x2 + a1 · x + a2 Al ajustar a los puntos obtenidos por m´ınimos cuadrados obtendremos los valores de a0 , a1 y a2 es decir las constantes ocultas.
4.3.
C´ omo Obtener las Constantes Ocultas
Para facilitar la labor del ajuste, emplearemos el programa xmgrace. Para ello nos iremos al men´ u que se muestra en la figura 1.7. A continuaci´on introduciremos la forma funcional de T (n) e indicaremos qu´e n´ umero de constantes ocultas tiene. En la figura 1.8 se puede ver que hemos introducido a0*x^2+a1*x+a2 y hemos dado un n´ umero de constantes ocultas igual a 3. A continuaci´on le damos al bot´on on Apply y default aparecer´a una ventana como la que se muestra en la figura 1.9. En esta ventana se muestra qu´e valores han adoptado las constantes ocultas adem´as de obtener informaci´on de estad´ısticos como Chi-cuadrado, el coeficiente de correlaci´on, el error cuadr´atico medio, entre otros. De entre estos estad´ısticos podemos quedarnos con el coeficiente de correlaci´on. De tal forma que el coeficiente de correlaci´on cuanto m´as se aproxime a 1 mejor ajuste representa. Simult´aneamente se representa la gr´afica que se obtiene con T (n) ya con los valores que hemos ajustado para las constantes ocultas.
4 C´omo Mostrar los Datos
10
Figura 1.4: Gr´afica con los tiempo del algoritmo Burbuja
Figura 1.5: Exportar la gr´afica
4 C´omo Mostrar los Datos
Figura 1.6: Salvar la gr´afica en formato jpeg
Figura 1.7: C´omo realizar el ajuste de las constantes ocultas
11
4 C´omo Mostrar los Datos
12
Figura 1.8: Introducir T(n) y el n´ umero de constantes ocultas
Figura 1.9: Valores de las constantes ocultas y datos estad´ısticos de la bondad del ajuste