メモ化のメモ

再帰関数を効率の良いコードに直せ、と言われてパッと思い浮かぶのが

• ループに還元
• 末尾再帰

これくらいしかないと思ってた。メモ化なんて選択肢もあるのね。

• 関数の値のメモワイズ -- On Lisp (邦訳)

計算コストの高い関数を同じ引数で複数回呼び出したいときがあるなら，値をメモワイズ(memoize)しておくのが得だ．以前の返り値をみな保管しておき，関数が呼び出される度にまず保管場所を見て，値が既に得られていないか調べる．

memoize 関数のコードはここでは省くとして、ハッシュをキャッシュに使えるのかと知ってひとつ賢くなった気分。

;; ベタベタな2重再帰フィボナッチ定義
(setf (symbol-function 'fibo)
      (memoize #'(lambda (n)
                   (cond ((= n 0) 0)
                         ((= n 1) 1)
                         (t (+ (fibo (- n 1))
                               (fibo (- n 2))))))))
(time (fibo 1000))     ; on xyzzy
Real time: 3.219 sec.
;=>4346655768693745643568852767504062580256466051737178040248172908
   9536555417949051890403879840079255169295922593080322634775209689
   6232398733224711616429964409065331879382989696499285160037044761
   37795166849228875

速っ！

ここでもうひとつ、最近自分が弄っている newLISP でもメモ化を使う方法があるのでご紹介を。 といっても newLISP にはハッシュ関数がないのでコンテキストで代用ですが。

Speed up with memoization -- newLISP Code Patterns

(define-macro (memoize mem-func func)
  (set (sym mem-func mem-func)
       (letex (f func  c mem-func)
         (lambda ()
           (or (context c (string (args)))
               (context c (string (args)) (apply f (args))))))))

(memoize fibo (lambda (n)
                (cond ((= n 0) 0)
                      ((= n 1) 1)
                      (true (+ (fibo (- n 1))
                               (fibo (- n 2)))))))
(time (fibo:fibo 100))
;=>0

newLISP のコンテキストは Common Lisp の簡易版パッケージ機能と考えていいでしょう。たぶん。 ここではキャッシュ用に名前空間 fibo を作成して、そこに関数値を放り込んだり参照したりしてます。

;; コンテキスト使用例
; 検索
(context MAIN "define")         ;=> define <407ee9>
(context MAIN "kosh")           ;=> nil

; 登録
(context MAIN "kosh" "lisper?")
(context MAIN "kosh")           ;=> "lisper?"

※ただし戻り値の正確さは (fibo:fibo 90) くらいで限界なんですが…多倍長整数に弱い？