Significantly speeding up computations with smart predicates

There is a technique that allows optimization of repeated calculation results for a set of inputs called memoization. This technique is particularly helpful when working with numeric computations, pathing, such as for tree searches, etc. where the time taken to traverse the result set is expediential. What's more interesting is that the technique is applied on top of the System.Func object allowing for transparent optimization of those delegate types. Here is the method that I use to perform the optimization.

 public static class SystemMemoizationExtension 
{ 
    private static object lockObject = new object(); /// <summary>
        /// Wraps the original delegate passed via <paramref name="func"/> with a closure that
        /// includes a Dictionary&lt;&gt; instance to store the cached values for the given
        /// delegate <paramref name="func"/>. This serves as a cache that greatly improves
        /// efficiency.
        /// </summary>
        /// <typeparam name="T">The type of the parameter of the method that this delegate encapsulates.</typeparam>
        /// <typeparam name="TResult">The type of the return value of the method that this delegate encapsulates.</typeparam>
        /// <param name="func">The parameter of the method that this delegate encapsulates.</param>
        /// <returns>The return value of the method that this delegate encapsulates.</returns>
        /// <remarks>
        /// Additional information about Memoization available at
        /// https://en.wikipedia.org/wiki/Memoization
        /// </remarks>
        public static Func<T, TResult> Memoize<T, TResult>( this Func<T, TResult> func )
        {
            lock( lockObject )
            {
                var cache = new Dictionary<T, TResult>();
                return ( x ) =>
                {
                    TResult result = default( TResult );
                    if( cache.TryGetValue( x, out result ) )
                    {
                        return result;
                    }                    result = func( x );
                    cache[ x ] = result;
                    return result;
                };
            }
        }
    } 
} 

To utilize the method simply assign the result of the Memoize method back to your delegate as shown in the example below.

 Func<int, int> Fibonacci = null; 
//Recursive Fibonacci algorithm
Fibonacci = n >=n <= 1 ? n : Fibonacci(n – 1) + Fibonacci(n-2); 
//Optimize lookups
Fibonacci = Fibonacci.Memoize(); 

While this is an overly simplistic example of recursion optimization you can see that by calling the code once then again using the same input that a dramatic improvement is made performing the computation (an input for F(n) where n = 42 takes several seconds to compute, while the subsequent call takes sub seconds). The technique itself is useful for reducing the traversal time for any top-down parsing.

Technorati Tags: C#

Comments

• Anonymous
  October 15, 2008
  More of an acute fascination than anything else I expanded my use of memoization for computation to use

• Anonymous
  December 21, 2008
  I gotta admit I never heard about memoization before..but have already used it/tested it in a few situations I run into...and well the time reduction is awesome..simply awesome...thx for sharing the knowledge :) Erik cox http://www.notionsolutions.com

• Anonymous
  January 05, 2009
  You've been kicked (a good thing) - Trackback from DotNetKicks.com