Memoize: Dictionary, functools.lru_cacheUnderstand the concept of memoization. Use the dictionary and functools.lru_cache.
Python
Memoize. A dictionary is often a cache. With a key we retrieve a stored value. We can use a dictionary, or functools, to perform caching.
Memoize, details. In a method call, we can turn the method parameters into a key, and store and retrieve values in a dictionary. This is called memoization.
Dictionary
Dictionary example. This program introduces compute(). This method receives one number and returns another. Compute() could be called many times with identical arguments.
And Each time, compute() must do its slow computations to calculate its result.
However If we add a dictionary cache, and memoize compute(), we must only do these computations once per key.
Info The first 10 calls to compute lead to stores within the dictionary. These calls are slower than a non-memoized compute method.
But In the last 5 calls, we use cached, memoized values. We avoid recomputing our values. We just do a dictionary lookup.
def compute(n): # Check the cache. if n in cache: return cache[n] # Do a computation. if n > 10: n = 10 v = n ** n if v > 1000: v /= 2 # Store the result. cache[n] = v return v # Cache is a dictionary. cache = {} # Test. print(compute(1)) print(compute(2)) print(compute(3)) print(compute(4)) print(compute(5)) print(compute(6)) print(compute(7)) print(compute(8)) print(compute(9)) print(compute(10)) # These use the cache. print(compute(1)) print(compute(2)) print(compute(3)) print(compute(4)) print(compute(5))
1 4 27 256 1562.5 23328.0 411771.5 8388608.0 193710244.5 5000000000.0 1 4 27 256 1562.5
Lru_cache. We can use functools to implement caching (memoization) in a more compact and easy-to-maintain way. We can specify the max number of cache entries with maxsize.
import functools @functools.lru_cache(maxsize=12) def compute(n): # We can test the cache with a print statement. if n > 10: n = 10 v = n ** n if v > 1000: v /= 2 return v # Fill up the cache. print(compute(1)) print(compute(2)) print(compute(3)) print(compute(4)) print(compute(5)) # Cache is hit now. print(compute(1)) print(compute(2)) print(compute(3)) print(compute(4)) print(compute(5))
1 4 27 256 1562.5 1 4 27 256 1562.5
Notes, memoization. Methods that are computationally intensive, use few different arguments and many identical calls, often become faster with memoization.
However Methods that receive a wide variety of arguments, or are called few times, become slower and receive no benefit.
Info Math methods can be memoized effectively if they are called with relatively few arguments in a program, and are slow to invoke.
A summary. Memoization is sometimes a useful optimization. And other times, it lends itself to excess memory use and slower execution times.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.