SICPを読む(108) 問題 3.27 - メモ化

Scheme

いよいよメモ化

問題 3.27

以下が何をやってるのか説明せよという問題。

普段でも使えるように改造版にしてみた。

(define (memoize f)
  (let ((table '()))
    (lambda x
      (let ((prev-result (assoc x table)))
        (if prev-result
            (cdr prev-result)
            (let ((result (apply f x)))
              (set! table (cons (cons x result) table))
              result))))))

(define memo-fib
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else
                     (+ (memo-fib (- n 1))
                        (memo-fib (- n 2))))))))

(trace memo-fib)
(memo-fib 1000)
; 43466557686937456435688527675040625802564660517371780402481729089536555
;  4179490518904038798400792551692959225930803226347752096896232398733224
;  71161642996440906533187938298969649928516003704476137795166849228875

メモ化スゲーーーーーーーーーーーーーーーーーーーーーーー。

お前再帰だろ。再帰らしく無限ループしてろよ！！

と、ちと興奮気味。

説明

あ、そだそだ、説明ね。

ちなみに再帰フィボナッチの演算回数は、

f(0) = 1
f(1) = 1
f(n) = f(n - 1) + f(n - 2) + 1

nの演算には、自分自身の演算と、一個前と、二個前の演算回数を足し合わせたものになる。

と、フィボナッチっぽい式になります。

再帰でフィボナッチ1000をやろうと思ったら、宇宙が誕生するより長い時間がかかっちゃう事になりそうなので止めたほうがいいと思う。


フィボナッチでは、同じ計算を何度もしてるのが問題で、同じ計算なら


「キャッシュを使えばいいじゃねぇか」


となる訳。これをメモ化という。メモ化がやることは単純で、

  • f(5)の計算を前にやってたら、キャッシュからf(5)の計算結果を返す。
  • f(5)の計算をしていなければ、計算して、キャッシュに貯める。


となる。


f(5)でシミュレートすると、

f(5)を見る。キャッシュが無い。
f(4)を見る。キャッシュが無い。
f(3)を見る。キャッシュが無い。
f(2)を見る。キャッシュが無い。
f(1)を見る。キャッシュが無い。
f(1)の演算結果をキャッシュに貯めて返す。
f(0)を見る。キャッシュが無い。
f(0)の演算結果をキャッシュに貯めて返す。
f(2)の演算結果をキャッシュに貯めて返す。
f(1)を見る。キャッシュヒット。
f(3)の演算結果をキャッシュに貯めて返す。
...どんどんキャッシュを返すだけ。

従って、1度呼び出すだけなら反復のほうが早い。


一度f(1000)を実行してしまえば、次にf(1000)を呼出した時に、キャッシュヒットして、O(1)で返すので、何度も同じ演算を必要とする場合、メモ化はかなり使える。


次。

memo-fibを(memoize fib)と定義してもいいか。という設問。

ムリ。

fibを呼び出しちゃうので、ソレはダメ。1個しかキャッシュしない。

memoize > fib > memoize > fib ... と呼び出す必要があるので、memoizeは関数をフックさせるマクロになってないとダメ。


メモ化を手に入れた。ぐへへへ。

問題はten million(10,000,000)オーダーのメモリをどうするかってことだよな・・・