# Wednesday, 16 December 2009
The canonical Fibonacci series algorithm can now be represented in C# as simply:

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

If this algorithm were running on a local client application, the results would appear almost instanty.

However, in cloud computing, the slightest inefficiency in an algorithm becomes magnified once high concurrency is introduced. In this case, the fib(int) function will be repeatedly called with the same input value as it recurses through the series.

Memoization supports the retention of previously calculated values in a "memo", so that if fib(5) has already been calculated, it's cached value is returned instead of re-calculated.

C# supports closure through method extensions that allow us to wrap the fib() function in a container with a Dictionary memo.

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
  var map = new Dictionary<A, R>();
  return a =>
    {
      R value;
      if (map.TryGetValue(a, out value))
        return value;
      value = f(a);
      map.Add(a, value);
      return value;
    };
}


The fib function is then bound to the memo wrapper through a call to the method extension.
Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
fib = fib.Memoize();

Please don't misconstrue this as a need to optimize for performance early in the development lifecycle. As always, agile development should optimize for performance later.

This memoization just demonstrates the elegant decoupling of functions using some new C# tricks historically only available to functional programming languages.


Wednesday, 16 December 2009 11:35:57 (Pacific Standard Time, UTC-08:00)
Comments are closed.