Understanding memoization in Python

Question

I would like to understand memoization in Python better. In an online class I am taking, the following example is provided:

def memoize(func):
    memo_dict = {}
    def wrapper(*args):
        if args not in memo_dict:
            memo_dict[args] = func(*args)
        return memo_dict[args]
    return wrapper

@memoize
def find_divisors_memo(n):
    divisors = []
    for i in range(1, n+1):
        if n % i == 0:
            divisors.append(i)
    return divisors

I am trying to find the numerical values stored in memo_dict after running a few examples, e.g.:

find_divisors_memo(100000009)
find_divisors_memo(100000008)

I do:

for x,y in memo_dict.items():      
        print(x,y)

and it says: NameError: name 'memo_dict' is not defined.

`memo_dict` isn't global, it's local to `memoize` and only available to `wrapper` via the *closure*. — jonrsharpe, May 11 '19 at 07:29
Hello Bogdan, i suppose you are executing the for outside the function. The problem here is that the memo_dict = {} is local to the function and you can't call it from outside. If you'll put your for inside, it will work. — arcticless, May 11 '19 at 07:31
side note: if you want to use a function cache [`functools.lru_cache`](https://docs.python.org/3/library/functools.html#functools.lru_cache) is probably the best choice. — hiro protagonist, May 11 '19 at 07:37
See e.g. https://stackoverflow.com/q/55320884/3001761 for how to access the closure contents. You can also make the dictionary an attribute on the `wrapper` function, so it's more easily accessible, like in [this implementation](https://stackoverflow.com/a/17268784/3001761). — jonrsharpe, May 11 '19 at 07:39
Dear all, thank you for your help and comments. If you could please offer a more precise solution -- how shall I change the code. I am still learning a lot about python. — Bogdan, May 11 '19 at 08:00

score 2 · Answer 1 · answered May 11 '19 at 08:03

If you want to have a look at the dict for the purpose of understanding memoization, you can add a few print statements:

def memoize(func):
    memo_dict = {}
    def wrapper(*args):
        if args not in memo_dict:
            memo_dict[args] = func(*args)
        else:
            print('using cached value')
        print(memo_dict.items())
        return memo_dict[args]
    return wrapper

@memoize
def find_divisors_memo(n):
    print('function called')
    divisors = []
    for i in range(1, n+1):
        if n % i == 0:
            divisors.append(i)
    return divisors

Now you can see the items of the dict in every function call.
Also, you'll see how memoization works: If you call the function with a specific parameter for the first time, the function is actually called. If you call it a second time with the same parameter, it does not actually call the function (which could be a very computation-intensive function), but instead uses the cached value from the dict.

If you want to use caching in a real project, I recommend functools.lru_cache. Also, there are other cache implementations available in a (non-stdlib) library named cachetools.

Understanding memoization in Python

1 Answers1