[LISP] メモ化

メモ化(memoization)は関数の引数と返値の対応をハッシュテーブルなどに保存しておくことにより、同じ引数で呼ばれた場合の再計算を防ぐプログラミング技法だ。ただし、メモ化する関数が内部状態を持っていて引数によらないで値が変わる場合、すなわち参照透明でない場合には使えない。
On Lispでは、クロージャの応用例として登場する。次の関数memoizeはハッシュテーブルを内部状態として持つクロージャを返す。

;; On Lispでのメモ化の実装
(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind (val win) (gethash args cache)
          (if win
              val
              (setf (gethash args cache) 
                    (apply fn args)))))))

実際に使うときはどうなるだろうか。フィボナッチ数列の場合、素の実装だと時間がかかるが、

(defun fib (n)
  (cond ((= n 0) 1)
	((= n 1) 1)
	(t (+ (fib (1- n))
	      (fib (- n 2))))))


(time (fib 40))
; Evaluation took:
;   4.313 seconds of real time
;   4.459297 seconds of total run time (4.459297 user, 0.000000 system)
;   103.39% CPU
;   11,501,086,452 processor cycles
;   65,664 bytes consed
  
165580141

次のようにメモ化すると、

(defparameter memoized-fib (memoize #'fib))

(time (funcall memoized-fib 40))
; Evaluation took:
;  4.338 seconds of real time
;  4.347672 seconds of total run time (4.347672 user, 0.000000 system)
;  100.23% CPU
;  11,568,512,880 processor cycles
;  55,152 bytes consed

あれ？全く速くなってない。fibの定義中の再帰呼び出しはメモ化されていない元の関数を呼び出しているからだ。そのためfibを以下のように再定義する必要がある。

(defun fib (n)
  (cond ((= n 0) 1)
	((= n 1) 1)
	(t (+ (funcall memoized-fib (1- n))
	      (funcall memoized-fib (- n 2))))))

(defparameter memoized-fib (memoize #'fib))

(time (funcall memoized-fib 40))
; Evaluation took:
;  0.000 seconds of real time
;  0.000039 seconds of total run time (0.000039 user, 0.000000 system)
;  100.00% CPU
;  93,196 processor cycles
;  0 bytes consed
  
165580141

これで一応高速化できたわけだけど、関数定義の中でその時点ではまだ定義されていない変数を使うのは気持ち悪いし、マクロを使えばもっと自然に書けるはずだ。

実はCommon Lisp用のメモ化ライブラリはもうあるのでそれを使えばいいのだった。

(def-memoized-function fib (n)
  (cond ((= n 0) 1)
	((= n 1) 1)
	(t (+ (fib (- n 1))
	      (fib (- n 2))))))

(time (fib 40))
; Evaluation took:
;   0.000 seconds of real time
;   0.000024 seconds of total run time (0.000021 user, 0.000003 system)
;   100.00% CPU
;   57,104 processor cycles
;   0 bytes consed