Ciencias de la Computación FAMAF

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Clase 6 ======

===== Mejorando al eficiencia (optimización de cómputo) =====

Vimos que hay diferentes formas de definir una misma función. Estas distintas definiciones pueden resultar muy distintas en eficiencia. Vamos a ver algunas estrategias para mejorar la eficiencia de las funciones.

==== Siendo verdaderamente recursivos en dos argumentos ====

En la clase anterior vimos la función //encuentraEstafador//, que sirve para encontrar números que se encuentran en dos listas. En nuestro ejemplo, tenemos dos listas de DNIs, una con los DNIs de personas que estén cobrando subsidio por desempleo y otra con personas que están trabajando en la municipalidad. Para encontrar a todas las personas que estén en las dos listas, podemos hacerlo de una forma muy poco eficiente:

  encuentraEstafador :: [Int] -> [Int] -> [Int]
  encuentraEstafador [] _      = []
  encuentraEstafador (x:xs) ys | existe x ys = x : encuentraEstafador xs ys
                               | otherwise   =     encuentraEstafador xs ys

Esta función es poco eficiente porque, para cada elemento de la primera lista, recorre la segunda lista entera. Para este problema, no es necesario recorrer tantas veces las listas, sino que podemos recorrer ambas listas una única vez, si las dos listas estan ordenadas con el mismo orden. Si eso es así, podemos escribir la siguiente función:

  encuentraEstafador' :: [Int] -> [Int] -> [Int]
  encuentraEstafador' [] _ = []
  encuentraEstafador' _ [] = []
  encuentraEstafador' (x:xs) (y:ys) | x < y  =     encuentraEstafador' xs (y:ys)
                                    | x > y  =     encuentraEstafador' (x:xs) ys
                                    | x == y = x : encuentraEstafador' xs ys

En esta versión, como la función es verdaderamente recursiva, tenemos dos casos base y hacemos inducción en los dos argumentos. De esta forma, vamos recorriendo las dos listas a la vez, consumiendo solamente una de las dos cabezas de lista: la menor. En el caso en que ambas sean iguales, habremos encontrado un estafador y lo concatenamos al resultado. Así nos evitamos recorrer toda la segunda lista para cada uno de los elementos de la primera.

Para garantizar que las listas estén ordenadas, podemos hacerlo de dos formas: con una función que compruebe si las listas están ordenadas o con una función que las ordene.

Podemos comprobar que la segunda versión de la función es más eficiente que la primera usando el comando //:set +s// en Hugs:

<code>
Main> :set +s
</code>

Este comando nos permite ver cuántos pasos de reducción y celdas de memoria se han usado en la ejecución de cada función. Para desactivarlo, basta con introducir el comando //:set -s// en Hugs.

Vemos que las funciones //encuentraEstafador// y //encuentraEstafador'// no se comportan exactamente como esperábamos: en el caso de listas con muy pocos elementos, //encuentraEstafador// llega a ser incluso más eficiente que //encuentraEstafador'//. Sin embargo, //encuentraEstafador'// es más eficiente cuanto más largas son las listas con las que trabajamos.

==== Explotando el absorbente ====

Otra forma de optimizar el cómputo es cortando la recursión en el momento en que el resultado queda determinado y no puede ser cambiado en ninguna iteración posterior de la función, independientemente de los valores que la función encuentre. Eso pasa típicamente cuando se encuentra el valor absorbente del operador que estemos usando.

Recordemos que el absorbente es el contrario exacto del neutro: para una determinada operación binaria, aplicar la operación a cualquier valor y el absorbente devuelve siempre el absorbente.

Veamos un ejemplo con la función //existe//. Cuando la habíamos definido con recursión clásica, la definimos así:

  existe :: Eq a => a -> [a] -> Bool
  existe a [] = False
  existe a (x:xs) = x == a || existe a xs

o bien, usando foldr:

  existe' :: Eq a => a -> [a] -> Bool
  existe' a xs = foldr (||) False (map (igual a) xs)
    where 
      igual :: Eq a => a -> a -> Bool
      igual x y = x == y

Sin embargo, hay una forma más eficiente de definirla:

  existe'' :: Eq a => a -> [a] -> Bool
  existe'' a [] = False
  existe'' a (x:xs) | (x == a) == True  = True
                    | (x == a) == False = existe'' a xs

De esta forma, la recursión se corta en dos casos: cuando llegamos al final, en que se devuelve el neutro (//False//) o cuando encontramos al absorbente (//True//). En el caso recursivo no se acumula ningún resultado, aunque esta función es un acumulador, ya que sabemos de antemano que sólo puede haber dos resultados: el neutro o el absorbente, y tenemos definidos los casos en que nos va a devolver el uno o el otro.

Podemos aplicar esta estrategia de optimización para los casos de acumuladores con un absorbente: la multiplicación, el paratodo (que es un //&&// generalizado).

En el caso concreto de Haskell, este tipo de optimización no es especialmente eficiente, por la forma como funciona Haskell, sin embargo, esta estrategia dá muy buena optimización para otros lenguajes.



===== Tipos definidos por el usuario =====

Para este apartado vamos a usar las filminas de [[http://www.lcc.uma.es/~pacog/|Paco Gutiérrez]] sobre [[http://www.lcc.uma.es/~pacog/apuntes/pd/cap04.pdf|definiciones de tipo]] y [[http://www.lcc.uma.es/~pacog/apuntes/pd/cap05.pdf|el sistema de clases de Haskell]].

===== Ejercicios de repaso =====


==== Recursión en dos argumentos ====

* Definir la función //segmentoInicial :: Int -> [a] -> [a]//, que dado un natural //n// y una lista //[a]//, devuelve los //n// primeros elementos de la lista.

* Definir la función //subsegmento :: Int -> Int -> [a] -> [a]//, que dados dos naturales //i// y //j//, devuelve el segmento de la lista que se encuentra entre las posiciones //i// y //j// de la lista, ambos inclusive. Para ello, usar la función //segmentoInicial// y una modificación de la función //nesimo//.

* Definir la función //combina :: Ord a => [a] -> [a] -> [a]//, que dadas dos listas nos devuelve una lista que combina las dos anteriores con sus elementos ordenados de menor a mayor. Implementen diferentes estrategias para obtener los elementos ordenados: ordenar las listas de antemano y después combinarlas (en una estrategia similar a //encuentraEstafador''//), ordenar la lista resultante, o comprobar si están ordenadas.

* Definir la función //eliminaDuplicados :: [a] -> [a]//, que elimina los elementos duplicados de una lista.

* Definir la función //fusiona :: Ord a => [a] -> [a] -> [a]//, que dadas dos listas nos devuelve una lista que combina las dos anteriores con sus elementos ordenados de menor a mayor, sin duplicados.

* Definir la función //esPalindromo :: [a] -> Bool//, que dada una lista nos dice si es un palíndromo, es decir, si es igual leída de izquierda a derecha que de derecha a izquierda.

* Definir la función //divideEnDos :: Int -> [a] -> ([a],[a])//, que divide una lista en dos, donde la longitud de la primera viene dada por el primer argumento de la función.