>
> 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
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
>
> (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 calc
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]
tion. Using build-in lazy funciton perform better.
>
> On Saturday, April 13, 2013 12:52:28 PM UTC+8, Liao Pengyu wrote:
>>
>> Hi, there. I have a question about the memoization in clojure.
>> I compare two functions to test the performance improvement of
>> memoization:
&g
re. 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 res
> > (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
> > >
> wrote:
> >>
> >>
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
beh
nefit from its memory.
>
> So, try this:
>
> (let [f (memoize fib-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 wrot
gyu 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))
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: 3
11 matches
Mail list logo
