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]
(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)))
Calling fib just creates a new function, no values
are calculated. So
On Sunday, April 14, 2013 5:30:13 PM UTC+1, Jonathan Fischer Friberg wrote:
Calling fib just creates a new function, no values
are calculated. So you're measuring the time
it takes to create a function, and not the calculation
of fibonacci numbers.
Oops ;)
Of course you are right. The
Oops ;)
Of course you are right. The amazing thing is that the times I observed
fitted somehow the situation (the first (fib 30) call taking much more time
than the others, the third call more than the second and fourth) that I was
tricked into believing the calculations were being done and
Hi, there. I have a question about the memoization in clojure.
I compare two functions to test the performance improvement of memoization:
(defn fib [n]
(if (or (zero? n) (= n 1))
1
(+ (fib (dec n) ) (fib (- n 2)
(time (fib 30))
get the result:
Elapsed time: 316.65
...@gmail.com wrote:
Hi, there. I have a question about the memoization in clojure.
I compare two functions to test the performance improvement of memoization:
(defn fib [n]
(if (or (zero? n) (= n 1))
1
(+ (fib (dec n) ) (fib (- n 2)
(time (fib 30))
get the result
-nocur)]
(time (f 30))
(time (f 30))
(time (f 30)))
and see if the second and third times are much shorter than the first one.
On Sat, Apr 13, 2013 at 12:52 AM, Liao Pengyu arise...@gmail.com wrote:
Hi, there. I have a question about the memoization in clojure.
I compare two functions
And in cases like this recursive function, not only you need to do as above
said, but also you will want to make sure that the recursive calls use the
memoized function, otherwise, only top level results are getting the
benefit of memoization, resulting in the same tragic exponential time
about the memoization in clojure.
I compare two functions to test the performance improvement of
memoization:
(defn fib [n]
(if (or (zero? n) (= n 1))
1
(+ (fib (dec n) ) (fib (- n 2)
(time (fib 30))
get the result:
Elapsed time: 316.65 msecs
the memoization in clojure.
I compare two functions to test the performance improvement of memoization:
(defn fib [n]
(if (or (zero? n) (= n 1))
1
(+ (fib (dec n) ) (fib (- n 2)
(time (fib 30))
get the result:
Elapsed time: 316.65 msecs
1346269
And then test
a question about the memoization in clojure.
I compare two functions to test the performance improvement of
memoization:
(defn fib [n]
(if (or (zero? n) (= n 1))
1
(+ (fib (dec n) ) (fib (- n 2)
(time (fib 30))
get the result:
Elapsed time: 316.65 msecs
1346269
11 matches
Mail list logo
