One thing to watch for as well is packratting. (def foo (memoize ...)) will
have a long-lived, global store of all the past results returned from the
memoized function. You may want to limit the memoization scope, in some
cases at least, to a local scope of some sort. To combine that with
recursion, a pattern like this works:
(defn proto-fib [f n]
(if (or (zero? n) (= n 1))
1
(+ (f f (dec n)) (f f (- n 2)))))
(let [mpf (memoize proto-fib)
fib #(mpf mpf %)]
(time (proto-fib proto-fib 30))
(time (proto-fib proto-fib 30))
(time (proto-fib proto-fib 40))
(time (proto-fib proto-fib 40))
(time (fib 30))
(time (fib 30))
(time (fib 40))
(time (fib 40)))
"Elapsed time: 180.976855 msecs"
"Elapsed time: 99.103625 msecs"
"Elapsed time: 11837.923979 msecs"
"Elapsed time: 11914.769097 msecs"
"Elapsed time: 1.5401 msecs"
"Elapsed time: 0.008399 msecs"
"Elapsed time: 0.12536 msecs"
"Elapsed time: 0.006843 msecs"
165580141
As you can see from the latter four timings, the fib function is memoized,
and the memoization applies to its recursive calls to itself, yet the
memoization cache is local to the let scope since the result of the
(memoize...) call does not escape from that scope. The cost is a bit more
setup, as the actual calculating function needs to take an added parameter
specifying what to call to recurse, so that a memoized version can later be
created in a local scope and then passed in as that parameter.
On Sat, Apr 13, 2013 at 1:02 PM, Liao Pengyu <arise...@gmail.com> wrote:
> I realize that this is my fault, I misunderstood the `memoize` and I
> search the mail list and find this issue already solved.
> Sorry to raise this issue again.
> The right way to use memoization with recursion is to use the "memoized"
> method in stead of call the raw "unmemoized" method.
> @Paulo Sérgio Almeida 's solution just the thing i wanted.
> BTW, I found the lazy way is more effective then TCO, the loop-recur I
> mean, and memoization. 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:
>> (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 for memoization:
>> user> (time ((memoize fib-nocur) 30))
>> "Elapsed time: 308.729 msecs"
>> 1346269
>> user> (time ((memoize fib-nocur) 30))
>> "Elapsed time: 314.942 msecs"
>> 1346269
>> user> (time ((memoize fib-nocur) 30))
>> "Elapsed time: 308.657 msecs"
>> 1346269
>>
>> Seems no effect. Since I just test it in nrepl and have no experience
>> about using clojure in project, I wander was the memoization really works?
>> Look forward to your responses
>>
> --
> --
> 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.
>
>
>
--
--
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.
