next up previous
Next: 9 遅延評価(lazy evaluation) Up: 8 クロージャによる結果記憶型関数(memoization)の実現 Previous: 8.2 結果記憶型関数を定義するマクロの定義

8.3 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月6日