Profile Lisp programs with SLIME
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) 222232244629420445529739893461909967206666939096499764990979600enquanto 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
Criado/Created: NaN
Última actualização/Last updated: 10-10-2022 [14:26]
(c) Tiago Charters de Azevedo