(defun fib (n)
(if (<= n 1) 1
(+ (fib (- n 1)) (fib (- n 2)))))
(defun memo (fn)
(let ((table (make-hash-table)))
#'(lambda (x)
(multiple-value-bind (val found-p)
(gethash x table)
(if found-p
val
(setf (gethash x table) (funcall fn x)))))))
(defun memoize (fn-name)
(setf (symbol-function fn-name) (memo (symbol-function fn-name))))
CL-USER> (memoize 'fib)
#<CLOSURE (LAMBDA (X)) {A748FC5}>
CL-USER> (time (fib 1000))
Evaluation took:
0.002 seconds of real time
0.001999 seconds of user run time
0.0 seconds of system run time
0 page faults and
135,064 bytes consed.
7033036771142281582183525487718...
CL-USER> (time (fib 1000)) ; 2eme appel -> instantané
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
7033036771142281582183525487718...
Comme quoi le choix de l'algorithme est parfois (beaucoup) plus important que le langage. /me range sont PAIP, enfonce des portes ouvertes et --> [ ]
[^] # Re: Comment casser le mythe de rapidité de Fibonacci :-)
Posté par hocwp (site web personnel) . En réponse à la dépêche Erlang/OTP R11B supporte les architectures multiprocesseur. Évalué à 4.
CL-USER> (memoize 'fib) #<CLOSURE (LAMBDA (X)) {A748FC5}> CL-USER> (time (fib 1000)) Evaluation took: 0.002 seconds of real time 0.001999 seconds of user run time 0.0 seconds of system run time 0 page faults and 135,064 bytes consed. 7033036771142281582183525487718... CL-USER> (time (fib 1000)) ; 2eme appel -> instantané Evaluation took: 0.0 seconds of real time 0.0 seconds of user run time 0.0 seconds of system run time 0 page faults and 0 bytes consed. 7033036771142281582183525487718...Comme quoi le choix de l'algorithme est parfois (beaucoup) plus important que le langage. /me range sont PAIP, enfonce des portes ouvertes et --> [ ]