|
|
from functools import wraps |
|
|
|
|
|
|
|
|
def recurrence_memo(initial): |
|
|
""" |
|
|
Memo decorator for sequences defined by recurrence |
|
|
|
|
|
Examples |
|
|
======== |
|
|
|
|
|
>>> from sympy.utilities.memoization import recurrence_memo |
|
|
>>> @recurrence_memo([1]) # 0! = 1 |
|
|
... def factorial(n, prev): |
|
|
... return n * prev[-1] |
|
|
>>> factorial(4) |
|
|
24 |
|
|
>>> factorial(3) # use cache values |
|
|
6 |
|
|
>>> factorial.cache_length() # cache length can be obtained |
|
|
5 |
|
|
>>> factorial.fetch_item(slice(2, 4)) |
|
|
[2, 6] |
|
|
|
|
|
""" |
|
|
cache = initial |
|
|
|
|
|
def decorator(f): |
|
|
@wraps(f) |
|
|
def g(n): |
|
|
L = len(cache) |
|
|
if n < L: |
|
|
return cache[n] |
|
|
for i in range(L, n + 1): |
|
|
cache.append(f(i, cache)) |
|
|
return cache[-1] |
|
|
g.cache_length = lambda: len(cache) |
|
|
g.fetch_item = lambda x: cache[x] |
|
|
return g |
|
|
return decorator |
|
|
|
|
|
|
|
|
def assoc_recurrence_memo(base_seq): |
|
|
""" |
|
|
Memo decorator for associated sequences defined by recurrence starting from base |
|
|
|
|
|
base_seq(n) -- callable to get base sequence elements |
|
|
|
|
|
XXX works only for Pn0 = base_seq(0) cases |
|
|
XXX works only for m <= n cases |
|
|
""" |
|
|
|
|
|
cache = [] |
|
|
|
|
|
def decorator(f): |
|
|
@wraps(f) |
|
|
def g(n, m): |
|
|
L = len(cache) |
|
|
if n < L: |
|
|
return cache[n][m] |
|
|
|
|
|
for i in range(L, n + 1): |
|
|
|
|
|
F_i0 = base_seq(i) |
|
|
F_i_cache = [F_i0] |
|
|
cache.append(F_i_cache) |
|
|
|
|
|
|
|
|
|
|
|
for j in range(1, i + 1): |
|
|
F_ij = f(i, j, cache) |
|
|
F_i_cache.append(F_ij) |
|
|
|
|
|
return cache[n][m] |
|
|
|
|
|
return g |
|
|
return decorator |
|
|
|
