Another problem with (def fib (memoize ...)) for tight recursion patterns
with little code is the cost of accessing the var itself, which may also
prevent further optimizations. To restrict the scope of memoization and
obtain both simplicity and even more efficiency:
(letfn [(fib [x]
(memoize
#(if (or (zero? %) (= % 1))
1
(+ (fib (- % 1)) (fib (- % 2))))))]
(time (fib 30))
(time (fib 30))
(time (fib 40))
(time (fib 40)))
In cases like the first (fib 30) where no cached values exist yet, this is
almost 10 times faster than both versions above. Comparing the three
versions, fibmem3, the proto-fib, and this last one with letfn:
memoization 3:
"Elapsed time: 1.704 msecs"
"Elapsed time: 0.051 msecs"
"Elapsed time: 0.48 msecs"
"Elapsed time: 0.051 msecs"
memoization proto-fib:
"Elapsed time: 1.708 msecs"
"Elapsed time: 0.018 msecs"
"Elapsed time: 0.446 msecs"
"Elapsed time: 0.016 msecs"
memoization leftn
"Elapsed time: 0.206 msecs"
"Elapsed time: 0.0040 msecs"
"Elapsed time: 0.021 msecs"
"Elapsed time: 0.0030 msecs"
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
