pythonlistfunctionrecursionmemoization

How to make a function memorize 2 variable function values?


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.


Solution

  • 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.