2

I have a memoization decorator that looks like this:

def memoize(obj):
    from functools import wraps
    cache = {}

    @wraps(obj)
    def memoizer(*args, **kwargs):
        if args not in cache:
            cache[args] = obj(*args, **kwargs)
        return cache[args]

    return memoizer

However, I'm not sure this function works properly because it seems like to me it recreates cache as an empty dictionary every time the decorated function is called. When I test it with a simple fibonacci function, it does appear to memoize correctly. So is cache not recreated every time?

The python wiki has a version that includes this line:

cache = obj.cache = {}

So I am not sure what this does. I guess that python functions are objects so it is creating a new attribute associated with the function and is publically available/usable every time the function is called.

In either version, if I make repeated calls to the function, as in a recursive definition or just through repeated calls, how is the cache treated? Is it associated with the function, does it become a "global" variable, or something else?

qwr
  • 9,525
  • 5
  • 58
  • 102
  • "every time" - every *what*? It creates a new `cache` every time `memoize` is called, but `memoize` isn't called every time the memoized function is called. – user2357112 Jun 15 '17 at 22:00

1 Answers1

3

1) A new cache is created for each call to memoize(). But memoize() is called only once for each decorated function. Thus each decorated function has its own cache.

2) Concerning cache = obj.cache = {}:

Functions are also objects in Python. And as you already assumed, obj.cache = {} will create a new attribute on the wrapped function. The local cache object and the cache attribute on the wrapped function will point at the same dictionary.

This does not man that cache is a global variable - it's local in the memoize function and it's a attribute on the function.

If you have a decorated function f you could access f.cache on a global scope, if that's what you mean with a global variable.

If you call the decorated function repeatedly, it will always access the same cache specific to the decorated function.

To work around inner functions not beeing "memoized".

def outer():
    # do not add the decorator here!
    def inner():
        return 5
    if(not hasattr(outer, "inner")):
        # the "@" decorator is only syntactical sugar, 
        # we can simply call the decorator function to wrap another function
        outer.inner = memoize( inner )
    outer.inner()
    return outer.inner()

outer()
outer()
Mike Scotty
  • 10,530
  • 5
  • 38
  • 50
  • This answer might be better if you mentioned *closures* and that `memoizer` *closes over* its environment, including both `cache` and `obj`. (Also, there's no apostrophe in "its own.") – David Conrad Jun 15 '17 at 22:19
  • Brief follow up: I tested a decorated function defined inside another function, so every time the cache was reset. Is this because the function definition was gone after falling out of scope? – qwr Jun 16 '17 at 01:16
  • @qwr exactly. if you add ``print("memoize called", obj)`` to the memoize function you will see that the inner function changes if you call the outer function again. but if you call the inner function multiple times within the outer function it's still in the same scope. – Mike Scotty Jun 16 '17 at 08:44
  • @qwr I updated the answer to show how you can work around inner functions not beeing memoized, by making the inner function an attribute of the outer function. – Mike Scotty Jun 16 '17 at 08:54