ISerialized .Net, C#, Scrum and agile software development

Memoization using generics – Part 2

This is Part 2 of my series on Memoization. In Part 1 I described the basic principles behind memoization, and showed some examples on how to create an effective generic method to do memoization of methods with zero and one parameter. In this post I will show how to do memoization of methods with two parameters

Why is there a difference between one and two parameters when doing memoization? Well, we store our memoized values in Dictionary, with the parameter as the key, and calculated result of the method as the value. So far so good, but when we suddenly have to parameters in our method signature, and hence two keys in combination defining the result.

We can handle this, either through a struct or a class. In this example, I will use a struct. To get started we make a struct called KeyPair to store two generic values.

private struct KeyPair
{
    public P1 key1;
    public P2 key2;

    public KeyPair(P1 param1, P2 param2)
    {
        key1 = param1;
        key2 = param2;
    }

    public override bool Equals(object obj)
    {
        if (obj.GetType().Equals(typeof(KeyPair)))
        {
            var compareTo = (KeyPair)obj;
            if (compareTo.key1.Equals(key1) && compareTo.key2.Equals(key2))
                return true;
        }
        return false;
    }

    public override int GetHashCode()
    {
        return key1.GetHashCode() ^ key2.GetHashCode();
    }
}

For this example, I have just created a very simple GetHasCode method, and realize that it might not produce  unique values in all situations with the bitwise exclusive OR (Binary Xor) of the two hash codes.

Now we have a full struct to store our keys, and we can now update the memoization method shown in Part 1 to handle two parameters:

public static Func<P1,P2,T> Memoize(Func<P1, P2, T> f)
{
    var map = new Dictionary<KeyPair, T>();
    return (a1, a2) =>
    {
        T calculatedValue;
        var key = new KeyPair(a1, a2);
        if (map.TryGetValue(key, out calculatedValue))
        {
            return calculatedValue;
        }
        calculatedValue = f(a1, a2);
        map.Add(key,calculatedValue);
        return calculatedValue;
    };
}

It's not that different from the former version, apart from the fact that we now have two parameters in our lamda, and that we now introduce a key of type KeyPair. We can then easily use the memoizer in the following way:

private readonly Func<int,int,string> MyFunc = Memoizer<string,int,int>.Memoize(test2);

public void Calculate()
{
    //a lot bla bla bla
    foreach (var row in alotofrows)
    {
        row["result"] = MyFunc(row["a"], row["b"]);
    }
}

public static string test2(int a, int b)
{
    //Calculate something a return a string
    return result;
}

Here you can see that we actually can the Function instead of the method test2 directly, letting the Memoizer decide whether to call the actual method or not.