8.1 結果記憶手続きへの変換手続き

Next: 8.2 結果記憶型関数を定義するマクロの定義 Up: 8 クロージャによる結果記憶型関数(memoization)の実現 Previous: 8 クロージャによる結果記憶型関数(memoization)の実現

8.1 結果記憶手続きへの変換手続き

ユーザが定義する関数を記憶型の関数に変換するプログラムは，この対のデータをユーザの関数ごとに記憶する必要がある．このデータを記憶するためにいちいち大域変数を用意するのではなく，もとの関数を記憶型に変換した関数データを返すことにし，対の記憶データはクロージャの中に蓄えることで実現が可能になる．


(defun memo (fn)
  (let (alist)
    #'(lambda (x)
        (let ((result (assoc x alist)))
          (cond
           ((null result)
            (setq result (funcall fn x))
            (setq alist (cons (cons x result) alist))
            result)
           (t (cdr result)))))))

このmemo関数にfibを渡して記憶型のfibを定義することができる．


> (setq fib-memo (memo #'fib))
...
> (funcall fib-memo 4)
 0: (FIB 3)
   1: (FIB 2)
     2: (FIB 1)
     2: returned 1
     2: (FIB 0)
     2: returned 1
   1: returned 2
   1: (FIB 1)
   1: returned 1
 0: returned 3
 0: (FIB 2)
   1: (FIB 1)
   1: returned 1
   1: (FIB 0)
   1: returned 1
 0: returned 2
5

このfib-memoを実行してもfib自体が変更されていないために，トップレベルの実行結果のみしか蓄積されない．そこでfib-memoをfib本体として定義してしまえば良い．

> (setf (symbol-function 'fib) fib-memo)
#<Function FIB @ #x900a76> 
> (fib 5)
 0: (FIB 5)
   1: (FIB 4)
   1: returned 5
   1: (FIB 3)
   1: returned 3
 0: returned 8
8 
> (fib 6)
 0: (FIB 6)
   1: (FIB 5)
   1: returned 8
   1: (FIB 4)
   1: returned 5
 0: returned 13
13

このようにfibが下請けの計算をいちいちせずに関数を用意していることがわかる．

generated through LaTeX2HTML. M.Inaba 平成18年5月7日