Re: Memoizing a recursive function?
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 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 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 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.comclojure%2bunsubscr...@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 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
Re: Memoizing a recursive function?
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. On Jul 22, 4:51 pm, Paul Mooser taron...@gmail.com wrote: Why not simply do: (defn fib [n] (println called with n) (if ( n 2) (+ (fib (- n 2)) (fib (- n 1))) 1)) (def fib (memoize fib)) 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? -- 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
Re: Memoizing a recursive function?
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 -- 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
Re: Memoizing a recursive function?
Yes, because the code I posted still makes me wonder what's happening ... 2010/7/23 Meikel Brandmeyer m...@kotka.de 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 -- 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.comclojure%2bunsubscr...@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 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
Re: Memoizing a recursive function?
[Context lost to top posting.] On Thu, 22 Jul 2010 15:56:32 -0700 (PDT) logan duskli...@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. 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 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
Memoizing a recursive function?
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. -- 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
Re: Memoizing a recursive function?
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. On Jul 22, 5:47 am, 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? 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. -- 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
Re: Memoizing a recursive function?
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 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
Re: Memoizing a recursive function?
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 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 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.comclojure%2bunsubscr...@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 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
Re: Memoizing a recursive function?
(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 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 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.comclojure%2bunsubscr...@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 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
Re: Memoizing a recursive function?
nevermind, the following code does not work. Jules' one is the right one 2010/7/22 Laurent PETIT laurent.pe...@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-googlegroups.620...@mired.org 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 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.comclojure%2bunsubscr...@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 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
Re: Memoizing a recursive function?
Why not simply do: (defn fib [n] (println called with n) (if ( n 2) (+ (fib (- n 2)) (fib (- n 1))) 1)) (def fib (memoize fib)) 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? -- 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
Re: Memoizing a recursive function?
Here is what I get: (and BTW, my original version with #' seems to work, I'm a little bit puzzled ...) user= (defn fib [n] (println called with n) (if ( n 2) (+ (fib (- n 2)) (fib (- n 1))) 1)) (def fib (memoize fib)) #'user/fib user= user= #'user/fib user= (fib 6) called with 6 called with 4 called with 2 called with 3 called with 1 called with 2 called with 5 called with 3 called with 1 called with 2 called with 4 called with 2 called with 3 called with 1 called with 2 8 user= (defn fib [n] (println called with n) (if ( n 2) (+ (#'fib (- n 2)) (#'fib (- n 1))) 1)) (def fib (memoize fib)) #'user/fib user= user= #'user/fib user= (fib 6) called with 6 called with 4 called with 2 called with 3 called with 1 called with 5 8 user= 2010/7/23 Paul Mooser taron...@gmail.com Why not simply do: (defn fib [n] (println called with n) (if ( n 2) (+ (fib (- n 2)) (fib (- n 1))) 1)) (def fib (memoize fib)) 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? -- 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.comclojure%2bunsubscr...@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 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
