Next: 8.1 結果記憶手続きへの変換手続き
Up: ソフトウェア特論 講義資料 クロージャ，オブジェクト指向
Previous: 7 シンボルの関数定義
memoizationというのは，ある計算が実行された時に，計算したデータをどこ
かに保存しておいてその計算がもう一度呼び出された際には再び計算の本体を
実行することはせずに，前に計算しておいたデータを返すだけにするという方
法です．
たとえば，フィボナッチ数を計算する関数fibにおいて，
(defun fib (n)
(if (< n 2) 1
(+ (fib (1- n)) (fib (- n 2)))))
> (fib 19)
6765
> (time (fib 19))
cpu time (non-gc) 13134 msec user, 617 msec system
cpu time (gc) 483 msec user, 0 msec system
cpu time (total) 13617 msec user, 617 msec system
real time 14453 msec
6765
というように14秒程度の時間がかかっています．
このfibの定義を見るとわかるように，(fib 19)をするために
(fib 18)と(fib 17)が呼ばれ，(fib 18)をするために(fib 17)が
また呼ばれます．しかし，それぞれの(fib 17)では定義どおりの
計算をそれぞれ実行してしまいます．
そこで，(fib 17)の計算結果が
出たところでその値を保存し，次に(fib 17)が呼ばれるとその
記憶値を利用するという方法をとれば
計算時間の大幅な短縮が期待されます．
ここで記憶するデータは，引数と計算結果の対です．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日