{"id":395,"date":"2010-08-11T07:39:59","date_gmt":"2010-08-11T07:39:59","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/la-funcion-de-takeuchi-como-banco-de-prueba-para-la-eficiencia\/"},"modified":"2014-04-09T19:50:08","modified_gmt":"2014-04-09T17:50:08","slug":"la-funcion-de-takeuchi-como-banco-de-prueba-para-la-eficiencia","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/la-funcion-de-takeuchi-como-banco-de-prueba-para-la-eficiencia\/","title":{"rendered":"La funci\u00f3n de Takeuchi como banco de prueba para la eficiencia"},"content":{"rendered":"

La funci\u00f3n de Takeuchi est\u00e1 definida por
\n\"tak(x,y,z)<\/p>\n

En este art\u00edculo voy a comparar la la eficiencia de Haskell, Maxima y Lisp escribiendo en los tres la definici\u00f3n recursiva de la funci\u00f3n de Takeuchi y calculando \"tak(16,6,1)\".
\n
\nLa definici\u00f3n en Haskell es<\/p>\n

\r\ntak x y z\r\n    | x <= y    = y\r\n    | otherwise = tak (tak (x-1) y z)\r\n                      (tak (y-1) z x)\r\n                      (tak (z-1) x y)\r\n<\/pre>\n
y el c\u00e1lculo es<\/p>\n
\r\n*Main> :set +s\r\n*Main> tak 16 6 1\r\n16\r\n(0.02 secs, 0 bytes)\r\n<\/pre>\n
La definici\u00f3n en Maxima es<\/p>\n
\r\ntak(x,y,z) :=\r\n  if is(x <= y) then y\r\n  else tak(tak(x-1,y,z),\r\n           tak(y-1,z,x),\r\n           tak(z-1,x,y))$\r\n<\/pre>\n
y es el c\u00e1lculo es<\/p>\n
\r\n(%i4) compile(tak);\r\n\r\nCompiling \/tmp\/gazonk_1499_0.lsp.\r\nEnd of Pass 1.  \r\nEnd of Pass 2.  \r\nOPTIMIZE levels: Safety=2, Space=3, Speed=3\r\nFinished compiling \/tmp\/gazonk_1499_0.lsp.\r\n(%o4)                                [tak]\r\n(%i5) showtime:true$\r\nEvaluation took 0.0000 seconds (0.0000 elapsed)\r\n(%i6) tak(16,6,1);\r\nEvaluation took 5908.4700 seconds (6967.5700 elapsed)\r\n(%o6) 16\r\n<\/pre>\n
La definici\u00f3n en Lisp es<\/p>\n
\r\n(defun tak (x y z)\r\n  (if (<= x y)\r\n      y\r\n      (tak (tak (- x 1) y z)\r\n           (tak (- y 1) z x)\r\n           (tak (- z 1) x y))))\r\n<\/pre>\n
y el c\u00e1lculo es<\/p>\n
\r\n[2]> (time (tak 16 6 1))\r\nReal time: 6217.7544 sec.\r\nRun time: 6204.172 sec.\r\nSpace: 0 Bytes\r\n16\r\n[3]> (compile-file \"Takeuchi.lsp\")\r\n;; Compiling file Takeuchi.lsp ...\r\n;; Wrote file Takeuchi.fas\r\n0 errores, 0 advertencias\r\n#P\"Takeuchi.fas\" ;\r\nNIL ;\r\nNIL\r\n[4]> (load \"Takeuchi.fas\")\r\n;; Loading file Takeuchi.fas ...\r\n;; Loaded file Takeuchi.fas\r\nT\r\n[5]> (time (tak 16 6 1))\r\nReal time: 1014.2405 sec.\r\nRun time: 1006.6749 sec.\r\nSpace: 0 Bytes\r\n16\r\n<\/pre>\n
Todo los c\u00e1lculos se han realizado en un ordenador con Ubuntu versi\u00f3n 10.04,  n\u00facleo linux 2.6.32-24-generic, 2,0 GiB de memoria y un procesador Intel(R) Atom(TM) CPU N280 @ 1.66GHz.<\/p>\n
El resumen de los tiempos obtenidos es
\n\"\begin{array}{|l|l|r|}<\/p>\n
Los tiempos anteriores depende de la versi\u00f3n del lenguaje y de la m\u00e1quina que se est\u00e9 usando. Por ejemplo, si en lugar de usar Clisp sobre Ubuntu usamos LispWorksPersonal Edition 5.1.1 en una m\u00e1quina con Windows XP, Intel (R) Atom (TM) CPU N270 @ 1.60 GHz y 1.99 GB de RAM despu\u00e9s de compilar el fichero el resultado es<\/p>\n
\r\nCL-USER 1 > (time (tak 16 6 1))\r\nTiming the evaluation of (TAK 16 6 1)\r\n\r\nUser time    =  0:02:43.437\r\nSystem time  =        0.312\r\nElapsed time =  0:02:49.922\r\nAllocation   = 155816 bytes\r\n0 Page faults\r\n16\r\n<\/pre>\n
El tiempo total es de 169.92 segundos, que es sensiblemente inferior a los 1006.67 segundos de Clisp.<\/p>\n
\u00bfQu\u00e9 opin\u00e1is de estas diferencias de tiempo? <\/p>\n","protected":false},"excerpt":{"rendered":"
La funci\u00f3n de Takeuchi est\u00e1 definida por En este art\u00edculo voy a comparar la la eficiencia de Haskell, Maxima y Lisp escribiendo en los tres la definici\u00f3n recursiva de la funci\u00f3n de Takeuchi y calculando .<\/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,74,95],"tags":[93,270,283,281,284,94],"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\/395"}],"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=395"}],"version-history":[{"count":15,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/395\/revisions"}],"predecessor-version":[{"id":4258,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/395\/revisions\/4258"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=395"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=395"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=395"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}