Python Development, memoized functions.
Alec Mihailovs
alec at mihailovs.com
Fri Jan 5 10:11:45 CET 2007
From: "Antti Karttunen" <antti.karttunen at gmail.com>
> we can assume the existence of a "memoizating" decorator
> with just name M, so that A000045 could then just have a line like:
>
> %o A000045 (Python) @M def A000045(n): if(n < 2): return(n) else:
> return(A000045(n-1)+A000045(n-2))
>
> and this is then to be interpreted as
> @M
> def A000045(n): if(n < 2): return(n) else:
> return(A000045(n-1)+A000045(n-2))
>
> (where the exact implementation of M-decorator would be given in a
> separate
> file appendix of OEIS (like transforms.txt, etc.), containing possibly
> also
> some higher-order functionals, like those for computing records, positions
> of distinct values, etc.)
>
> Another idea is that we can tacitly assume that such
> a decorator should be used whenever the Python-definition
> uses recursion that would take aions to compute in ordinary way.
>
> I leave the implementation of practical, robust version of
> such decorator for somebody more experienced in Python.
> For a similar thing in Scheme, see the definition of definec macro
> for example in:
> http://www.research.att.com/~njas/sequences/a126000.scm.txt
I'm not sure how practical and robust that is, but that could be done as
def function_with_cache(f):
def new_f(*args):
if args in new_f.cache: return new_f.cache[args]
result=f(*args)
new_f.cache[args]=result
return result
new_f.cache={}
new_f.func_name=f.func_name
return new_f
with function_with_cache instead of M. For example,
@function_with_cache
def A000045(n):
if n<2: return n
return A000045(n-1)+A000045(n-2)
A000045(3)
2
A000045.cache
{(2,): 1, (0,): 0, (3,): 2, (1,): 1}
Or, another example,
@function_with_cache
def binomial(m,n):
if m <0 or n >m: return 0
if n==0 or m==n: return 1
return binomial(m-1,n)+binomial(m-1,n-1)
binomial(5,3)
10
binomial.cache
{(3, 2): 3, (3, 3): 1, (3, 1): 3, (2, 1): 2, (2, 0): 1, (4, 3): 4, (2, 2):
1, (4, 2): 6, (1, 0): 1, (1, 1): 1, (5, 3): 10}
Alec
More information about the SeqFan
mailing list