KMRCLを眺める(160) MEMOIZE — #:g1

Posted 2010-06-03 22:55:00 GMT

今回は、KMRCLのfunctions.lispからMEMOIZEです。
前回のMEMO-PROCを利用して既存の関数をメモ化版にするものです。
定義は、

(defun memoize (fn-name)
  (setf (fdefinition fn-name) (memo-proc (fdefinition fn-name))))
動作は、
(DEFUN FIB (N)
  (IF (< N 2)
      N
      (+ (FIB (1- N))
         (FIB (- N 2)))))

;; トレース (TRACE FIB)

(FIB 5) 0: (FIB 5) 1: (FIB 4) 2: (FIB 3) 3: (FIB 2) 4: (FIB 1) 4: FIB returned 1 4: (FIB 0) 4: FIB returned 0 3: FIB returned 1 3: (FIB 1) 3: FIB returned 1 2: FIB returned 2 2: (FIB 2) 3: (FIB 1) 3: FIB returned 1 3: (FIB 0) 3: FIB returned 0 2: FIB returned 1 1: FIB returned 3 1: (FIB 3) 2: (FIB 2) 3: (FIB 1) 3: FIB returned 1 3: (FIB 0) 3: FIB returned 0 2: FIB returned 1 2: (FIB 1) 2: FIB returned 1 1: FIB returned 2 0: FIB returned 5 ;⇒ 5

;; メモ化発動 (KL:MEMOIZE 'FIB)

(FIB 5) 0: (FIB 5) 1: (FIB 4) 2: (FIB 3) 3: (FIB 2) 4: (FIB 1) 4: FIB returned 1 4: (FIB 0) 4: FIB returned 0 3: FIB returned 1 3: (FIB 1) 3: FIB returned 1 2: FIB returned 2 2: (FIB 2) 2: FIB returned 1 1: FIB returned 3 1: (FIB 3) 1: FIB returned 2 0: FIB returned 5 ;⇒ 5

といったところで、FIBをメモ化すると関数の呼び出しが減るのが分かると思います。

comments powered by Disqus