Memoization of Imported Functions

Question

I'm creating a decorator to illustrate memoization. Per most folks, I'm using a recursively defined Fibonacci function.

I understand that naming the memoized version of the function differently than the original will result in inefficiency because the recursive calls will activate the unmemoized function. (See this old question, Memoization python function)

My issue is I can't seem to find the correct syntax to overwrite the name an imported function.

from fibonacci import fibonacci

def with_memoization(function):
    past_results = {}

    def function_with_memoization(*args):
        if args not in past_results:
            past_results[args] = function(*args)
        return past_results[args]
    return function_with_memoization


def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)


fib = with_memoization(fib)
fibonacci = with_memoization(fibonacci)

print(fib(100)) # completes in <1 second
print(fibonacci(100)) # completes in >2 minutes, probably hours

The imported fibonacci function and the fib function here are identical. What am I missing?

The problem is that the imported function is looking up its name in the module's namespace, not the namespace where you redefined the function. — Barmar
After from fibonacci import fibonacci, you have no name you can store the decorated function under that will be found recursively by fibonacci. Try import fibonacci instead, and use fibonacci.fibonacci to apply and call the decorator. — jasonharper
@jasonharper Lol, just got that myself. Thanks, write it up quick and I'll accept it.. — Joe Manlove
@jasonharper but will that work? The imported function will refer to itself via the local object from the module which has already been bound when the function was created. — Mark Ransom

Joe Manlove Joe Manlove · Accepted Answer · 2020-07-20T17:55:16

The from module import function statement aliases the function from the module as function. Therefore, when it gets decorated, only the alias is decorated. The recursive calls are to the unaliased function (in the module) i.e. the undecorated one.

You can think of this as creating a partial memory, the aliased function will remember the results of it's own calculations, but not the intermediate steps. In the code above, fibonacci(100) will be the only entry in dictionary when it's done. (Don't wait up for it.)

Using import module syntax doesn't alias the function, module.function is it's 'real' name. Therefore, decorations applied to fibonacci.fibonacci will also decorate the function that's being recursively called.

Working implementation:

import fibonacci

def with_memoization(function):

    past_results = {}

    def function_with_memoization(*args, **kwargs):
        if args not in past_results:
            past_results[args] = function(*args, **kwargs)
        return past_results[args]
    return function_with_memoization


fibonacci.fibonacci = with_memoization(fibonacci.fibonacci)

print(fibonacci.fibonacci(100))

Memoization of Imported Functions

1 Answers