Spaces:
Sleeping
Sleeping
File size: 1,838 Bytes
6a86ad5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
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):
# get base sequence
F_i0 = base_seq(i)
F_i_cache = [F_i0]
cache.append(F_i_cache)
# XXX only works for m <= n cases
# generate assoc sequence
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
|