Wed Jul 10 00:54:17 JST 2013

参照透過性と言えばメモ化

そういや誰かがHaskellではメモ化がデフォルトだと言ったので その場で一緒に確かめたらそんなことはなかった. 入出力まで含めて参照透過性を作ってしまったHaskellなんだから, 本当にそうであってもいいと思ったのに

Land of Lisp を読んでてヤバいメモ化を思いついた!と思ったけど 書いてみたら別にそんなことはなかった.

メモ化はメモ (cache) として例えばハッシュテーブルを使うけど

提案手法

関数そのものをデータを保存するためのものとして使うこと

そう言えばHaskellで経路探索問題を書く課題で、マップのデータとして 関数を使ってそんなことしてるのは私だけだったのを思い出した

-- 複数あるブロックの座標を与えます
b = [[1,3], [2,1], [5,3], [5,6]]
-- 私はこう書いた
b 1 3 = True
b 2 1 = True
b 5 3 = True
b 5 6 = True
b _ _ = False

だって、リストから具体的にデータを取得するの面倒でしょ getter関数どうせ定義するんでそ? 線形時間かかるし 私のなら、データを直接 getter関数として書くことになる

人に見せたら、このコードはやばいと言われたけれど

で、本題

;;  普通のメモ化関数
(define fib
  (let1 memo (make-hash-table)
  (lambda (n)
    (cond ((<= n 1) n)
          ((hash-table-get memo n #f) => values)
          (else
            (let1 ans (+ (fib (- n 1)) (fib (- n 2)))
            (hash-table-put! memo n ans)
            ans))))))

レキシカルスコープに変数 memo をハッシュテーブルとして作成 副作用満載にキャッシュを更新する

提案手法

ハッシュテーブルの構造を利用する代わりに、(memo n) という 手続きを作る (memo n) は (fib n) の答えを知らなければ #f を返す. 最初はただ #f を返す定数関数である. その時、memoという手続き自体を更新してしまう

(cond ((memo n) => values) ; values は恒等関数
      (else (update-memo! ...)))

こういう感じ 具体的に フィボナッチを計算するのは 下

(define (fib2 n)
  (define (memo n) #f)
  (cond ((<= n 1) n)
        ((memo n) => values)
        (else
          (let ((ans (+ (fib2 (- n 1)) (fib2 (- n 2))))
                (memo0 memo))
           (set! memo (lambda (m) (if (= m n) ans (memo0 m))))
           ans))))

(hash-table-get memo n #f) とかいう長いゲッターが (memo n) とかいう簡単になる、のはいいけれど、 手続きを更新するトコがちょっとやばい

あー、あのねー、 最初間違えてて、fib2からfibを呼び出してて、fibってのは はじめに書いた方 それで全然fibもfib2も速度変わらなくてすげーって思ってたんだけど

関数を毎回それを包み込む関数に更新するとかいうことして 残念ながら非常に遅いです

まあ、ただの冗談だってことで