Created
September 9, 2010 00:22
-
-
Save PaulHobbs/571117 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
(require '(clojure [zip :as zip])) | |
(defn memoize-calls | |
"Takes an expression, and replaces calls to func with cache checks, and calls | |
if cache is missing." | |
([func cache expr] (memoize-calls func cache expr (zip/seq-zip expr))) | |
([func cache expr pos] | |
(if (zip/end? pos) (zip/root pos) ; if at the end, return the tree. | |
(if (and (= func (zip/node pos)) | |
(empty? (zip/lefts pos))) | |
;; replace function call with if-let cache check expression | |
(let [args (zip/rights pos) | |
call (-> pos zip/up zip/node) | |
retval (gensym) | |
pos ;; write over pos with new expression | |
(-> pos zip/up | |
(zip/replace | |
`(if-let [~retval (get-in (deref ~cache) [~@args])] | |
~retval | |
(let [~retval (~func ~@args)] | |
(swap! ~cache assoc-in [~@args] ~retval) | |
~retval))))] | |
(recur func cache expr (zip/next pos))) ; keep traversing | |
;; if not at a function call, keep traversing (DFS) | |
(recur func cache expr (zip/next pos)))))) | |
(defmacro defn-memo-rec | |
"Replaces recursion with memoization checks" | |
[name args expr] | |
(let [cache (gensym) | |
new-expr (memoize-calls name cache expr)] | |
`(let [~cache (atom {})] | |
(defn ~name ~args | |
~new-expr)))) | |
(defn-memo-rec | |
fib [n] | |
(if (<= n 1) 1 | |
(+ (fib (dec n)) | |
(fib (- n 2))))) | |
(time (fib 1000)) | |
;; "Elapsed time: 52.709875 msecs" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment