Ask Your Question

Is there a kind of memoization in Sage build in?

asked 2012-02-09 09:21:57 -0500

petropolis gravatar image

updated 2015-01-16 03:17:46 -0500

FrédéricC gravatar image

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?

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted

answered 2012-02-09 12:08:35 -0500

DSM gravatar image

updated 2012-02-09 13:30:25 -0500

Yes.. 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..
sage: f(10)

(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)
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 but I wouldn't recommend them for production use..

edit flag offensive delete link more



You 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.

William Stein gravatar imageWilliam Stein ( 2012-02-09 17:26:38 -0500 )edit

Just for clarity, that example isn't a true tail-call since you take the result and do something with it, namely adding 1.

Ivan Andrus gravatar imageIvan Andrus ( 2012-02-09 23:02:06 -0500 )edit

I wondered if someone was going to call me out on that. :-)

DSM gravatar imageDSM ( 2012-02-10 00:56:17 -0500 )edit

answered 2012-02-10 02:55:28 -0500

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I 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([])
edit flag offensive delete link more


Kind 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??`.

DSM gravatar imageDSM ( 2012-02-10 03:18:59 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2012-02-09 09:21:57 -0500

Seen: 611 times

Last updated: Feb 10 '12