For years, we software developers fell into the beautiful deception of Moore’s Law – that temptingly wonderful promise that transistor counts would double every 18 months and that our software would run faster and faster with no work on our part. And as many developers have noticed, CPU speeds are not growing in leaps and bounds anymore. (A fabulous article on this topic is Herb Sutter’s The Free Lunch is Over). Considering the changes in the hardware climate, I think it is about time we give a fresh look at pattern/technique that often been a second-class citizen: Memoization.
Simply put, memoization is the storing of a function’s results to be reused at a later time instead of recomputing the function. By utilizing a caching mechanism, such as a hash table lookup, function results can be rapidly stored and accessed. Because this assumes memoized functions will always return the same value, functions using this technique must be referentially transparent (i.e., given the exact same input, they will always yield the exact same output).
However, there may be a few occasions when intentionally relaxing this restriction is acceptable. For instance, consider a web search utility. Though the internet is continually gaining new entries of keywords every second, it isn’t desirous to search the entire internet (or even an entire database of web pages) every time we search. Instead, we may decide it is acceptable to only re-perform the entire search on a given keyword once every week. In this case, we can use a modified memoization technique.
Here’s a memoization implementation that leverages C# generics and delegates:
public delegate T Function<T>(T x);
class MemoizationPattern
{
public static Function<T> Memoize<T>(Function<T> func)
Dictionary<T, T> dictionary = new Dictionary<T,T>();
return delegate(T x)
T retVal = default(T);
if (dictionary.TryGetValue(x, out retVal))
return retVal;
}
else
T newVal = func(x);
dictionary[x] = newVal;
return newVal;
};
To see this in action, utilize the class in the following manner:
class Program
static int ReallySlowFunction(int x)
System.Threading.Thread.Sleep(1000);
return x;
static void Main(string[] args)
Random rand = new Random();
Function<int> FastFunction =
MemoizationPattern.Memoize<int>(ReallySlowFunction);
Console.WriteLine("ReallySlowFunction Output: ");
for (int i = 0; i < 10; i++)
Console.WriteLine(ReallySlowFunction(rand.Next(3)));
Console.WriteLine("FastFunction Output: ");
for(int i = 0; i < 10; i++)
Console.WriteLine(FastFunction(rand.Next(3)));
This example uses the Memoization technique to boost the ReallySlowFunction from a one second wait to an instant return. Run this and you’ll notice the time of the loop drops from 10 seconds to 3. You can easily extend the Memoize function to have separate types for the parameters and return value. Put this technique to work wherever you have functions that are heavily used and referentially transparent, and you’ll see a marked performance boost.