Python Memoize: Dictionary, functools.lru_cache

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

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Python Memoize: Dictionary, functools.lru_cache

Related Links:

.Net

Java

Related Links