✍ Profile Lisp programs with SLIME

Comparação de desempenho em duas implementações da sucessão de Fibonacci em CL

Há sempre duas maneiras diferentes de fazer a mesma coisa, em particular, o cálculo da sucessão de Fibonacci pode ser feita: da maneira ingénua

(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib (- n 1))
              (fib (- n 2))))))
e da inteligente
(defun fib-lin (n)
  (labels ((fib-iter (a b count)
             (cond ((eq count 0)
                    b)
                   (t
                    (fib-iter (+ a b) a (- count 1))))))
  (fib-iter 1 0 n)))
Podemos calcular os 10 primeiros termos através de, e da maneira inteligente,
> (loop for i from 1 to 10 collect
      (list i (fib-lin i)))

((1 1) (2 1) (3 2) (4 3) (5 5) (6 8) (7 13) (8 21) (9 34) (10 55))

Vejamos então analisar o comportamento de fib e fib-lin usando o slime-profile. Não há dúvida que fib-lin é bastante mais eficiente, não se sente nenhum sobressalto,

> (fib-lin 300)

222232244629420445529739893461909967206666939096499764990979600
enquanto o mesmo não acontece para
> (fib 10)

55

A função fib-lin tem um crescecimento tipo n enquanto fib tem um crescimento do tipo (fib n). Usando o slime-profile-report dá:

                                               Cons
             %      %                          Per      Total     Total
Function    Time   Cons    Calls  Sec/Call     Call     Time      Cons
--------------------------------------------------------------------------
FIB-LIN:   53.79  100.00        1  0.003997    18144     0.004       18144
FIB:       46.21    0.00      177  0.000019        0     0.003           0
--------------------------------------------------------------------------

Note-se a diferença!

Já agora a sucessão de Lucas é dada por

(defun lucas-lin (n)
  (labels ((fib-iter (a b count)
             (cond ((eq count 0)
                    b)
                   (t
                    (fib-iter (+ a b) a (- count 1))))))
  (fib-iter 1 2 n)))

Claro que a primeira forma é a natural tendo em conta a definição dos números de Fibonacci no entanto a eficiência desse procedimento é catastrófica, isto porque, por exemplo para o cálculo de (fib 5) temos

                                        +---------------------- (fib 5) -----------------------------+
                                        |                                                            |
                      +-------------- (fib 4) -----------+                                 +------ (fib 3) -----+
                      |                                  |                                 |                    |
            +------ (fib 3) -----+                +--- (fib 2) ---+                 +--- (fib 2) ---+         (fib 1)
            |                    |                |               |                 |               |
     +--- (fib 2) ---+         (fib 1)          (fib 1)         (fib 0)           (fib 1)         (fib 0)
     |               |
   (fib 1)         (fib 0)
e por isso temos de calcular (fib 2) 3 vezes. Na realidade o número de operações para o cálculo de (fib n) é da ordem de (fib n), para n suficientemente grande. Em vez de pensarmos, por agora, numa forma definida por recorrência para o calculo de (fib n) vejamos uma forma imperativa do algoritmo.
(defun fib-iter (n)
  (let ((a 1) (b 1) (c 1))
    (do ((i 2 (+ i 1)))
    ((> i n))
      (setq a b
            b c
            c (+ a b)))
    c))
 
Na forma anterior apenas uma soma éfectuada em cada iteração do ciclo do, e, assim, para valores grandes de n, o número de operações é da ordem de n.

Note-se que a expressão

(defun fib-lin (n)
  (labels ((fib-iter (a b count)
             (cond ((eq count 0)
                    b)
                   (t
                    (fib-iter (+ a b) a (- count 1))))))
  (fib-iter 1 0 n)))
faz isso mesmo mas usa uma função interna fib-iter com argumentos extra para contar, como faz o ciclo do, as operações efectuadas; e é uma forma bastante mais elucidativa que mostra como escrever um ciclo iterativo através de uma expressão definida por recorrência. Palavras chave/keywords: Lisp, Fibonacci, SLIME, profile

Última actualização/Last updated: 2014-11-13 [00:04]


1999-2014 (ç) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.