Home
C#
Memoization
This page was last reviewed on Apr 4, 2023.
Dot Net Perls
Memoization. This is way to optimize repeated method calls in C#. 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.
An example. This code example shows us how to implement memoization with a Dictionary. We try to avoid recomputing lowercased strings with a cache.
Start Lowercase1 is much simpler. It calls ToLower on the string argument each time and returns it.
String ToLower, ToUpper
Next Lowercase 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
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; } }
test test test
Benchmark. To check the performance advantage, I created a benchmark. I 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.
Result It is faster to cache. But with just 1 argument being tested, the cache hit rate is 100%. So this is not realistic.
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")); } }
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 array lookup table.
int Array
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.
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.
This page was last updated on Apr 4, 2023 (edit).
Home
Changes
© 2007-2024 Sam Allen.