memoize_test.md

#clojure 入門者向け勉強会 #mitori_cljでClojureのメモ化関数についてこんなのどう？という提案をいただいたのでちょっと確認してみました。

結果はやっぱりだめでした。

(12/20 16:05)というのはうそでした。 指摘いただいたやりかたの実装が間違ってました。ひぇー。

以下は修正版です。

(defn fib [n]
  (do
     (println "-->" n)
     (if (<= n 1)
        n
        (+ (fib (dec n)) (fib (- n 2))))))

これを実行するとこう

user> (fib 4)
--> 4
--> 3
--> 2
--> 1
--> 0
--> 1
--> 2
--> 1
--> 0
3
user> (fib 5)
--> 5
--> 4
--> 3
--> 2
--> 1
--> 0
--> 1
--> 2
--> 1
--> 0
--> 3
--> 2
--> 1
--> 0
--> 1
5

関数が呼ばれると毎回計算します。

まずは普通にメモ化してみます。

(def fib-outmem (memoize fib))

実行するとこう

user> (fib-outmem 4)
--> 4
--> 3
--> 2
--> 1
--> 0
--> 1
--> 2
--> 1
--> 0
3
user> (fib-outmem 5)
--> 5
--> 4
--> 3
--> 2
--> 1
--> 0
--> 1
--> 2
--> 1
--> 0
--> 3
--> 2
--> 1
--> 0
--> 1
5

• 関数内部での呼び出しでメモ化が効いてません。
• 外部でも(fib 5)の呼び出しで(fib 4)の結果が使われていません。

提案いただいたのは、memoizeに無名関数を渡してやればいいのでは？というものなのでやってみます。

(def fib-inmem
  (memoize
   (fn [n]
     (do
       (println "-->" n)
       (if (<= n 1)
         n
         (+ (fib-inmem (dec n)) (fib-inmem (- n 2))))))))

実行してみると、ちゃんと動きます。

user> (fib-inmem 4)
--> 4
--> 3
--> 2
--> 1
--> 0
3
user> (fib-inmem 5)
--> 5
5

ちなみに、僕の作ったマクロでメモ化でやってもこうなります。(まちがえて5でやってしまった)

user> (fib-defmemo 5)
--> 5
--> 4
--> 3
--> 2
--> 1
--> 0
5
user> (fib-defmemo 6)
--> 6
8

なんというポカミスでしょう！！！！
やっぱりあわててやるといいことありませんね。