{"id":453,"date":"2010-08-24T10:09:13","date_gmt":"2010-08-24T10:09:13","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/ventajas-de-la-pereza\/"},"modified":"2013-03-08T05:53:41","modified_gmt":"2013-03-08T05:53:41","slug":"ventajas-de-la-pereza","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/ventajas-de-la-pereza\/","title":{"rendered":"Ventajas de la pereza en el problema de los k menores elementos"},"content":{"rendered":"

\nUna caracter\u00edstica singular de Haskell<\/a> es su car\u00e1cter perezoso, frente al impaciente de la mayor\u00eda de los restantes lenguajes.<\/p>\n

\nLos lenguajes perezosos usan evaluaci\u00f3n perezosa<\/a>; es decir, al evaluar una expresi\u00f3n eval\u00faan sus argumentos s\u00f3lo cuando los necesita. De manera opuesta, en la evaluaci\u00f3n impaciente<\/a> los argumentos de las expresiones se eval\u00faan antes que las expresiones.<\/p>\n

\nEn esta entrada presento un ejercicio para Inform\u00e1tica (del Grado de Matem\u00e1ticas)<\/a> con objeto de resaltar la ventaja de la evaluaci\u00f3n perezosa de Haskell<\/a> frente a la evaluaci\u00f3n impaciente de Maxima<\/a>. Para ello comparar\u00e9 sus rendimientos al calcular los k primeros elementos de una lista con definiciones semejantes en Haskell<\/a> y Maxima<\/a>.
\n<\/p>\n

\nEl ejercicio en Haskell<\/a> es el siguiente<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    menores :: Ord a => Int -> [a] -> [a]\r\n-- tal que (menores k xs) es la lista de los k menores elementos de\r\n-- xs. Por ejemplo, \r\n--    menores 3 [9,7,2,6,5,4,6,8]  ==  [2,4,5]\r\n-- ---------------------------------------------------------------------\r\n\r\nmenores :: Ord a => Int -> [a] -> [a]\r\nmenores k xs = take k (sort xs) \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Determinar los tiempos empleados en calcular las\r\n-- siguientes expresiones\r\n--    menores 3 [1..1000000]\r\n--    length (sort [1..1000000])\r\n-- A la vista de los resultados anteriores, deducir si para calcular \r\n-- (menores 3 [1..1000000]) se calcula (sort [1..1000000]).\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Soluci\u00f3n: Los c\u00e1culos son\r\n--    *Main> :set +s\r\n--    *Main> menores 3 [1..1000000]\r\n--    [1,2,3]\r\n--    (2.77 secs, 180963472 bytes)\r\n--    *Main> length (sort [1..1000000])\r\n--    1000000\r\n--    (6.42 secs, 521957272 bytes)\r\n-- \r\n-- Por tanto, para calcular (menores 3 [1..1000000]) no se calcula \r\n-- (sort [1..1000000]).\r\n<\/pre>\n
\nEl ejercicio en Maxima<\/a> es el siguiente<\/p>\n
\r\n\/* ---------------------------------------------------------------------\r\n * Ejercicio 1. Definir la funci\u00f3n take tal que take(n,xs) es la lista\r\n * de los n primeros elementos de xs. Por ejemplo,\r\n *    take(3,[2,5,4,7,6]) = [2, 5, 4]\r\n * ------------------------------------------------------------------ *\/\r\n\r\ntake(n,xs) := rest(xs,n-length(xs))$\r\n\r\n\/* ---------------------------------------------------------------------\r\n * Ejercicio 2. Definir la funci\u00f3n menores tal que menores(k,xs) es la\r\n * lista de los k menores elementos de xs. Por ejemplo,\r\n *    menores(3,[9,7,2,6,5,4,6,8])  =  [2,4,5]\r\n * ------------------------------------------------------------------ *\/\r\n\r\nmenores(k,xs) := take(k,sort(xs))$ \r\n\r\n\/* ---------------------------------------------------------------------\r\n * Ejercicio 2. Determinar los tiempos empleados en calcular las\r\n * siguientes expresiones (con las definiciones compiladas):\r\n *    menores(3,makelist(i,i,1,1000000))$\r\n *    sort (makelist(i,i,1,1000000))$\r\n * ------------------------------------------------------------------ *\/\r\n\r\n\/* Soluci\u00f3n:\r\n *    (%i4) compile(all)$\r\n *    (%i5) showtime : true$\r\n *    Evaluation took 0.0000 seconds (0.0000 elapsed)\r\n *    (%o5) true\r\n *    (%i6) menores(3,makelist(i,i,1,1000000));\r\n *    Evaluation took 94.1800 seconds (94.4900 elapsed)\r\n *    (%i7) sort (makelist(i,i,1,1000000))$\r\n *    Evaluation took 93.0800 seconds (93.4500 elapsed)\r\n *\/\r\n<\/pre>\n
\nComo se observa, el tiempo que usa Haskell<\/a> 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<\/a> para calcular los 3 menores elementos (94.18 segundos) es ligeramente superior al tiempo de ordenarla (93.08 segundos).<\/p>\n","protected":false},"excerpt":{"rendered":"
Una caracter\u00edstica singular de Haskell es su car\u00e1cter perezoso, frente al impaciente de la mayor\u00eda de los restantes lenguajes. Los lenguajes perezosos usan evaluaci\u00f3n perezosa; es decir, al evaluar una expresi\u00f3n eval\u00faan sus argumentos s\u00f3lo cuando los necesita. De manera opuesta, en la evaluaci\u00f3n impaciente los argumentos de las expresiones se eval\u00faan antes que las…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[108,157,158,270,281],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/453"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=453"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/453\/revisions"}],"predecessor-version":[{"id":3032,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/453\/revisions\/3032"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=453"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=453"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=453"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}