無限にメモ化しない memoize

memoize で上限を設定できたらいいのになぁと思って、hackathonの時に作ってましたが Clojure Google Groupにそのものズバリのスレッドがありました。

bounded memoize
http://groups.google.com/group/clojure/browse_thread/thread/36a13d150d830683

議論の末、こうなったそうです。
まとめ
http://kotka.de/blog/2010/03/The_Rule_of_Three.html
http://kotka.de/blog/2010/03/memoize_done_right.html
奥深い！
atom の中に2つの値を突っ込んでatomなのに協調的に更新する技や、計算中に他のスレッドから同じ引数で呼ばれるという微妙な状況でも無駄に同じ計算をしないような工夫がされています。あまり理解できていないけど。

自分が作ったのはこれです。メモ用のマップとサイズカウント用の整数の2つの変数があるので、atom じゃなくて ref を使った方が良いのかもしれないですが、キャッシュ用だし別にいいだろと思考を止めてしまいました。あと指定サイズから溢れ始めたら、一番古くに使われた要素を特定するのに last が O(n) 食ってしまっています。

(defn my-memoize
  [f size]
  (let [mem (atom {})
	cnt (atom 0)]
    (fn [& args]
      (if-let [e (find @mem args)]
	(do (swap! mem #(assoc (dissoc % (key e)) args (val e)))
	    (println @mem)
	    (val e))
        (let [ret (apply f args)]
	  (if (>= @cnt size)
	    (swap! mem #(assoc (dissoc % (key (last %))) args ret))
	    (do (swap! mem assoc args ret)
		(swap! cnt inc)))
	  (println @mem)
	  ret)))))
;キャッシュを見るためにprintlnしてます。

来月は 5/8(土) にHackathonが開催されます。 Tokyo.clj #2