À propósito, ikarus Scheme, um compilador nativo incremental usando
GMP, parece dar uma performance excelente mesmo para o fatorial
simples, melhor que SBCL:
namekusei...@nameku:~$ ikarus
Ikarus Scheme version 0.0.3
Copyright (c) 2006-2008 Abdulaziz Ghuloum
> (define (fact n)
(let f ((n n) (r 1))
(if (< n 2) r (f (- n 1) (* r n)))))
> (time (and (fact 100000) #t))
running stats for (and (fact 100000) #t):
2405 collections
4988 ms elapsed cpu time, including 664 ms collecting
4990 ms elapsed real time, including 691 ms collecting
9931119600 bytes allocated
#t
namekusei...@nameku:~$ sbcl
This is SBCL 1.0.11.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun fact (n &optional (r 1))
(if (< n 2) r
(fact (1- n) (* r n))))
FACT
* (time (and (fact 100000) t))
Evaluation took:
9.696 seconds of real time
9.192575 seconds of user run time
0.504031 seconds of system run time
[Run times include 0.904 seconds GC run time.]
0 calls to %EVAL
0 page faults and
9,931,045,056 bytes consed.
T
postei sobre isso em comp.lang.lisp e comp.lang.scheme... mas
provavelmente o mérito é mais da GMP mesmo, pusta biblioteca, ainda
mais quando acessada de uma linguagem de alto nível. :)
On Apr 30, 4:27 am, namekuseijin <[email protected]> wrote:
> On Apr 30, 2:43 am, tarcisio praciano-pereira
>
>
>
> <[email protected]> wrote:
> > Eras, Pedro! explica o código - put some comments! Não entendi nada, e
> > sou matemático.
>
> > Aparentemente fazes alguma seleção entre par e impar, mas não entendi
> > porque.
> > > (defun ! (n)
> > > (let ((shift 0))
> > > (labels ((fact1 (n m)
> > > (cond
> > > ((and (evenp n) (> m 1))
> > > (incf shift (ash n -1))
> > > (fact1 (ash n -1) (ash m -1)))
> > > ((<= n m) n)
> > > (t (* (fact1 n (ash m 1)) (fact1 (- n m)(ash m 1)))))))
> > > (ash (fact1 n 1) shift))))
>
> > > pedro
>
> Ele usou otimização com bitshifting, uma operação a nível de máquina.
> Não é pra ser compreendido para não iniciados. ;)
>
> Fatorial é aquela definição recursiva e simples (e não otimizada) de
> sempre:
> (defun fatorial (n)
> (if (< n 2) 1
> (* n (fatorial (- n 1)))))
>
> Exceto que uma implementação puramente recursiva desse tipo
> rapidamente chega a um limite de execução: a pilha estoura por haver
> muitas chamadas para ns muito grandes. A solução simples em
> programação funcional é usar o estilo de tail calls (que a maioria das
> implementações suporta).
>
> Nesse estilo, elimina-se a necessidade de se manter várias chamadas em
> aberto na pilha ao se eliminar a espera pelo termino de uma
> computação: a última chamada (tail call) é realmente uma chamada, não
> uma expressão esperando pelo resultado de uma chamada. Como nada
> exceto a chamada original da função espera pelo seu resultado final,
> por baixo dos panos pode-se simplesmente, a grosso modo, eliminar todo
> o artefato de chamadas reais de função e compilá-la como se fosse uma
> simples iteração ou um goto nomeado. Não se gasta pilha de chamadas.
>
> Ilustrando:
>
> (if (< n 2) 1 ; <- expressão final
> (* n (fatorial (- n 1))))) ; <- expressão final esperando pelo
> resultado da chamada recursiva
>
> a troca é simples e o benefício é imenso:
> (if (< n 2) 1
> (fatorial (- n 1) (* n)))) ; trazemos a expressão final como um
> parâmetro para a própria chamada
>
> mas está incompleto, pois o resultado de (fatorial (- n 1)) ainda não
> foi calculado e não podemos portanto multiplicá-lo a n, certo? Bem,
> digamos que possamos e chamemos a ele de resultado:
>
> (if (< n 2) resultado ; <- aqui
> (fatorial (- n 1) (* n resultado)))) ; <- e aqui
>
> agora vamos dar um valor inicial a resultado, que por acaso vai ser o
> mesmo para a condição de parada original: 1
>
> (defun fatorial (n &optional (resultado 1))
> (if (< n 2) resultado
> (fatorial (- n 1) (* n resultado))))
>
> Bem, devo dizer que esse SBCL realmente é um bicho parrudo. Executou
> (and (fatorial 100000) t) em 9,8 segundos. Gambit, uma das mais
> potentes implementações para Scheme, ficou na marca de 32 segundos
> para uma implementação similar:
>
> (define (fatorial n)
> (define (! n r) (if (< n 2) r (! (- n 1) (* r n))))
> (! n 1))
>
> 3 x mais lento... por outro lado, gera C portável. :)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Lisp-br" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/lisp-br?hl=en
-~----------~----~----~----~------~----~------~--~---
