# Python memoization decorator

I have spent all night whipping up this recipe. It's my first Python decorator. I feel like I have a full understanding of how decorators work now and I think I came up with a good object-oriented algorithm to automatically provide memoization. Please let me know what you think.

I made a few quick changes after pasting it in here so please let me know if my changes broke something (don't have an interpreter on hand).

"""This provides a way of automatically memoizing a function. Using this eliminates the need for extra code. Below is an example of how it would be used on a recursive Fibonacci sequence function:

def fib(n):
if n in (0, 1): return n
return fib(n - 1) + fib(n - 2)

fib = memoize(fib)

That's all there is to it. That is nearly identical to the following:

_memos = {}
def fib(n):
if n in _memos:
return _memos[n]
if n in (0, 1):
_memos[n] = n
return _memos[n]
_memos[n] = fib(n - 1) + fib(n - 2)
return _memos[n]

The above is much more difficult to read than the first method. To make things even simpler, one can use the memoize function as a decorator like so:

@memoize
def fib(n):
if n in (0, 1): return n
return fib(n - 1) + fib(n - 2)

Both the first and third solutions are completely identical. However, the latter is recommended due to its elegance. Also, note that functions using keywords will purposely not work. This is because this memoization algorithm does not store keywords with the memos as it HEAVILY increases the CPU load. If you still want this functionality, please implement it at your own risk."""
class memoize:

"""Gives the class it's core functionality."""
def __call__(self, *args):
if args not in self._memos:
self._memos[args] = self._function(*args)
return self._memos[args]

def __init__(self, function):
self._memos = {}
self._function = function

# Please don't ask me to implement a get_memo(*args) function.

"""Indicated the existence of a particular memo given specific arguments."""
def has_memo(self, *args):
return args in self._memos

"""Returns a dictionary of all the memos."""
@property
def memos(self):
return self._memos.copy()

"""Remove a particular memo given specific arguments. This is particularly useful if the particular memo is no longer correct."""
def remove_memo(self, *args):
del self._memos[args]

"""Removes all memos. This is particularly useful if something that affects the output has changed."""
def remove_memos(self):
self._memos.clear()

"""Set a particular memo. This is particularly useful to eliminate double-checking of base cases. Beware, think twice before using this."""
def set_memo(self, args, value):
self._memos[args] = value

"""Set multiple memos. This is particular useful to eliminate double-checking of base cases. Beware, think twice before using this."""
def set_memos(self, map_of_memos):
self._memos.update(map_of_memos)

• Why would you need anything else than __call__ and __init__? – Quentin Pradet Feb 29 '12 at 9:55
• Did you read the comments for the set_memo(self, args, value) and set_memos(self, map_of_memos)? Eliminating particular base cases will usually not make too big of a difference. Also, something that the function uses may update and one may want to remove some or all values to recalculate them. I can't think of examples where one would want to do this, but I thought I'd throw it in there for the heck of it. – Tyler Crompton Feb 29 '12 at 17:12
• __contains__ instead of has_memo ? Then you can ask 10 in fib. – Adrian Panasiuk Mar 4 '12 at 2:02
• @AdrianPanasiuk, ah, didn't think about that. Thanks! – Tyler Crompton Mar 4 '12 at 20:46
• is it like lru cash, cause its in standart python there – user8426627 May 27 '19 at 18:23

## 2 Answers

The first thing that came to mind looking at your code was: style.

There's a particular reason for placing your doc-strings above the functions instead of below? The way you're doing it will show None in the __doc__ attribute.

IMHO Some of that strings are not even doc-strings:

def __call__(self, *args)
"""Gives the class its core functionality."""
# ...


It doesn't really say much. Keep also in mind that comments are for the programmers, docstrings for the users.

• PEP8 tells you all about this style guide,
• and PEP257 is specifically about Docstring Conventions.

Also I didn't like very much that you put the __call__ method before __init__, but I don't know if that is just me, or there's some convention about that.

Cleared this, I'm failing in founding the point in all your methods that you've written beside __init__ and __call__. What's their use? Where your code is using them?
If you need something write the code for it, otherwise don't. Or you'll be writing for something that you don't need and that will probably not match your hypothetical requires of tomorrow.

I get that you were probably doing an exercise to learn about decorators, but when implementing something, don't ever write code just for the heck of it.

Let's take a deeper look at your non-doc strings, like this one:

"""Removes all memos. This is particularly useful if something that affects the output has changed."""
def remove_memos(self):
self._memos.clear()


That should probably just be:

def remove_memos(self):
"""Removes all memos."""
self._memos.clear()


And nothing more. What on earth does "This is particularly useful if something that affects the output has changed." this means? "something that affects the output has changed"? It's all very strange and confusing. Also, how will your decorator know that "something that affects the output has changed"?

There's nothing in here:

def __call__(self, *args):
if args not in self._memos:
self._memos[args] = self._function(*args)
return self._memos[args]


that does that or that uses any of the other methods. Also you seem to not being able to provide a scenario where they might be used (and even if you could there's still no way to use them).

My point is that all those additional methods are useless, probably it wasn't write them if you learned some Python, but that is as far as their use is gone.

• I haven't really used docstrings that much so thank you for the tips. I sorted the methods in alphabetical order. (It's easier to find a method that way). But that really doesn't matter at all. Perhaps I was gold plating but I can see the extra methods' purposes so I went ahead and implemented them. They can be useful in some scenarios. There's no requirement to use them. – Tyler Crompton Mar 1 '12 at 21:12
• @TylerCrompton: (1) Don't applay the alphabetical order to __init__, because others are expecting to find it at the beginning if it's implemented. (Take a look into the python standard library code :) I can't also stress this enough: your coding style is important if you want others to read/use/share your code. (2) Which scenario? If you can't provide one they're useless. – Rik Poggi Mar 2 '12 at 12:35
• In regards to number 2, have a look at the docstrings. Surely those will provide enough information as to what scenarios that they would be good for. – Tyler Crompton Mar 3 '12 at 8:20
• @TylerCrompton: No offense, but I've already read your non-doc strings, yet I don't see how those methods could be used. – Rik Poggi Mar 3 '12 at 22:08
• Perhaps you misunderstand. I do understand the my docstrings are wrong. I get that. The "something that affects the output has changed" phrase means if one is accessing global variables and that variable changes and by doing so affects the output. The decorator isn't supposed to know when it changes. It's the programmers responsibility to detect that. If I want to clear the memos. I would just do function_name.remove_memos(). – Tyler Crompton Mar 4 '12 at 20:45
"""Gives the class it's core functionality."""
def __call__(self, *args):
if args not in self._memos:
self._memos[args] = self._function(*args)
return self._memos[args]


It's more idiomatic (and faster) to "ask for forgivness rather than ask for permission", e.g.:

def __call__(self, *args):
try:
return self._memos[args]
except KeyError:
value = self._function(*args)
self._memos[args] = value
return value

• Didn't know about this idiom. I tend to use exceptions only to denote really unusual situations (eg. "file not found"). – Quentin Pradet Feb 29 '12 at 8:36
• It's actually optimal to use in Python for several reasons. See books.google.se/… for further reading :) – rreillo Feb 29 '12 at 10:49
• Thanks for the reference! I was using a C idiom. By the way, EAFP is also defined in the docs glossary – Quentin Pradet Feb 29 '12 at 11:01
• Shouldn't that be a KeyError? – Winston Ewert Feb 29 '12 at 16:57
• @raba, Does storing the result in a temporary variable really make that much of a difference? Just curious. – Tyler Crompton Feb 29 '12 at 17:09