Tiago Charters work gallery about contact

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.

---

For attribution, please cite this page as:

Charters, T., "Profile Lisp programs with SLIME": https://nexp.pt/profile.html (23-01-2025 [00:04])

---

(cc-by-sa) Tiago Charters - tiagocharters@nexp.pt