Home

Search

Python Memoize: Dictionary, functools.lru_cache

Understand the concept of memoization. Use the dictionary and functools.lru_cache.

dot net perls

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.Def
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.
Python program that memoizes with dictionary 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)) Output 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 (memozation) in a more compact and easy-to-maintain way. We can specify the max number of cache entries with maxsize.
Python program that uses lru_cache for memoization 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)) Output 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.
Math

A summary. Memoization is sometimes a useful optimization. And other times, it lends itself to excess memory use and slower execution times.

Home

© 2007-2020 sam allen. send bug reports to info@dotnetperls.com.