next up previous
Next: 8.1 結果記憶手続きへの変換手続き Up: ソフトウェア第三 講義資料 クロージャ,スコープ,遅延評価,オブジェクト,立体モデル Previous: 7 シンボルの関数定義

8 クロージャによる結果記憶型関数(memoization)の実現

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