Memoizing a recursive function?
73 views
Skip to first unread message
logan
Jul 21, 2010, 5:47:12 PM7/21/10
to Clojure
Lets say I have the following function
(defn fib[n]
(if (> n 2)
(+ (fib (- n 2)) (fib (- n 1)))
1))
and I want to memoize it, what is the right way to do it?
Using the default memoize does not work correctly. the reason is even
though the first call to fib is memoized, the recursive calls go to
the original fib, and not the memoized function.
Even using
(def fib (memoize fib))
does not seem to work. if you run (fib 45) and (fib 46), in the ideal
case, (fib 47) should just call the memoized (fib 45) and (fib 46) and
return almost immediately, but that is not the case.
(defn fib[n]
(if (> n 2)
(+ (fib (- n 2)) (fib (- n 1)))
1))
and I want to memoize it, what is the right way to do it?
Using the default memoize does not work correctly. the reason is even
though the first call to fib is memoized, the recursive calls go to
the original fib, and not the memoized function.
Even using
(def fib (memoize fib))
does not seem to work. if you run (fib 45) and (fib 46), in the ideal
case, (fib 47) should just call the memoized (fib 45) and (fib 46) and
return almost immediately, but that is not the case.
dennis
Jul 22, 2010, 6:31:01 AM7/22/10
to Clojure
You should make a LazySeq to momoize intermediate result:
(defn fib[n]
(if (> n 2)
(+ (fib (- n 2)) (fib (- n 1)))
1))
(def fib (memoize fib))
(def fib-seq (map fib (iterate inc 0)))
then take the result by nth:
user=> (nth fib-seq 45)
1134903170
user=> (nth fib-seq 46)
1836311903
user=> (nth fib-seq 47)
2971215073
The only problem is that the fib-seq would cosume more memories to
hold intermediate result.
(defn fib[n]
(if (> n 2)
(+ (fib (- n 2)) (fib (- n 1)))
1))
(def fib-seq (map fib (iterate inc 0)))
then take the result by nth:
user=> (nth fib-seq 45)
1134903170
user=> (nth fib-seq 46)
1836311903
user=> (nth fib-seq 47)
2971215073
The only problem is that the fib-seq would cosume more memories to
hold intermediate result.
Mike Meyer
Jul 22, 2010, 7:19:35 AM7/22/10
to clo...@googlegroups.com, dusk...@gmail.com
On Wed, 21 Jul 2010 14:47:12 -0700 (PDT)
logan <dusk...@gmail.com> wrote:
logan <dusk...@gmail.com> wrote:
> Lets say I have the following function
>
> (defn fib[n]
> (if (> n 2)
> (+ (fib (- n 2)) (fib (- n 1)))
> 1))
>
> and I want to memoize it, what is the right way to do it?
Use defn-memo from clojure.contrib.def.
<mike
--
Mike Meyer <m...@mired.org> http://www.mired.org/consulting.html
Independent Network/Unix/Perforce consultant, email for more information.
O< ascii ribbon campaign - stop html mail - www.asciiribbon.org
Laurent PETIT
Jul 22, 2010, 7:25:12 AM7/22/10
to clo...@googlegroups.com, dusk...@gmail.com
Another solution, use the var, and then use memoize on your function as usual:
(defn fib[n]
(if (> n 2)
(+ (#'fib (- n 2)) (#'fib (- n 1))))
(of course this was to answer closely to the question. Nobody would write fib like that in practice : good general question, bad example)
HTH,
--
Laurent
2010/7/22 Mike Meyer <mwm-keyword-goo...@mired.org>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@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+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
Jules
Jul 22, 2010, 8:21:07 AM7/22/10
to Clojure
(def fib (memoize (lambda ...)))
On Jul 22, 1:25 pm, Laurent PETIT <laurent.pe...@gmail.com> wrote:
> Another solution, use the var, and then use memoize on your function as
> usual:
>
> (defn fib[n]
> (if (> n 2)
> (+ (#'fib (- n 2)) (#'fib (- n 1))))
>
> (of course this was to answer closely to the question. Nobody would write
> fib like that in practice : good general question, bad example)
>
> HTH,
>
> --
> Laurent
>
> 2010/7/22 Mike Meyer <mwm-keyword-googlegroups.620...@mired.org>
On Jul 22, 1:25 pm, Laurent PETIT <laurent.pe...@gmail.com> wrote:
> Another solution, use the var, and then use memoize on your function as
> usual:
>
> (defn fib[n]
> (if (> n 2)
> (+ (#'fib (- n 2)) (#'fib (- n 1))))
>
> (of course this was to answer closely to the question. Nobody would write
> fib like that in practice : good general question, bad example)
>
> HTH,
>
> --
> Laurent
>
>
>
>
> > On Wed, 21 Jul 2010 14:47:12 -0700 (PDT)
> > logan <duskli...@gmail.com> wrote:
>
> > > Lets say I have the following function
>
> > > (defn fib[n]
> > > (if (> n 2)
> > > (+ (fib (- n 2)) (fib (- n 1)))
> > > 1))
>
> > > and I want to memoize it, what is the right way to do it?
>
> > Use defn-memo from clojure.contrib.def.
>
> > <mike
> > --
> > Mike Meyer <m...@mired.org>
> >http://www.mired.org/consulting.html
> > Independent Network/Unix/Perforce consultant, email for more information.
>
> > O< ascii ribbon campaign - stop html mail -www.asciiribbon.org
>
> > --
> > You received this message because you are subscribed to the Google
> > Groups "Clojure" group.
> > To post to this group, send email to clo...@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+u...@googlegroups.com<clojure%2Bunsu...@googlegroups.com >
>
>
> > On Wed, 21 Jul 2010 14:47:12 -0700 (PDT)
> > logan <duskli...@gmail.com> wrote:
>
> > > Lets say I have the following function
>
> > > (defn fib[n]
> > > (if (> n 2)
> > > (+ (fib (- n 2)) (fib (- n 1)))
> > > 1))
>
> > > and I want to memoize it, what is the right way to do it?
>
> > Use defn-memo from clojure.contrib.def.
>
> > <mike
> > --
> > Mike Meyer <m...@mired.org>
> >http://www.mired.org/consulting.html
> > Independent Network/Unix/Perforce consultant, email for more information.
>
> > O< ascii ribbon campaign - stop html mail -www.asciiribbon.org
>
> > --
> > You received this message because you are subscribed to the Google
> > Groups "Clojure" group.
> > To post to this group, send email to clo...@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
Laurent PETIT
Jul 22, 2010, 8:36:46 AM7/22/10
to clo...@googlegroups.com, dusk...@gmail.com
nevermind, the following code does not work.
Paul Mooser
Jul 22, 2010, 7:51:09 PM7/22/10
to Clojure
Why not simply do:
(defn fib [n]
(println "called with " n)
I inserted the println to verify when we were actually calling the
function, and I believe this works - fib only seems to get invoked a
single time for any given n. Is this solution incorrect in some way?
(defn fib [n]
(println "called with " n)
(if (> n 2)
(+ (fib (- n 2)) (fib (- n 1)))
1))
(def fib (memoize fib))
(+ (fib (- n 2)) (fib (- n 1)))
1))
I inserted the println to verify when we were actually calling the
function, and I believe this works - fib only seems to get invoked a
single time for any given n. Is this solution incorrect in some way?
ajuc
Jul 23, 2010, 3:58:19 AM7/23/10
to Clojure
recur). For big values of n it could cause stack overflow.
logan
Jul 22, 2010, 6:56:32 PM7/22/10
to Clojure
I tried defn-memo .. it still does not appear to memoize the original
fib call? I tried this using clojure 1.2 beta. Reading the code
definition for defn-memo it seems like it should work, but calling
(fib 41) still takes a long time after calling (fib 40), when it
should basically be an instantaneous call if the memoization works
correctly.
Jules code works, except of course in clojure there is no lambda, but
fn.
On Jul 22, 5:36 am, Laurent PETIT <laurent.pe...@gmail.com> wrote:
> nevermind, the following code does not work.
>
> Jules' one is the right one
>
> 2010/7/22 Laurent PETIT <laurent.pe...@gmail.com>
fib call? I tried this using clojure 1.2 beta. Reading the code
definition for defn-memo it seems like it should work, but calling
(fib 41) still takes a long time after calling (fib 40), when it
should basically be an instantaneous call if the memoization works
correctly.
Jules code works, except of course in clojure there is no lambda, but
fn.
On Jul 22, 5:36 am, Laurent PETIT <laurent.pe...@gmail.com> wrote:
> nevermind, the following code does not work.
>
> Jules' one is the right one
>
>
>
>
> > Another solution, use the var, and then use memoize on your function as
> > usual:
>
> > (defn fib[n]
> > (if (> n 2)
> > (+ (#'fib (- n 2)) (#'fib (- n 1))))
>
> > (of course this was to answer closely to the question. Nobody would write
> > fib like that in practice : good general question, bad example)
>
> > HTH,
>
> > --
> > Laurent
>
> > 2010/7/22 Mike Meyer <mwm-keyword-googlegroups.620...@mired.org>
>
>
> > Another solution, use the var, and then use memoize on your function as
> > usual:
>
> > (defn fib[n]
> > (if (> n 2)
> > (+ (#'fib (- n 2)) (#'fib (- n 1))))
>
> > (of course this was to answer closely to the question. Nobody would write
> > fib like that in practice : good general question, bad example)
>
> > HTH,
>
> > --
> > Laurent
>
>
> > On Wed, 21 Jul 2010 14:47:12 -0700 (PDT)
> >> logan <duskli...@gmail.com> wrote:
>
> >> > Lets say I have the following function
>
> >> > (defn fib[n]
> >> > (if (> n 2)
> >> > (+ (fib (- n 2)) (fib (- n 1)))
> >> > 1))
>
> >> > and I want to memoize it, what is the right way to do it?
>
> >> Use defn-memo from clojure.contrib.def.
>
> >> <mike
> >> --
> >> Mike Meyer <m...@mired.org>
> >>http://www.mired.org/consulting.html
> >> Independent Network/Unix/Perforce consultant, email for more information.
>
> >> O< ascii ribbon campaign - stop html mail -www.asciiribbon.org
>
> >> --
> >> You received this message because you are subscribed to the Google
> >> Groups "Clojure" group.
> >> To post to this group, send email to clo...@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+u...@googlegroups.com<clojure%2Bunsu...@googlegroups.com >
> > On Wed, 21 Jul 2010 14:47:12 -0700 (PDT)
> >> logan <duskli...@gmail.com> wrote:
>
> >> > Lets say I have the following function
>
> >> > (defn fib[n]
> >> > (if (> n 2)
> >> > (+ (fib (- n 2)) (fib (- n 1)))
> >> > 1))
>
> >> > and I want to memoize it, what is the right way to do it?
>
> >> Use defn-memo from clojure.contrib.def.
>
> >> <mike
> >> --
> >> Mike Meyer <m...@mired.org>
> >>http://www.mired.org/consulting.html
> >> Independent Network/Unix/Perforce consultant, email for more information.
>
> >> O< ascii ribbon campaign - stop html mail -www.asciiribbon.org
>
> >> --
> >> You received this message because you are subscribed to the Google
> >> Groups "Clojure" group.
> >> To post to this group, send email to clo...@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
logan
Jul 22, 2010, 9:02:55 PM7/22/10
to Clojure
paul what version did you use? your version was the first one I tried,
and on 1.2 at least it does not work.
Jules version works, except lambda should be fn in clojure.
and on 1.2 at least it does not work.
Jules version works, except lambda should be fn in clojure.
Meikel Brandmeyer
Jul 23, 2010, 7:25:59 AM7/23/10
to Clojure
Hi,
On Jul 23, 3:02 am, logan <duskli...@gmail.com> wrote:
> paul what version did you use? your version was the first one I tried,
> and on 1.2 at least it does not work.
It works on 1.1. I guess there is some issue with the direct linking
introduced in 1.2.
Sincerely
Meikel
On Jul 23, 3:02 am, logan <duskli...@gmail.com> wrote:
> paul what version did you use? your version was the first one I tried,
> and on 1.2 at least it does not work.
introduced in 1.2.
Sincerely
Meikel
Mike Meyer
Jul 23, 2010, 9:25:08 AM7/23/10
to clo...@googlegroups.com, dusk...@gmail.com
[Context lost to top posting.]
On Thu, 22 Jul 2010 15:56:32 -0700 (PDT)
logan <dusk...@gmail.com> wrote:
> I tried defn-memo .. it still does not appear to memoize the original
> fib call? I tried this using clojure 1.2 beta. Reading the code
> definition for defn-memo it seems like it should work, but calling
> (fib 41) still takes a long time after calling (fib 40), when it
> should basically be an instantaneous call if the memoization works
> correctly.
Works fine on 1.1:
user> (defn-memo fib [n]
(println "Calling fib with arg --> " n)
(cond
(= n 0) 0
(= n 1) 1
:else (+ (fib (- n 1))
(fib (- n 2)))))
#'user/fib
user> (fib 40)
Calling fib with arg --> 40
[elided]
Calling fib with arg --> 0
102334155
user> (fib 41)
Calling fib with arg --> 41
165580141
user>
And yes, it's pretty much instantaneous. Possibly it's the same bug
that bit using the var in 1.2? Or maybe it's a different one.
Reply all
Reply to author
Forward
0 new messages