I want to improve the performance of a recursive calculation of values
n = 100
def T(n,k):
q = 0
if n == 0 and k == 0:
return(1)
q = 1
if k>n or n<0:
return(0)
q = 1
if q != 1:
return(T(n-1,k-1)+n*T(n-1,k))
for i in range(n):
for n in range(i+1):
print(T(i,n))
print("*********")
However, I've only found ways to do this with functions that only take 1 argument, like this:
def mem(f):
memory = {}
def inner_function(x):
if x not in memory:
memory[x] = f(x)
return memory[x]
else:
return memory[x]
return inner_function
@mem
def fibonacci(n):
if n == 1 or n == 0:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
I was thinking of doing a 2d array, but I don't know yet (assuming it's possible) how the idea of doing so, with lists of lists, would help.
You can easily extend your mem
decorator to work with variable *args
parameters, looking them up in the memory
. This would work with **kwargs
, too, you'd have to convert them to a hashable type though, e.g. frozenset
of tuples
. And of course all parameters must be hashable for this.
def mem(f):
memory = {}
def inner_function(*args):
if args not in memory:
memory[args] = f(*args)
return memory[args]
return inner_function
Tested with your T
function, works fine. In practice, however, you might still want to use functools.lru_cache
.