Memoize

The first time I saw this word I thought someone had mispelled it. Instead - as I later found out - it's the name for a common pattern in functional programming. Memoize caches the result of a function based on its input parameters. That may not sound particularly special, but in cases where a solution is recursive and frequently calls itself with the same parameters, memoize can turn an algorithm that takes billions of years to run[1], into one that takes a fraction of a second.

Consider this problem outlined on ROT13(Cebwrpg Rhyre). Every node in the triangle has an associated maximum cost. For the elements at the base level of the triangle, that value is the value of the element. For the element at the next highest level, the maximum cost is the value of the element itself, plus the greater value of the two elements below it. This property holds recursively throughout the entire graph, and we can use the memoize pattern to our advantage: instead of working out the cost of each element every time our algorithm requires it, we simply fetch it from the cache (if it doesn't exist, we add it to the cache, and use it on all subsequent calls.)

The original brute force C# code looked like this:
static int MaxCost(Triangle triangle, int x, int y)
{
if (y == triangle.Depth)
{
return 0;
}
else
{
int left = MaxCost(triangle, x, y + 1);
int right = MaxCost(triangle, x + 1, y + 1);
return Math.Max(left, right) + triangle[x, y];
}
}
We need to rewrite the method body slightly because it's self-recursive, and we can't take advantage of the memoize cache if our function just calls back into itself directly.

If we're pressed for time, we might simply code the cache into the method body:
static int MaxCost(Triangle triangle, int x, int y)
{
var key = new Tuple<Triangle,int,int>(triangle, x, y);
if (cache.ContainsKey(key))
{
return cache[key];
}

if (y == triangle.Depth)
{
return 0;
}
else
{
int left = MaxCost(triangle, x, y + 1);
int right = MaxCost(triangle, x + 1, y + 1);
int result = Math.Max(left, right) + triangle[x, y];
cache.Add(key, result);
return result;
}
}
With more time on our hands, we might separate the function into two distinct logic functions, one that deals with memoization, and the other that deals with the problem at hand:
static int MemoizedMaxCost(Triangle triangle, int y, int x)
{
var key = new Tuple<Triangle, int, int>(triangle, x, y);
if (cache.ContainsKey(key))
{
cache[key];
}
int result = InternalMaxCost(triangle, y, x);
cache.Add(key, result);
return result;
}

static int InternalMaxCost(Triangle triangle, int x, int y)
{
if (y == triangle.Depth)
{
return 0;
}
else
{
int left = MemoizedMaxCost(triangle, x, y + 1);
int right = MemoizedMaxCost(triangle, x + 1, y + 1);
return Math.Max(left, right) + triangle[x, y];
}
}
Note that we now have a pair of mutually recursive functions: the memoized function calls the internal one to evaluate any uncached values, and the internal one calls the memoized one to gain any of the performance benefits from memoizing. A match made in heaven?