Next: 9 遅延評価(lazy evaluation)
Up: 8 クロージャによる結果記憶型関数(memoization)の実現
Previous: 8.2 結果記憶型関数を定義するマクロの定義
また，引数がリストであっても大丈夫なようにmemoを拡張する．
(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
という具合の時間がかかることがわかる．
generated through LaTeX2HTML. M.Inaba 平成18年5月7日