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 clo
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
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 tha
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 outp
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?'.
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
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
direc
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 (de
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
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
> dependenci
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
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)
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
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
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 transla
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 memoiza
16 matches
Mail list logo
