Function memoization in C#

in #programming7 years ago

Function memoization is a means to cache function calls that take a long time. It means you only have to perform the operation once for a given set of arguments, the next time you call with the same arguments you just reuse the results from the previous call.

The implementation is actually simple enough, for any given function we build a new function with the same signature that wraps it and provides the required caching.

The following static object can be used to wrap 1, 2 or 3 argument function in this way. Each version is the same basic idea, create a closure to hold the results cache and then when called look in the cache for the result and use it if found otherwise call the function then cache the result.

public static class Memoize
{
    public static Func<T, TResult> 
        Wrap<T, TResult>(Func<T, TResult> operation)
    {
        var cache = new Dictionary<T, TResult>();
        return
            param =>
            {
                TResult result;
                if (!cache.TryGetValue(param, out result))
                {
                    result = operation(param);
                    cache.Add(param, result);
                }
                return result;
            };
    }

    public static Func<T1, T2, TResult> 
        Wrap<T1, T2, TResult>(Func<T1, T2, TResult> operation)
    {
        var cache = new Dictionary<string, TResult>();
        return
            (param1, param2) =>
            {
                var key = $"{param1}.{param2}";

                TResult result;
                if (!cache.TryGetValue(key, out result))
                {
                    result = operation(param1, param2);
                    cache.Add(key, result);
                }
                return result;
            };
    }

    public static Func<T1, T2, T3, TResult> 
        Wrap<T1, T2, T3, TResult>(Func<T1, T2, T3, TResult> operation)
    {
        var cache = new Dictionary<string, TResult>();
        return
            (param1, param2, param3) =>
            {
                var key = $"{param1}.{param2}.{param3}";

                TResult result;
                if (!cache.TryGetValue(key, out result))
                {
                    result = operation(param1, param2, param3);
                    cache.Add(key, result);
                }
                return result;
            };
    }
}

There are a few gotcha with this technique:

  • The function must always produce the same results given the same arguments. So a pure function.
  • The arguments must be value types or immutable such as string.
  • If an argument is a class it should be immutable and have a meaningful "ToString()" override to uniquely identify the class.

The reason for the pure, "ToString()" and immutable requirements is that we need to ensure that the arguments are a true match for previous cache entries.

Feel free to ask any questions

Happy coding

Woz

Sort:  

to sum up in simple words memorization is used to improve the performance our code and the basic idea is to cache(store) the value and then return back.

Exactly, wish I had used similar wording :)

You're so nice for commenting on this post. For that, I gave you a vote!