La función de Ackermann como prueba de rendimiento
En la entrada la función de Takeuchi como banco de prueba para la eficiencia usé la función de Takeuchi para comparar la eficiencia de Haskell (GHC) y Lisp (Clisp y LispWorks). En esta voy a hacer lo mismo con la función de Ackermann.
La función de Ackermann (también llamada función de Ackermann-Péter) es un ejemplo sencillo de función recursiva que no es primitiva recursiva. Definida en 1926 por Wilhelm Ackermann, pero se presenta frecuentemente en la forma propuesta por Rózsa Péter, que es la siguiente
En The Common-Lisp benchmarking suite se plantea la prueba ACKERMANN consistente en medir, a partir de la siguiente definición de la función de Ackermann,
|
1 2 3 4 5 6 |
(defun ackermann (m n) (declare (type integer m n)) (cond ((zerop m) (1+ n)) ((zerop n) (ackermann (1- m) 1)) (t (ackermann (1- m) (ackermann m (1- n)))))) |
el tiempo necesario para calcular (ackermann 3 11).
He realizado la prueba de ACKERMANN en Clisp:
|
1 2 3 4 5 6 7 |
[1]> (compile-file "Ackermann.lsp") [2]> (load "Ackermann") [3]> (time (ackermann 3 11)) Real time: 50.266396 sec. Run time: 50.175137 sec. Space: 0 Bytes 16381 |
y en LispWorks:
|
1 2 3 4 5 6 7 8 9 10 11 |
CL-USER 1 > (compile-file "Ackermann.lsp") CL-USER 2 > (load "Ackermann") CL-USER 3 > (time (ackermann 3 11)) Timing the evaluation of (ACKERMANN 3 11) User time = 6.140 System time = 0.015 Elapsed time = 7.140 Allocation = 8600 bytes 0 Page faults 16381 |
Para hacer la prueba de ACKERMANN en Haskell he definido la función
|
1 2 3 4 |
ackermann :: Integer -> Integer -> Integer ackermann 0 n = n+1 ackermann m 0 = ackermann (m-1) 1 ackermann m n = ackermann (m-1) (ackermann m (n-1)) |
El resultado de la prueba con GHC es el siguiente
|
1 2 3 4 5 6 |
*Main> :set +s *Main> :set -fobject-code *Main> :load "Ackermann.hs" *Main> ackermann 3 11 16381 (96.29 secs, 14331472060 bytes) |
El resumen de los tiempos (en segundos) obtenidos en las pruebas de Takeuchi y de Ackermann es
