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
– jonrsharpe, Commented May 11, 2019 at 7: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
– arcticless, Commented May 11, 2019 at 7:31
side note: if you want to use a function cache functools.lru_cache is probably the best choice. — hiro protagonist
– hiro protagonist, Commented May 11, 2019 at 7:37
See e.g. 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. — jonrsharpe
– jonrsharpe, Commented May 11, 2019 at 7: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
– Bogdan, Commented May 11, 2019 at 8:00

Michael H. · Accepted Answer · 2019-05-11 08:03:26Z

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.

Collectives™ on Stack Overflow

Understanding memoization in Python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related