(defun memo (fn &key (test #'eql)) (let ((table (make-hash-table :test test))) #'(lambda (&rest args) (multiple-value-bind (val found-p) (gethash args table) (if found-p val (setf (gethash args table) (apply fn args)))))))これを使ったdefun*によりfib*を定義し直して 実行を行なうと,
> (time (fib* 19)) cpu time (non-gc) 117 msec user, 16 msec system cpu time (gc) 300 msec user, 117 msec system cpu time (total) 417 msec user, 133 msec system real time 572 msec 6765 > (time (fib* 19)) cpu time (non-gc) 17 msec user, 0 msec system cpu time (gc) 0 msec user, 0 msec system cpu time (total) 17 msec user, 0 msec system real time 8 msec 6765というようになる. 引数が複数ある場合に,引数のデータの組合せの数が 大きくなると問題になり,かえって時間がかかったりする. たとえば,
(defun tarai (x y z) (cond ((> x y) (tarai (tarai (1- x) y z) (tarai (1- y) z x) (tarai (1- z) x y) )) (t y))) (defun* tarai* (x y z) (cond ((> x y) (tarai* (tarai* (1- x) y z) (tarai* (1- y) z x) (tarai* (1- z) x y) )) (t y)))という関数は,ベンチマークテストによく使われる. (tarai 8 4 0)を行なうと12605回のtaraiが呼ばれることになる.
> (time (tarai 8 4 0)) cpu time (non-gc) 14500 msec user, 700 msec system cpu time (gc) 217 msec user, 0 msec system cpu time (total) 14717 msec user, 700 msec system real time 15535 msec 8という具合に時間がかかるが, tarai*の方は数分以上の時間がかかる. 連想リストではなくハッシュ関数で実現すると,
(defun memo (fn &key (test #'eql)) (let ((table (make-hash-table :test test))) #'(lambda (&rest args) (multiple-value-bind (val found-p) (gethash args table) (if found-p val (setf (gethash args table) (apply fn args)))))))というぐあいに定義できる. multiple-value-bindは多値関数(multiple-valued function)が返す 値を局所変数にバインドするスペシャルフォームである. gethashは,データだけでなく引数のキーに対応するデータが存在するかしな いかという情報を多値として返す. この定義を使うと,
> (time (tarai* 8 4 0)) cpu time (non-gc) 186683 msec user, 1683 msec system cpu time (gc) 19733 msec user, 134 msec system cpu time (total) 206416 msec user, 1817 msec system real time 209876 msec 8という具合の時間がかかることがわかる.