sympy/utilities/memoization.py

   1
   2 def recurrence_memo(initial):
   3     """
   4     Memo decorator for sequences defined by recurrence
   5
   6     See usage examples e.g. in the specfun/combinatorial module
   7     """
   8     cache = initial
   9     def decorator(f):
  10         def g(n):
  11             L = len(cache)
  12             if n <= L - 1:
  13                 return cache[n]
  14             for i in xrange(L, n+1):
  15                 cache.append(f(i, cache))
  16             return cache[-1]
  17         return g
  18     return decorator
  19
  20
  21 def assoc_recurrence_memo(base_seq):
  22     """
  23     Memo decorator for associated sequences defined by recurrence starting from base
  24
  25     base_seq(n) -- callable to get base sequence elements
  26
  27     XXX works only for Pn0 = base_seq(0) cases
  28     XXX works only for m <= n cases
  29     """
  30
  31     cache = []
  32     def decorator(f):
  33         def g(n,m):
  34             L = len(cache)
  35             if n < L:
  36                 return cache[n][m]
  37
  38             for i in xrange(L,n+1):
  39                 # get base sequence
  40                 F_i0 = base_seq(i)
  41                 F_i_cache = [F_i0]
  42                 cache.append(F_i_cache)
  43
  44                 # XXX only works for m <= n cases
  45                 # generate assoc sequence
  46                 for j in xrange(1,i+1):
  47                     F_ij = f(i,j, cache)
  48                     F_i_cache.append(F_ij)
  49
  50             return cache[n][m]
  51
  52         return g
  53     return decorator
  54
  55
  56