Re: much lower recursion depth with memoization
I posted an article detailing the approaches I outlined earlier in this thread: http://programming-puzzler.blogspot.com/2013/09/defeating-stack-overflows.html -- -- 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.
Re: much lower recursion depth with memoization
Of course John, the reason you can do the sum of 1-200 in your head is thanks to Gauss's formula, I'm assuming you're not really recursing 200 times in your head :) Love your blog too BTW, especially your style of presentation and the types of things you write about (i.e. non-trivial but still widely interesting). On Tuesday, September 24, 2013 5:12:19 AM UTC+10, John Lawrence Aspden wrote: > > James, it will generate a stack overflow on a sufficiently large problem, > certainly. > > Most of the cases where recursions are a good idea are order (n^2) and > worse algorithms, though, so the question is rather 'will the stack > overflow before the heap is exhausted or the processor catches fire?'. > There are usually ways of dealing with cases where the recursion is just > an iteration. > > A stack depth of 100 should be livable with. A stack depth of 200 > means the machine has trouble with problems I can do in my head. > > Cheers, John. > > > > On Monday, September 23, 2013 12:50:28 AM UTC+1, James Reeves wrote: >> >> On 23 September 2013 00:28, John Lawrence Aspden >> wrote: >> >>> Nice, but it won't work for me, since I'm trying to avoid computing all >>> the values in the table, and so I can't use the pump-priming approach. I >>> don't know what values I'm going to need primed! >>> I'm sure there are ways round it, but I think they're all complicated >>> and ugly. >>> >>> I think I'll translate my program into python, where presumably it will >>> just work. Or actually you've reminded me about Racket. I used to like that >>> when it was PLT scheme. >>> >> >> As far as I can tell, the code you have will generate a stack overflow in >> any language. It's not tail recursive, and the first time you run the >> function it can't draw from the cache. >> >> - James >> > -- -- 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.
Re: much lower recursion depth with memoization
Puzzler, thanks for all your excellent ideas!
I get the impression that you're as troubled as I am by the brokenness of
recursion, but it looks like it can be worked around.
A bit of memory thrown at the JVM stack combined with a better memoization
technique should work in most of the cases that trampoline and recur miss.
It's obviously not ideal that the stack and heap can't coexist under one
limit, but worst case that means that you need twice as much memory as you
should. I can live with that.
John.
On Monday, September 23, 2013 8:59:19 AM UTC+1, puzzler wrote:
>
> Sorry, I wrote that implementation off-the-cuff and then realized that
> breadth-first search doesn't actually give you an appropriate dependency
> ordering. In the above examples I gave, I had:
> => (all-dependencies 30)
> (0 1 3 2 5 6 7 10 12 20 15 25 30)
> which isn't right because 20 depends on 15 which doesn't come before 20 in
> the list.
>
> You want to do depth-first search, adding nodes in post-traversal order.
> There are several ways of going about this; here is one way that will
> hopefully be clear:
>
> (defn all-dependencies [n]
> (loop [stack []
> unprocessed [n]
> processed {}]
> (if (empty? unprocessed) stack
> (let [i (peek unprocessed)
> status (processed i)]
> (case status
> :done (recur stack (pop unprocessed) processed),
> :seen-once (recur (conj stack i) (pop unprocessed) (assoc
> processed i :done)),
> (recur stack (into unprocessed (dependencies i))
> (assoc processed i :seen-once)))
>
> Items start out in `unprocessed` and eventually get added to the `stack`
> accumulator which holds the final dependency list. (I called it `stack`
> because, essentially, you're building the "call stack" that would be built
> by the memoized recursive function.) A map called `processed` tracks the
> status of items, marking whether they have been partially or fully
> processed.
>
> The first time we see an item in `unprocessed`, we mark it as :seen-once
> (in the `processed` map), but keep it in `unprocessed`, adding all its
> dependencies to `unprocessed` as well. The second time we see the item in
> `unprocessed`, we can conclude that all its dependencies have already been
> fully processed, and therefore can mark this item as :done and move it to
> the final `stack`.
>
> Now it works:
>
> => (all-dependencies 30)
> [3 2 7 0 5 10 15 1 6 12 20 25 30]
>
> The important thing to note here is that all-dependencies is a general
> strategy (known as topological sorting), and you can just pick an
> implementation and use it for any sort of memoization/priming task. All
> you need to do is code the `dependencies` function in a way that mirrors
> your recursive dependencies, and plug it into this or another similar
> implementation of topological sort.
>
--
--
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.
Re: much lower recursion depth with memoization
Jim, increasing the stack size solved the problem in so far as it allowed the code to run (I needed a tree depth of 2000), but then it just sat and churned for hours and ran down the battery bank on my narrowboat, so I killed it. This morning I bit the bullet and got the clojure program to output a short C program to solve the problem. It took quarter of an hour to write and 65 seconds to run. Thanks for you kind words! There'll almost certainly be a blog post about this at some point. John. > -- -- 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.
Re: much lower recursion depth with memoization
James, it will generate a stack overflow on a sufficiently large problem, certainly. Most of the cases where recursions are a good idea are order (n^2) and worse algorithms, though, so the question is rather 'will the stack overflow before the heap is exhausted or the processor catches fire?'. There are usually ways of dealing with cases where the recursion is just an iteration. A stack depth of 100 should be livable with. A stack depth of 200 means the machine has trouble with problems I can do in my head. Cheers, John. On Monday, September 23, 2013 12:50:28 AM UTC+1, James Reeves wrote: > > On 23 September 2013 00:28, John Lawrence Aspden > > > wrote: > >> Nice, but it won't work for me, since I'm trying to avoid computing all >> the values in the table, and so I can't use the pump-priming approach. I >> don't know what values I'm going to need primed! >> I'm sure there are ways round it, but I think they're all complicated and >> ugly. >> >> I think I'll translate my program into python, where presumably it will >> just work. Or actually you've reminded me about Racket. I used to like that >> when it was PLT scheme. >> > > As far as I can tell, the code you have will generate a stack overflow in > any language. It's not tail recursive, and the first time you run the > function it can't draw from the cache. > > - James > -- -- 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.
Re: much lower recursion depth with memoization
Chris, thank you! That looks like the explanation, which cheers me up immensely, since it should be easy to work round. I looked at the same memoize code and it never occured to me that that was what was going on. I just thought Clojure hated me. A combination of fixing memoize and increasing the stack size should give me as much recursion as a man could reasonably need. John. On Monday, September 23, 2013 2:13:12 PM UTC+1, Chris Perkins wrote: > > On Sunday, September 22, 2013 5:28:37 PM UTC-6, John Lawrence Aspden wrote: >> >> This recursion limit really is quite nasty. I could probably live with >> 4000, but 200? And why would memoization make it worse anyway? >> >> >> The factor of 20-or-so smaller recursion limit comes not from memoize > directly, but from apply, which appears to use a relatively enormous amount > of stack space. > > I suspect that since AFn.applyToHelper dispatches on up to 20 arguments, > that stack space for all 20 is always used, even if you only pass, say, one > argument. > > - Chris Perkins > > -- -- 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.
Re: much lower recursion depth with memoization
On Sunday, September 22, 2013 5:28:37 PM UTC-6, John Lawrence Aspden wrote: > > This recursion limit really is quite nasty. I could probably live with > 4000, but 200? And why would memoization make it worse anyway? > > > The factor of 20-or-so smaller recursion limit comes not from memoize directly, but from apply, which appears to use a relatively enormous amount of stack space. I suspect that since AFn.applyToHelper dispatches on up to 20 arguments, that stack space for all 20 is always used, even if you only pass, say, one argument. - Chris Perkins -- -- 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.
Re: much lower recursion depth with memoization
as Armando pointed out unless you remove the stack-issue memoization is not going become your friend. My take would be to simply use loop/recur and then you can memoize 'relentlessly', as Rich likes to put it :) (defn gauss-recurse [n] (loop [i n acc n] (if (zero? i) acc (recur (dec i) (+ acc (dec i)) Jim :) ps: increasing the stack-size is not a real solution, is it?btw, I love your blog posts! On 23/09/13 00:34, John Lawrence Aspden wrote: Ah, it turns out that adding this :jvm-opts ["-Xss50M"] to project.clj gets me about 25000 memoized self-calls, so that will do. Last time I had to worry about stack size I was programming an 8051 . I'd forgotten! Cheers, John. -- -- 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.
Re: much lower recursion depth with memoization
Sorry, I wrote that implementation off-the-cuff and then realized that
breadth-first search doesn't actually give you an appropriate dependency
ordering. In the above examples I gave, I had:
=> (all-dependencies 30)
(0 1 3 2 5 6 7 10 12 20 15 25 30)
which isn't right because 20 depends on 15 which doesn't come before 20 in
the list.
You want to do depth-first search, adding nodes in post-traversal order.
There are several ways of going about this; here is one way that will
hopefully be clear:
(defn all-dependencies [n]
(loop [stack []
unprocessed [n]
processed {}]
(if (empty? unprocessed) stack
(let [i (peek unprocessed)
status (processed i)]
(case status
:done (recur stack (pop unprocessed) processed),
:seen-once (recur (conj stack i) (pop unprocessed) (assoc
processed i :done)),
(recur stack (into unprocessed (dependencies i))
(assoc processed i :seen-once)))
Items start out in `unprocessed` and eventually get added to the `stack`
accumulator which holds the final dependency list. (I called it `stack`
because, essentially, you're building the "call stack" that would be built
by the memoized recursive function.) A map called `processed` tracks the
status of items, marking whether they have been partially or fully
processed.
The first time we see an item in `unprocessed`, we mark it as :seen-once
(in the `processed` map), but keep it in `unprocessed`, adding all its
dependencies to `unprocessed` as well. The second time we see the item in
`unprocessed`, we can conclude that all its dependencies have already been
fully processed, and therefore can mark this item as :done and move it to
the final `stack`.
Now it works:
=> (all-dependencies 30)
[3 2 7 0 5 10 15 1 6 12 20 25 30]
The important thing to note here is that all-dependencies is a general
strategy (known as topological sorting), and you can just pick an
implementation and use it for any sort of memoization/priming task. All
you need to do is code the `dependencies` function in a way that mirrors
your recursive dependencies, and plug it into this or another similar
implementation of topological sort.
--
--
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.
Re: much lower recursion depth with memoization
On Sun, Sep 22, 2013 at 8:54 PM, Mark Engelberg wrote:
> When you're doing memoization and you have a lot of "holes" in the inputs,
> one option is to have two phases to your function. The first phase takes
> the initial input and then computes a collection of all the inputs that are
> dependencies and need to be computed ahead of time. Then in phase two, you
> can "prime the pump" with that particular sequence of inputs. If you need
> help on this, I can give you a concrete example of how to do this.
>
OK, here's a concrete example. Let's say you have a recursive function f
that, for every n>5, is dependent on (f (- n 5)) and (f (quot n 2)). We'll
assume that the formula is not recursive for inputs in (range 5) and that
these are the base cases.
It's not obvious how to prime the pump here, so we need to compute it.
First, we express the dependencies:
(defn dependencies [n]
(if (< n 5) [] [(- n 5) (quot n 2)]))
Next, we do a tail-recursive breadth-first search:
(defn all-dependencies [n]
(loop [stack ()
unprocessed (conj clojure.lang.PersistentQueue/EMPTY n)
processed #{}]
(if (empty? unprocessed) stack
(let [i (peek unprocessed)]
(if (processed i)
(recur stack (pop unprocessed) processed)
(recur (conj stack i)
(into unprocessed (dependencies i))
(conj processed i)))
Now, we can run all-dependencies to get back the list of inputs to prime
the pump:
=> (all-dependencies 20)
(0 3 2 5 7 10 15 20)
=> (all-dependencies 30)
(0 1 3 2 5 6 7 10 12 20 15 25 30)
--
--
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.
Re: much lower recursion depth with memoization
James: It's extremely difficult to overflow the stack in Racket, because the stack isn't arbitrarily limited to some small value -- it does some tricks so that the stack is only limited by your total available memory. For me, having to worry about stack overflows is definitely one of the biggest pain points in Clojure. Clojure provides a few workarounds for the common cases (recur, trampoline, lazy-seq), but there are some scenarios where you really just need ample stack. John: When you're doing memoization and you have a lot of "holes" in the inputs, one option is to have two phases to your function. The first phase takes the initial input and then computes a collection of all the inputs that are dependencies and need to be computed ahead of time. Then in phase two, you can "prime the pump" with that particular sequence of inputs. If you need help on this, I can give you a concrete example of how to do this. Another option to consider: I wrote a blog entry about how to use core.async to convert a stack-consuming computation into stackless with minimal transformation to your program. I haven't tried this technique yet in any serious program, but it's worth investigating: http://programming-puzzler.blogspot.com/2013/07/stackless-clojure-with-coreasync_7.html -- -- 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.
Re: much lower recursion depth with memoization
With memoize there are additional calls (the new function and apply) per recursion, so I guess that will produce the stack overflow to happen sooner. You can use memoization once you remove the stack issue with iteration: (defn gauss-iter [n] (letfn [(f [n acc] (if (< n 1) acc (recur (dec n) (+ acc (dec n)] (f n n))) (def gauss-memo (memoize gauss-iter)) On Sunday, September 22, 2013 8:19:23 AM UTC-7, John Lawrence Aspden wrote: > > Hi Guys, > > I'm trying to memoize a fairly complicated double recursion, and it's > blowing stack after not terribly many calls. > > I've reduced the problem to a simple test case, summing from 1 to n : > > user=> (clojure-version) > "1.5.1" > user=> (def gauss-recurse (fn [n] (if (< n 1) 0 (+ n (gauss-recurse (dec > n)) > #'user/gauss-recurse > user=> (gauss-recurse 3500) > 6126750 > user=> (def gauss-memoized (memoize (fn [n] (if (< n 1) 0 (+ n > (gauss-memoized (dec n))) > #'user/gauss-memoized > user=> (gauss-memoized 160) > > StackOverflowError clojure.lang.RT.boundedLength (RT.java:1654) > user=> > > > Does anyone know why this would happen? Do I just have to give up on > memoization and find another way to do dynamic programming? > > Cheers, John. > -- -- 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.
Re: much lower recursion depth with memoization
On 23 September 2013 00:28, John Lawrence Aspden wrote: > Nice, but it won't work for me, since I'm trying to avoid computing all > the values in the table, and so I can't use the pump-priming approach. I > don't know what values I'm going to need primed! > I'm sure there are ways round it, but I think they're all complicated and > ugly. > > I think I'll translate my program into python, where presumably it will > just work. Or actually you've reminded me about Racket. I used to like that > when it was PLT scheme. > As far as I can tell, the code you have will generate a stack overflow in any language. It's not tail recursive, and the first time you run the function it can't draw from the cache. - James -- -- 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.
Re: much lower recursion depth with memoization
Ah, it turns out that adding this :jvm-opts ["-Xss50M"] to project.clj gets me about 25000 memoized self-calls, so that will do. Last time I had to worry about stack size I was programming an 8051 . I'd forgotten! Cheers, John. -- -- 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.
Re: much lower recursion depth with memoization
Nice, but it won't work for me, since I'm trying to avoid computing all the values in the table, and so I can't use the pump-priming approach. I don't know what values I'm going to need primed! I'm sure there are ways round it, but I think they're all complicated and ugly. I think I'll translate my program into python, where presumably it will just work. Or actually you've reminded me about Racket. I used to like that when it was PLT scheme. This recursion limit really is quite nasty. I could probably live with 4000, but 200? And why would memoization make it worse anyway? Is it possible to increase the stack size somehow? Or would that use up all the memory? Cheers, John. On Sunday, September 22, 2013 6:40:11 PM UTC+1, puzzler wrote: > > Check out my blog article from last year and search for the spot where I > describe the "priming the pump" trick: > > http://programming-puzzler.blogspot.com/2012/11/coin-change-kata-in-racket-and-clojure.html > > If the simplest way to write the solution to your problem is to use a > top-down form of memoization, you can still avoid blowing the stack by > running it in a bottom-up fashion a la traditional dynamic programming. > > > On Sun, Sep 22, 2013 at 8:19 AM, John Lawrence Aspden < > asp...@googlemail.com > wrote: > >> Hi Guys, >> >> I'm trying to memoize a fairly complicated double recursion, and it's >> blowing stack after not terribly many calls. >> >> I've reduced the problem to a simple test case, summing from 1 to n : >> >> user=> (clojure-version) >> "1.5.1" >> user=> (def gauss-recurse (fn [n] (if (< n 1) 0 (+ n (gauss-recurse (dec >> n)) >> #'user/gauss-recurse >> user=> (gauss-recurse 3500) >> 6126750 >> user=> (def gauss-memoized (memoize (fn [n] (if (< n 1) 0 (+ n >> (gauss-memoized (dec n))) >> #'user/gauss-memoized >> user=> (gauss-memoized 160) >> >> StackOverflowError clojure.lang.RT.boundedLength (RT.java:1654) >> user=> >> >> >> Does anyone know why this would happen? Do I just have to give up on >> memoization and find another way to do dynamic programming? >> >> Cheers, John. >> >> -- >> -- >> 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 >> --- >> 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+u...@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.
Re: much lower recursion depth with memoization
Check out my blog article from last year and search for the spot where I describe the "priming the pump" trick: http://programming-puzzler.blogspot.com/2012/11/coin-change-kata-in-racket-and-clojure.html If the simplest way to write the solution to your problem is to use a top-down form of memoization, you can still avoid blowing the stack by running it in a bottom-up fashion a la traditional dynamic programming. On Sun, Sep 22, 2013 at 8:19 AM, John Lawrence Aspden < aspd...@googlemail.com> wrote: > Hi Guys, > > I'm trying to memoize a fairly complicated double recursion, and it's > blowing stack after not terribly many calls. > > I've reduced the problem to a simple test case, summing from 1 to n : > > user=> (clojure-version) > "1.5.1" > user=> (def gauss-recurse (fn [n] (if (< n 1) 0 (+ n (gauss-recurse (dec > n)) > #'user/gauss-recurse > user=> (gauss-recurse 3500) > 6126750 > user=> (def gauss-memoized (memoize (fn [n] (if (< n 1) 0 (+ n > (gauss-memoized (dec n))) > #'user/gauss-memoized > user=> (gauss-memoized 160) > > StackOverflowError clojure.lang.RT.boundedLength (RT.java:1654) > user=> > > > Does anyone know why this would happen? Do I just have to give up on > memoization and find another way to do dynamic programming? > > Cheers, John. > > -- > -- > 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.
much lower recursion depth with memoization
Hi Guys, I'm trying to memoize a fairly complicated double recursion, and it's blowing stack after not terribly many calls. I've reduced the problem to a simple test case, summing from 1 to n : user=> (clojure-version) "1.5.1" user=> (def gauss-recurse (fn [n] (if (< n 1) 0 (+ n (gauss-recurse (dec n)) #'user/gauss-recurse user=> (gauss-recurse 3500) 6126750 user=> (def gauss-memoized (memoize (fn [n] (if (< n 1) 0 (+ n (gauss-memoized (dec n))) #'user/gauss-memoized user=> (gauss-memoized 160) StackOverflowError clojure.lang.RT.boundedLength (RT.java:1654) user=> Does anyone know why this would happen? Do I just have to give up on memoization and find another way to do dynamic programming? Cheers, John. -- -- 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.
