ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 10 Feb 2012 03:18:59 -0600Is there a kind of memoization in Sage build in?http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/Maple knows an option called 'remember' which allows the coding of a function with a recursive definition in a natural manner without a loss of efficiency (exponential time to compute often can be reduced to linear time). Does Sage have a similar option?Thu, 09 Feb 2012 09:21:57 -0600http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/Answer by DSM for <p>Maple knows an option called 'remember' which allows the coding of a function with a recursive definition in a natural manner without a loss of efficiency (exponential time to compute often can be reduced to linear time). Does Sage have a similar option?</p>
http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?answer=13262#post-id-13262Yes.. and no. There *is* a memoization decorator, called CachedFunction (or cached_function), and it can be applied easily:
sage: @CachedFunction
....: def f(x):
....: print 'slow call..'
....: sleep(5)
....: return x**2
....:
sage: f(10)
slow call..
100
sage: f(10)
100
(Or, equally, `g = cached_function(f)` or `h = CachedFunction(f)`.)
Unfortunately you can still blow the recursion stack:
sage: @CachedFunction
....: def r(x):
....: return 1 if x<= 1 else 1+r(x-1)
....:
sage: r(20)
20
sage: r(2000)
[...]
RuntimeError: maximum recursion depth exceeded while calling a Python object
CPython doesn't do tail-recursion optimization, so writing recursive functions isn't as natural. If you're interested, there are [some ways around this](http://groups.google.com/group/sage-flame/browse_thread/thread/845077dcd78c4f32?pli=1) but I wouldn't recommend them for production use..
Thu, 09 Feb 2012 12:08:35 -0600http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?answer=13262#post-id-13262Comment by William Stein for <p>Yes.. and no. There <em>is</em> a memoization decorator, called CachedFunction (or cached_function), and it can be applied easily:</p>
<pre><code>sage: @CachedFunction
....: def f(x):
....: print 'slow call..'
....: sleep(5)
....: return x**2
....:
sage: f(10)
slow call..
100
sage: f(10)
100
</code></pre>
<p>(Or, equally, <code>g = cached_function(f)</code> or <code>h = CachedFunction(f)</code>.)</p>
<p>Unfortunately you can still blow the recursion stack:</p>
<pre><code>sage: @CachedFunction
....: def r(x):
....: return 1 if x<= 1 else 1+r(x-1)
....:
sage: r(20)
20
sage: r(2000)
[...]
RuntimeError: maximum recursion depth exceeded while calling a Python object
</code></pre>
<p>CPython doesn't do tail-recursion optimization, so writing recursive functions isn't as natural. If you're interested, there are <a href="http://groups.google.com/group/sage-flame/browse_thread/thread/845077dcd78c4f32?pli=1">some ways around this</a> but I wouldn't recommend them for production use..</p>
http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?comment=20316#post-id-20316You can increase the recursion depth using e.g., "import sys; sys.setrecursionlimit(10000)". However, watch out -- if you make it too big, you'll just crash Python completely. Thu, 09 Feb 2012 17:26:38 -0600http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?comment=20316#post-id-20316Comment by Ivan Andrus for <p>Yes.. and no. There <em>is</em> a memoization decorator, called CachedFunction (or cached_function), and it can be applied easily:</p>
<pre><code>sage: @CachedFunction
....: def f(x):
....: print 'slow call..'
....: sleep(5)
....: return x**2
....:
sage: f(10)
slow call..
100
sage: f(10)
100
</code></pre>
<p>(Or, equally, <code>g = cached_function(f)</code> or <code>h = CachedFunction(f)</code>.)</p>
<p>Unfortunately you can still blow the recursion stack:</p>
<pre><code>sage: @CachedFunction
....: def r(x):
....: return 1 if x<= 1 else 1+r(x-1)
....:
sage: r(20)
20
sage: r(2000)
[...]
RuntimeError: maximum recursion depth exceeded while calling a Python object
</code></pre>
<p>CPython doesn't do tail-recursion optimization, so writing recursive functions isn't as natural. If you're interested, there are <a href="http://groups.google.com/group/sage-flame/browse_thread/thread/845077dcd78c4f32?pli=1">some ways around this</a> but I wouldn't recommend them for production use..</p>
http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?comment=20315#post-id-20315Just for clarity, that example isn't a true tail-call since you take the result and do something with it, namely adding 1. Thu, 09 Feb 2012 23:02:06 -0600http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?comment=20315#post-id-20315Comment by DSM for <p>Yes.. and no. There <em>is</em> a memoization decorator, called CachedFunction (or cached_function), and it can be applied easily:</p>
<pre><code>sage: @CachedFunction
....: def f(x):
....: print 'slow call..'
....: sleep(5)
....: return x**2
....:
sage: f(10)
slow call..
100
sage: f(10)
100
</code></pre>
<p>(Or, equally, <code>g = cached_function(f)</code> or <code>h = CachedFunction(f)</code>.)</p>
<p>Unfortunately you can still blow the recursion stack:</p>
<pre><code>sage: @CachedFunction
....: def r(x):
....: return 1 if x<= 1 else 1+r(x-1)
....:
sage: r(20)
20
sage: r(2000)
[...]
RuntimeError: maximum recursion depth exceeded while calling a Python object
</code></pre>
<p>CPython doesn't do tail-recursion optimization, so writing recursive functions isn't as natural. If you're interested, there are <a href="http://groups.google.com/group/sage-flame/browse_thread/thread/845077dcd78c4f32?pli=1">some ways around this</a> but I wouldn't recommend them for production use..</p>
http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?comment=20314#post-id-20314I wondered if someone was going to call me out on that. :-) Fri, 10 Feb 2012 00:56:17 -0600http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?comment=20314#post-id-20314Answer by petropolis for <p>Maple knows an option called 'remember' which allows the coding of a function with a recursive definition in a natural manner without a loss of efficiency (exponential time to compute often can be reduced to linear time). Does Sage have a similar option?</p>
http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?answer=13263#post-id-13263I do not know what is going on behind the scenes of decorater '@CachedFunction'. But perhaps it works similar as in this example:
def A000213(x) :
if x <= 1 : return 1
if x in dictfun : return dictfun[x]
dictfun[x] = A000213(x-3) + A000213(x-2) + A000213(x-1)
return dictfun[x]
dictfun = dict([])
A000213(20)
Fri, 10 Feb 2012 02:55:28 -0600http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?answer=13263#post-id-13263Comment by DSM for <p>I do not know what is going on behind the scenes of decorater '@CachedFunction'. But perhaps it works similar as in this example:</p>
<pre><code>def A000213(x) :
if x <= 1 : return 1
if x in dictfun : return dictfun[x]
dictfun[x] = A000213(x-3) + A000213(x-2) + A000213(x-1)
return dictfun[x]
dictfun = dict([])
A000213(20)
</code></pre>
http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?comment=20313#post-id-20313Kind of (although it checks "if x in dictfun" first). You can read the documentation by typing `CachedFunction?` and look at the actual source code for the decorator by typing `CachedFunction??`.Fri, 10 Feb 2012 03:18:59 -0600http://ask.sagemath.org/question/8624/is-there-a-kind-of-memoization-in-sage-build-in/?comment=20313#post-id-20313