La función de Takeuchi como banco de prueba para la eficiencia

La función de Takeuchi está definida por
$tak(x,y,z) = \newline \left\{ \begin{array}{ll} y, & si \ x \leq y \\ tak(tak(x-1,y,z), tak(y-1,z,x), tak(z-1,x,y)) & en\ caso\ contrario \end{array} \right.$

En este artículo voy a comparar la la eficiencia de Haskell, Maxima y Lisp escribiendo en los tres la definición recursiva de la función de Takeuchi y calculando $tak(16,6,1)$ .

La definición en Haskell es

tak x y z
    | x <= y    = y
    | otherwise = tak (tak (x-1) y z)
                      (tak (y-1) z x)
                      (tak (z-1) x y)

tak x y z

| x <= y = y

| otherwise = tak (tak (x-1) y z)

(tak (y-1) z x)

(tak (z-1) x y)

y el cálculo es

*Main> :set +s
*Main> tak 16 6 1
16
(0.02 secs, 0 bytes)

*Main> :set +s

*Main> tak 16 6 1

(0.02 secs, 0 bytes)

La definición en Maxima es

tak(x,y,z) :=
  if is(x <= y) then y
  else tak(tak(x-1,y,z),
           tak(y-1,z,x),
           tak(z-1,x,y))$

tak(x,y,z) :=

if is(x <= y) then y

else tak(tak(x-1,y,z),

tak(y-1,z,x),

tak(z-1,x,y))$

y es el cálculo es

(%i4) compile(tak);

Compiling /tmp/gazonk_1499_0.lsp.
End of Pass 1.  
End of Pass 2.  
OPTIMIZE levels: Safety=2, Space=3, Speed=3
Finished compiling /tmp/gazonk_1499_0.lsp.
(%o4)                                [tak]
(%i5) showtime:true$
Evaluation took 0.0000 seconds (0.0000 elapsed)
(%i6) tak(16,6,1);
Evaluation took 5908.4700 seconds (6967.5700 elapsed)
(%o6) 16

(%i4) compile(tak);

Compiling /tmp/gazonk_1499_0.lsp.

End of Pass 1.

End of Pass 2.

OPTIMIZE levels: Safety=2, Space=3, Speed=3

Finished compiling /tmp/gazonk_1499_0.lsp.

(%o4) [tak]

(%i5) showtime:true$

Evaluation took 0.0000 seconds (0.0000 elapsed)

(%i6) tak(16,6,1);

Evaluation took 5908.4700 seconds (6967.5700 elapsed)

(%o6) 16

La definición en Lisp es

(defun tak (x y z)
  (if (<= x y)
      y
      (tak (tak (- x 1) y z)
           (tak (- y 1) z x)
           (tak (- z 1) x y))))

(defun tak (x y z)

(if (<= x y)

(tak (tak (- x 1) y z)

(tak (- y 1) z x)

(tak (- z 1) x y))))

y el cálculo es

[2]> (time (tak 16 6 1))
Real time: 6217.7544 sec.
Run time: 6204.172 sec.
Space: 0 Bytes
16
[3]> (compile-file "Takeuchi.lsp")
;; Compiling file Takeuchi.lsp ...
;; Wrote file Takeuchi.fas
0 errores, 0 advertencias
#P"Takeuchi.fas" ;
NIL ;
NIL
[4]> (load "Takeuchi.fas")
;; Loading file Takeuchi.fas ...
;; Loaded file Takeuchi.fas
T
[5]> (time (tak 16 6 1))
Real time: 1014.2405 sec.
Run time: 1006.6749 sec.
Space: 0 Bytes
16

[2]> (time (tak 16 6 1))

Real time: 6217.7544 sec.

Run time: 6204.172 sec.

Space: 0 Bytes

[3]> (compile-file "Takeuchi.lsp")

;; Compiling file Takeuchi.lsp ...

;; Wrote file Takeuchi.fas

0 errores, 0 advertencias

#P"Takeuchi.fas" ;

NIL ;

NIL

[4]> (load "Takeuchi.fas")

;; Loading file Takeuchi.fas ...

;; Loaded file Takeuchi.fas

[5]> (time (tak 16 6 1))

Real time: 1014.2405 sec.

Run time: 1006.6749 sec.

Space: 0 Bytes

Todo los cálculos se han realizado en un ordenador con Ubuntu versión 10.04, núcleo linux 2.6.32-24-generic, 2,0 GiB de memoria y un procesador Intel(R) Atom(TM) CPU N280 @ 1.66GHz.

El resumen de los tiempos obtenidos es
$\begin{array}{|l|l|r|} \hline Lenguaje & Version & Segundos\\ \hline Haskell & GHC\ 6.12.1 & 0.02 \\ \hline Lisp & CLISP\ 2.44.1 & 6204.17 \\ \hline Lisp\ compilado & CLISP\ 2.44.1 & 1006.67 \\ \hline Maxima\ compilado & 5.20.1 & 5908.47 \\ \hline \end{array}$

Los tiempos anteriores depende de la versión del lenguaje y de la máquina que se esté usando. Por ejemplo, si en lugar de usar Clisp sobre Ubuntu usamos LispWorksPersonal Edition 5.1.1 en una máquina con Windows XP, Intel (R) Atom (TM) CPU N270 @ 1.60 GHz y 1.99 GB de RAM después de compilar el fichero el resultado es

CL-USER 1 > (time (tak 16 6 1))
Timing the evaluation of (TAK 16 6 1)

User time    =  0:02:43.437
System time  =        0.312
Elapsed time =  0:02:49.922
Allocation   = 155816 bytes
0 Page faults
16

CL-USER 1 > (time (tak 16 6 1))

Timing the evaluation of (TAK 16 6 1)

User time = 0:02:43.437

System time = 0.312

Elapsed time = 0:02:49.922

Allocation = 155816 bytes

0 Page faults

El tiempo total es de 169.92 segundos, que es sensiblemente inferior a los 1006.67 segundos de Clisp.

¿Qué opináis de estas diferencias de tiempo?

Se puede imprimir o compartir con