Memoization using generics and lambda expressions

This is Part 1 of my series of memoization, you can find Part 2 here.
Memoization is a hidden treasure of programming techniques. Most developers has a good understanding of caching and use it to optimize queries, but why even do calculations on cached or live data, when you don’t need to calculate at all?

The defenition
To quote Wikipedia:

A memoized function "remembers" the results corresponding to some set of specific inputs. Subsequent calls with remembered inputs return the remembered result rather than recalculating it, thus moving the primary cost of a call with given parameters to the first call made to the function with those parameters.

The idea is simple, and under the right circumstances it can reduce the calculation time from “infinite” to (almost) zero.

Parameter less memoization
The simplest use of memoization, which also gives a good example of how this work, is to memoize a simple parameter less function. The example memoize the call of function f, which returns a generic value of type S:

1:  public static Func<S> Memoize<S>(Func<S> f)

2:  {

3:      var value = default(S);

4:      var hasValue = false;

5:      return () =>

6:          {

7:              if (!hasValue)

8:              {

9:                  value = f();

10:                  hasValue = true;

11:              }

12:              return value;

13:          };

14:  }

Regardsless of how many calls, the function f will only be called once, and all consecutive calls will only return the already calculated value. The function is defined in the following line:

1:  public Func<int> myFunc = Memoize<int>(DoSomeWork);

Where DoSomeWork has the same signature as the Memoize method, and we call myFunc instead of calling DoSomeWork directly.

Memoizing functions with parameters
The next step is of course to look at functions which takes one parameter. Now instead of simply using a bool for hasValue, we now introduce a generic Dictionary to handle the calculated values:

1:  public static Func<S,T> Memoize<S,T>(Func<S,T> f)

2:  {

3:      var map = new Dictionary<S,T>();

4:      return (a) =>

5:          {

6:              T calculatedValue;

7:              if (!map.TryGetValue(a, out calculatedValue))

8:              {

9:                  calculatedValue = f(a);

10:                  map.Add(a,calculatedValue);

11:              }

12:              return calculatedValue;            

13:          };

14:  }

The parameter introduce a little more complexity, but still it is easy and effective to introduce this in your code! In a later post, I will also show how to use memoization with more parameters.

Be aware!
Memoization is a very powerful tool when used in the right situation, but remember, the memoized values will be kept for later calculations! So, if your underlying data changes, you will have to null the memoized map to get new and correct calculations.

This was Part 1 of my series of memoization, you can find Part 2 here.