Ventajas de la pereza en el problema de los k menores elementos
Una característica singular de Haskell es su carácter perezoso, frente al impaciente de la mayoría de los restantes lenguajes.
Los lenguajes perezosos usan evaluación perezosa; es decir, al evaluar una expresión evalúan sus argumentos sólo cuando los necesita. De manera opuesta, en la evaluación impaciente los argumentos de las expresiones se evalúan antes que las expresiones.
En esta entrada presento un ejercicio para Informática (del Grado de Matemáticas) con objeto de resaltar la ventaja de la evaluación perezosa de Haskell frente a la evaluación impaciente de Maxima. Para ello compararé sus rendimientos al calcular los k primeros elementos de una lista con definiciones semejantes en Haskell y Maxima.
El ejercicio en Haskell es el siguiente
|
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 |
-- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.List -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- menores :: Ord a => Int -> [a] -> [a] -- tal que (menores k xs) es la lista de los k menores elementos de -- xs. Por ejemplo, -- menores 3 [9,7,2,6,5,4,6,8] == [2,4,5] -- --------------------------------------------------------------------- menores :: Ord a => Int -> [a] -> [a] menores k xs = take k (sort xs) -- --------------------------------------------------------------------- -- Ejercicio 2. Determinar los tiempos empleados en calcular las -- siguientes expresiones -- menores 3 [1..1000000] -- length (sort [1..1000000]) -- A la vista de los resultados anteriores, deducir si para calcular -- (menores 3 [1..1000000]) se calcula (sort [1..1000000]). -- --------------------------------------------------------------------- -- Solución: Los cáculos son -- *Main> :set +s -- *Main> menores 3 [1..1000000] -- [1,2,3] -- (2.77 secs, 180963472 bytes) -- *Main> length (sort [1..1000000]) -- 1000000 -- (6.42 secs, 521957272 bytes) -- -- Por tanto, para calcular (menores 3 [1..1000000]) no se calcula -- (sort [1..1000000]). |
El ejercicio en Maxima es el siguiente
|
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 |
/* --------------------------------------------------------------------- * Ejercicio 1. Definir la función take tal que take(n,xs) es la lista * de los n primeros elementos de xs. Por ejemplo, * take(3,[2,5,4,7,6]) = [2, 5, 4] * ------------------------------------------------------------------ */ take(n,xs) := rest(xs,n-length(xs))$ /* --------------------------------------------------------------------- * Ejercicio 2. Definir la función menores tal que menores(k,xs) es la * lista de los k menores elementos de xs. Por ejemplo, * menores(3,[9,7,2,6,5,4,6,8]) = [2,4,5] * ------------------------------------------------------------------ */ menores(k,xs) := take(k,sort(xs))$ /* --------------------------------------------------------------------- * Ejercicio 2. Determinar los tiempos empleados en calcular las * siguientes expresiones (con las definiciones compiladas): * menores(3,makelist(i,i,1,1000000))$ * sort (makelist(i,i,1,1000000))$ * ------------------------------------------------------------------ */ /* Solución: * (%i4) compile(all)$ * (%i5) showtime : true$ * Evaluation took 0.0000 seconds (0.0000 elapsed) * (%o5) true * (%i6) menores(3,makelist(i,i,1,1000000)); * Evaluation took 94.1800 seconds (94.4900 elapsed) * (%i7) sort (makelist(i,i,1,1000000))$ * Evaluation took 93.0800 seconds (93.4500 elapsed) */ |
Como se observa, el tiempo que usa Haskell para calcular los 3 menores elementos de una lista de 1000000 elementos (2.77 segundos) es mucho menor que el tiempo necesario para ordenarla (6.42 segundo). En cambio, el tiempo de Maxima para calcular los 3 menores elementos (94.18 segundos) es ligeramente superior al tiempo de ordenarla (93.08 segundos).