For recursive one-shot memoized functions, I've been using this:
(defmacro memoized-fn [name args & body]
`(let [a# (atom {})]
(fn ~name ~args
(let [m# @a#
args# ~args]
(if-let [[_# v#] (find m# args#)]
v#
(let [v# (do ~...@body)]
(swap! a# assoc args# v#)
v#))))))
e.g.,
(memoized-fn fib [x]
(if (< n 2)
1
(+ (fib (- n 1)) (fib (- n 2)))))
If you need every last bit of performance, you can replace the atom-
map combination with a mutable Java HashMap.
-Jason
On Mar 18, 11:17 pm, B Smith-Mannschott <[email protected]> wrote:
> On Fri, Mar 19, 2010 at 06:56, Greg Fodor <[email protected]> wrote:
>
> > I would like to memoize bar such that the memory used for memoization
> > is GC'ed at the end of the call to foo, and additionally the cache
> > used for memoization is thread local (so no need for heavyweight
> > synchronization tools like atoms, etc.) In Ruby, I would implement
> > this as a simple local hash with the ||= operator through each
> > iteration of a loop inside foo that calls bar.
>
> ;; the "trick" I found is to explicitly deref the var binding the
> ;; function to be memoized. This way fib's recursive calls will use
> ;; the memoized binding established in
> ;; use-fib-memoized-thread-locally.
>
> (defn fib [n]
> (if (> 2 n) n
> (+ (@#'fib (dec n))
> (@#'fib (dec (dec n))))))
>
> (defn use-fib-memoized-thread-locally [n]
> (binding [fib (memoize fib)]
> (fib n)))
>
> ;; user> (time (fib 32))
> ;; "Elapsed time: 1755.796366 msecs" ;; SLOW
> ;; 2178309
> ;;
> ;; user> (time (use-fib-memoized-thread-locally 32))
> ;; "Elapsed time: 1.514927 msecs" ;; FAST
> ;; 2178309
> ;;
> ;; user> (time (fib 32))
> ;; "Elapsed time: 2024.836838 msecs" ;; SLOW, again
> ;; 2178309
>
> // Ben
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
To unsubscribe from this group, send email to
clojure+unsubscribegooglegroups.com or reply to this email with the words
"REMOVE ME" as the subject.
