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 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 pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.
This page was last updated on Sep 16, 2022 (edit link).