Created
March 12, 2010 19:13
-
-
Save cgrand/330644 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; an answer to http://kotka.de/blog/2010/03/The_Rule_of_Three.html#summary | |
;; memoize from core.clj: | |
(defn memoize | |
[f] | |
(let [mem (atom {})] | |
(fn [& args] | |
(if-let [e (find @mem args)] | |
(val e) | |
(let [ret (apply f args)] | |
(swap! mem assoc args ret) | |
ret))))) | |
(defn f [& xs] | |
(println "Called with" xs) | |
xs) | |
;; parametrized-memoize: | |
(defn memoize2 | |
([f] (memoize2 f [{} identity assoc])) | |
([f [init cached assoc]] | |
(let [mem (atom init)] | |
(fn [& args] | |
(if-let [e (find (cached @mem) args)] | |
(val e) | |
(let [ret (apply f args)] | |
(swap! mem assoc args ret) | |
ret)))))) | |
(defn fifo-strategy [bound] | |
[[(into clojure.lang.PersistentQueue/EMPTY (repeat bound :dummy)) {}] | |
peek | |
(fn [[queue cache] args ret] | |
[(-> queue pop (conj args)) | |
(-> cache (dissoc (peek queue)) (assoc args ret))])]) | |
(comment | |
user=> (def g (memoize2 f (fifo-strategy 3))) | |
#'user/g | |
user=> (map g (range 3)) | |
(Called with (0) | |
Called with (1) | |
Called with (2) | |
(0) (1) (2)) | |
user=> (g 0) | |
(0) | |
user=> (g 3) | |
Called with (3) | |
(3) | |
user=> (g 0) | |
Called with (0) | |
(0) | |
) | |
;; but alas, no way to implement a lru-strategy | |
;; 2nd attempt at parametrizing memoize: | |
(defn memoize3 | |
([f] (memoize3 f [{} identity identity assoc])) | |
([f [init cached hit assoc]] | |
(let [mem (atom init)] | |
(fn [& args] | |
(if-let [e (find (cached @mem) args)] | |
(do | |
(swap! mem hit args) | |
(val e)) | |
(let [ret (apply f args)] | |
(swap! mem assoc args ret) | |
ret)))))) | |
(defn fifo-strategy [bound] | |
[[(into clojure.lang.PersistentQueue/EMPTY (repeat bound :dummy)) {}] | |
peek | |
(fn [mem args] mem) | |
(fn [[queue cache] args ret] | |
[(-> queue pop (conj args)) | |
(-> cache (dissoc (peek queue)) (assoc args ret))])]) | |
(defn lru-strategy [bound] | |
[[bound (into (sorted-map) (for [n (range bound)] [n :dummy])) {} {}] | |
peek | |
(fn [[tick lru-map last-uses cache] args] | |
[(inc tick) | |
(-> lru-map (dissoc (last-uses args)) (assoc tick args)) | |
(assoc last-uses args tick) | |
cache]) | |
(fn [[tick lru-map last-uses cache] args ret] | |
(let [[ltick largs] (first lru-map)] | |
[(inc tick) | |
(-> lru-map (dissoc ltick) (assoc tick args)) | |
(-> last-uses (dissoc largs) (assoc args tick)) | |
(-> cache (dissoc largs) (assoc args ret))]))]) | |
(comment | |
user=> (def g (memoize3 f (lru-strategy 3))) | |
#'user/g | |
user=> (map g (range 3)) | |
(Called with (0) | |
Called with (1) | |
Called with (2) | |
(0) (1) (2)) | |
user=> (g 0) | |
(0) | |
user=> (g 3) | |
Called with (3) | |
(3) | |
user=> (g 0) | |
(0) | |
user=> (g 1) | |
Called with (1) | |
(1) | |
) | |
;; but, wait, there's at least one bug! | |
;; if two threads try to concurrently memoize the exact same call | |
;; the capacity of the cache may definitely decrease! | |
;; so we have to verify that the entry of interest to us hasn't changed: | |
(defn memoize4 | |
([f] (memoize4 f [{} identity identity assoc])) | |
([f [init cached hit assoc]] | |
(let [mem (atom init) | |
hit-or-assoc (fn [mem args ret] | |
(if (find (cached mem) args) | |
(hit mem args) | |
(assoc mem args ret)))] | |
(fn [& args] | |
(if-let [e (find (cached @mem) args)] | |
(let [ret (val e)] | |
(swap! mem hit-or-assoc args ret) | |
ret) | |
(let [ret (apply f args)] | |
(swap! mem hit-or-assoc args ret) | |
ret)))))) | |
;; wait, there's a repetition! let's refactor: | |
(defn memoize5 | |
([f] (memoize5 f [{} identity (fn [mem args] mem) assoc])) | |
([f [init cached hit assoc]] | |
(let [mem (atom init) | |
hit-or-assoc (fn [mem args ret] | |
(if (find (cached mem) args) | |
(hit mem args) | |
(assoc mem args ret)))] | |
(fn [& args] | |
(let [ret (if-let [e (find (cached @mem) args)] (val e) (apply f args))] | |
(swap! mem hit-or-assoc args ret) | |
ret))))) | |
;; and to be sure that you only compute each entry once, | |
;; we first change memoize5 so that the returned value *is* | |
;; the cached value and not another equal value. | |
(defn memoize6 | |
([f] (memoize6 f [{} identity (fn [mem args] mem) assoc])) | |
([f [init cached hit assoc]] | |
(let [mem (atom init) | |
hit-or-assoc (fn [mem args ret] | |
(if (find (cached mem) args) | |
(hit mem args) | |
(assoc mem args ret)))] | |
(fn [& args] | |
(let [ret (if-let [e (find (cached @mem) args)] (val e) (apply f args)) | |
m (swap! mem hit-or-assoc args ret)] | |
(get (cached m) args)))))) | |
;; then we can build memoize7 on memoize6: | |
(defn memoize7 | |
([f] (memoize7 f [{} identity (fn [mem args] mem) assoc])) | |
([f strategy] | |
(comp deref (memoize6 #(delay (apply f %&)) strategy)))) | |
;; integrating memoize6 and memoize7 (inspired by Eugen Dück memoize7-variant | |
;; see http://groups.google.com/group/clojure/browse_thread/thread/36a13d150d830683 ) | |
(defn memoize8 | |
([f] (memoize8 f [{} identity (fn [mem args] mem) assoc])) | |
([f [init cached hit assoc]] | |
(let [mem (atom init) | |
hit-or-assoc (fn [mem args] | |
(if (contains? (cached mem) args) | |
(hit mem args) | |
(assoc mem args (delay (apply f args)))))] | |
(fn [& args] | |
(let [m (swap! mem hit-or-assoc args)] | |
(-> (cached m) (get args) deref)))))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment