Unhashable type 'dict' error in memoize decorator-CodePudding

I'm writing a memoize decorator but I get a unhashable type 'dict' error when trying it on a simple example. Here is my code:

def memoize(func):
    """Store the results of the decorated function for fast lookup
    """
    # Store results in a dict that maps arguments to results
    cache = {}
    # Define the wrapper function to return
    def wrapper(*args, **kwargs):
        # If these arguments haven't been seen before, 
        if (args, kwargs) not in cache:
            # Call func() and store the result.
            cache[(args, kwargs)] = func(*args, **kwargs)
        return cache[(args, kwargs)]
    return wrapper

And here is a simple function created to test my decorator:

import time

@memoize
def slow_func(a, b):
    print("Sleeping...")
    time.sleep(5)
    return a  b

slow_func(2, 7)

I end up with this error:

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
~\AppData\Local\Temp/ipykernel_17888/3627587563.py in <module>
----> 1 slow_func(2, 7)

~\AppData\Local\Temp/ipykernel_17888/52581778.py in wrapper(*args, **kwargs)
      7     def wrapper(*args, **kwargs):
      8         # If these arguments haven't been seen before,
----> 9         if (args, kwargs) not in cache:
     10             # Call func() and store the result.
     11             cache[(args, kwargs)] = func(*args, **kwargs)

TypeError: unhashable type: 'dict'

I tested just in case if my Python was working properly with: (2, 3) not in {} which resulted in the correct output True.

Any help would be appreciated!

CodePudding user response：

The reason this raises an exception is that when you use **kwargs in a function definition, the variable kwargs will be of type dict. dictionaries are mutable and unhashable; this means they cannot be used as keys in another dict or as elements in a set. When you do cache[(args, kwargs)], you are trying to use the dict kwargs as part of a key in the dict cache, hence the error. If you don't need to implement the memoization function yourself, you can use the lru_cache function from the functools module in the standard library:

import functools, time

@functools.lru_cache
def slow_func(a, b):
    print("Sleeping...")
    time.sleep(5)
    return a   b


t1 = time.monotonic()
slow_func(2, 7)
slow_func(2, 7)
t2 = time.monotonic()
print("Total time:", t2-t1)

prints:

python t.py
Sleeping...
Total time: 5.005460884000058

CodePudding user response：

In this case, args are (2, 3) and the kwargs is an empty dictionary (since you did not pass any named args into your function call). However, dictionaries are mutable and cannot be used as keys in another dictionary and therefore are not hashable.

So where do we go from here? You could ignore kwargs entirely but you would still hit a problem when args itself contains a dictionary: slow_func({"key": 1}) would cause the same issue since the arg {key: 1} is itself a dictionary.

This appears to me to be a memoization for a very specific type of function. Meaning, a wrapper like this can't be blindly applied to any function. Does the order of arguments matter? If it does, memoizing just the args being present isn't enough. Putting some guards rails around the args would make the memoization predictable and easier.

The simplest workaround here is to only allow certain kinds or args or values for kwargs. Ex: all args and all kwarg values must be floats or ints.

That being said, if you need to memoize kwargs as well, you would have to parse the dictionary and any dict types in args and store the format in some hashable format.

One approach that comes to mind is that you could store parsed args and kwargs in a custom class which implements the __hash__ data method (more on that here: Making a python user-defined class sortable, hashable) and then store it in your cache. But again this all really depends on how you intend for this memoize decorator to be used.

EDIT: That being said, as others have pointed out, the standard functools library contains some utility methods already for caching: https://docs.python.org/3/library/functools.html#functools.cache