C# Memoization

Use memoization to speed up repeat calls to a method by caching arguments and results.

Memoization. This is way to optimize repeated method calls. With the memoization optimization technique, we store the results of a method as it is called.

Notes, strategy. When a method is called with the same arguments a second time, we use the lookup table to return them. We avoid recomputing.Optimization

An example. This code example shows us how to implement memoization with a Dictionary. We try to avoid recomputing lowercased strings with a cache.

Lowercase1: The first function is much simpler. It calls ToLower on the string argument each time and returns it.

ToLower

Lowercase2: The second is more complex. It checks the Dictionary. If it finds a match, it doesn't recalculate the lowercase string.

And: If no match is found, it calls ToLower and stores the result in the Dictionary, then returns the result.

Dictionary

C# program that uses memoization using System; using System.Collections.Generic; class Program { static void Main() { string result1 = Lowercase1("Test"); string result2 = Lowercase2("Test"); // Call Lowercase2. string result3 = Lowercase2("Test"); // Call Lowercase2 again. Console.WriteLine("{0} {1} {2}", result1, result2, result3); } static string Lowercase1(string value) { return value.ToLower(); } static Dictionary<string, string> _lowercase = new Dictionary<string, string>(); static string Lowercase2(string value) { string lookup; if (_lowercase.TryGetValue(value, out lookup)) return lookup; lookup = value.ToLower(); _lowercase[value] = lookup; return lookup; } } Output test test test

Benchmark. To check the performance advantage, I used a benchmark harness and timed the cost of lowercasing the string "Test" one million times and took the average.Benchmark

Version 1: This version of the code does not use the caching optimization. It does not memoize the results.

Version 2: This version uses a static Dictionary to store the results of its computations, and avoids many string creations.

Static Dictionary

Result: It is faster to cache. But with just 1 argument being tested, the cache hit rate is 100%. So this is not realistic.

C# program that times ToLower with memoization using System; using System.Collections.Generic; using System.Diagnostics; class Program { static string Lowercase1(string value) { return value.ToLower(); } static Dictionary<string, string> _lowercase = new Dictionary<string, string>(); static string Lowercase2(string value) { string lookup; if (_lowercase.TryGetValue(value, out lookup)) return lookup; lookup = value.ToLower(); _lowercase[value] = lookup; return lookup; } const int _max = 1000000; static void Main() { // Version 1: use ToLower. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { if (Lowercase1("TEST") != "test") { return; } } s1.Stop(); // Version 2: use ToLower with caching. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { if (Lowercase2("TEST") != "test") { return; } } s2.Stop(); Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); } } Output 99.54 ns Lowercase1 31.09 ns Lowercase2

Notes, arguments. We can memoize multiple argument methods. But when too many arguments are present, memoization is unlikely to help.

Tip: To memoize multiple arguments, you can concatenate a string key and then do a Dictionary lookup.

But: This would only optimize methods that are much slower than string concatenations.

Arrays. We do not need to use a Dictionary. For a method that only receives positive integers, you might be able to use an int[] (integer array) lookup table.Array, Dictionary Test Int Array

SICP. As stated in SICP, this can "transform processes that require an exponential number of steps into processes whose space and time requirements grow linearly with the input" (page 41).

Note: I have found memoization to be one of the more useful optimization techniques in programs.

Tip: Frequently, methods are called repeatedly with the same arguments. Sometimes, memoization can be achieved with just a static field.

A summary. This optimization can speed up certain methods. It is most effective on programs that repeatedly call a self-contained method with a small number of arguments.

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

C# Memoization

Related Links:

.Net

Java

Related Links