{"id":422,"date":"2010-08-18T13:41:02","date_gmt":"2010-08-18T13:41:02","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/la-funcion-de-ackermann-como-prueba-de-rendimiento\/"},"modified":"2013-03-08T05:53:42","modified_gmt":"2013-03-08T05:53:42","slug":"la-funcion-de-ackermann-como-prueba-de-rendimiento","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/la-funcion-de-ackermann-como-prueba-de-rendimiento\/","title":{"rendered":"La funci\u00f3n de Ackermann como prueba de rendimiento"},"content":{"rendered":"

En la entrada la funci\u00f3n de Takeuchi como banco de prueba para la eficiencia<\/a> us\u00e9 la funci\u00f3n de Takeuchi para comparar la eficiencia de Haskell (GHC) y Lisp (Clisp y LispWorks). En esta voy a hacer lo mismo con la funci\u00f3n de Ackermann.<\/p>\n

\nLa funci\u00f3n de Ackermann<\/a> (tambi\u00e9n llamada funci\u00f3n de Ackermann-P\u00e9ter) es un ejemplo sencillo de funci\u00f3n recursiva<\/a> que no es primitiva recursiva<\/a>. Definida en 1926 por Wilhelm Ackermann<\/a>, pero se presenta frecuentemente en la forma propuesta por R\u00f3zsa P\u00e9ter, que es la siguiente
\n\"<br
\n<\/p>\n

\nEn The Common-Lisp benchmarking suite<\/a> se plantea la prueba ACKERMANN consistente en medir, a partir de la siguiente definici\u00f3n de la funci\u00f3n de Ackermann,<\/p>\n

\r\n(defun ackermann (m n)\r\n  (declare (type integer m n))\r\n  (cond\r\n    ((zerop m) (1+ n))\r\n    ((zerop n) (ackermann (1- m) 1))\r\n    (t (ackermann (1- m) (ackermann m (1- n))))))\r\n<\/pre>\n
el tiempo necesario para calcular (ackermann 3 11). <\/p>\n
\nHe realizado la prueba de ACKERMANN en Clisp:<\/p>\n
\r\n[1]> (compile-file \"Ackermann.lsp\")\r\n[2]> (load \"Ackermann\")\r\n[3]> (time (ackermann 3 11))\r\nReal time: 50.266396 sec.\r\nRun time: 50.175137 sec.\r\nSpace: 0 Bytes\r\n16381\r\n<\/pre>\n
y en LispWorks:<\/p>\n
\r\nCL-USER 1 > (compile-file \"Ackermann.lsp\")\r\nCL-USER 2 > (load \"Ackermann\")\r\nCL-USER 3 > (time (ackermann 3 11))\r\nTiming the evaluation of (ACKERMANN 3 11)\r\n\r\nUser time    =  6.140\r\nSystem time  =  0.015\r\nElapsed time =  7.140\r\nAllocation   = 8600 bytes\r\n0 Page faults\r\n16381\r\n<\/pre>\n
\nPara hacer la prueba de ACKERMANN en Haskell he definido la funci\u00f3n<\/p>\n
\r\nackermann :: Integer -> Integer -> Integer\r\nackermann 0 n = n+1\r\nackermann m 0 = ackermann (m-1) 1\r\nackermann m n = ackermann (m-1) (ackermann m (n-1))\r\n<\/pre>\n
El resultado de la prueba con GHC es el siguiente<\/p>\n
\r\n*Main> :set +s\r\n*Main> :set -fobject-code\r\n*Main> :load \"Ackermann.hs\"\r\n*Main> ackermann 3 11\r\n16381\r\n(96.29 secs, 14331472060 bytes)\r\n<\/pre>\n
\nEl resumen de los tiempos (en segundos) obtenidos en las pruebas de Takeuchi y de Ackermann es
\n\"<br<\/p>\n","protected":false},"excerpt":{"rendered":"
En la entrada la funci\u00f3n de Takeuchi como banco de prueba para la eficiencia us\u00e9 la funci\u00f3n de Takeuchi para comparar la eficiencia de Haskell (GHC) y Lisp (Clisp y LispWorks). En esta voy a hacer lo mismo con la funci\u00f3n de Ackermann. La funci\u00f3n de Ackermann (tambi\u00e9n llamada funci\u00f3n de Ackermann-P\u00e9ter) es un ejemplo…<\/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,92,95],"tags":[97,270,283,284],"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\/422"}],"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=422"}],"version-history":[{"count":10,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/422\/revisions"}],"predecessor-version":[{"id":3036,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/422\/revisions\/3036"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=422"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=422"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=422"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}