Memoization explained part 4: multiple parameters


13 April 2012, by

Last time we saw the implementation of simple memoizers and I promised that this time, we’d take a look into the more advanced overloads – the ones with more than one parameter type.

Hopefully we won’t need to write too much more code, since these overloads are doing largely the same thing as the single-parameter version. However it does require a bit of thought. Two types can’t be used as a single key to a dictionary, so unless we want to use the dreaded dictionary-over-dictionary approach, we’ll need to make the key to our dictionary a tuple.

A tuple is a magical device that can hold a fixed number of strongly-typed values. For example, a Tuple<string, int> would store – you guessed it – a string and an integer. Tuples work even better with language support, which is available in a surprising number of languages.

So when a method is called with 2 parameters, we create a 2-tuple to hold its two parameters. When a method is called with 3 parameters, we use a 3-tuple; and so on, ad nauseam – which for me, was at four.

So without further ado…

public static Func<T1, T2, TResult>
  GetMemoizer<T1, T2, TResult>(Func<T1, T2, TResult> func) {
  // Check that the parameter is not null.
  NullCheck("func", func);
  // Make a version of the function that accepts a single tuple parameter
  // instead of two parameters.
  Func<Tuple<T1, T2>, TResult> tupled = tuple => {
    return func(tuple.Item1, tuple.Item2);
  };

  // Memoize this 'tupled' version of the function.
  tupled = GetMemoizer(tupled);

  // And make a version of the memoized function that is 'untupled' -
  // that accepts the original two parameters, and not a tuple.
  return (t1, t2) => tupled(new Tuple<T1, T2>(t1, t2));
}

As you can see, this method is just three lines – wrap the values in a tuple, memoize the function that deals with tuples, unwrap the values. But actually, since these are functions we’re wrapping and unwrapping, the values will flow the other way around – at first the bottom method will be called with the original t1, t2 parameters; then, the middle line gets called with the tuple parameter, and finally, if this is the first time these parameters are encountered (or if they threw an exception last time), the values are unwrapped in the first line and the original function is called.

The three- and four-parameter versions are strikingly similar, with only the number of ‘T’s changed – both when wrapping and when unwrapping:

public static Func<T1, T2, T3, TResult>
  GetMemoizer<T1, T2, T3, TResult>(Func<T1, T2, T3, TResult> func) {
	NullCheck("func", func);

	Func<Tuple<T1, T2, T3>, TResult> tupled = tuple => {
		return func(tuple.Item1, tuple.Item2, tuple.Item3);
	};

	tupled = GetMemoizer(tupled);

	return (t1, t2, t3) => tupled(new Tuple<T1, T2, T3>(t1, t2, t3));
}

public static Func<T1, T2, T3, T4, TResult>
  GetMemoizer<T1, T2, T3, T4, TResult>(Func<T1, T2, T3, T4, TResult> func) {
	NullCheck("func", func);

	Func<Tuple<T1, T2, T3, T4>, TResult> tupled = tuple => {
		return func(tuple.Item1, tuple.Item2, tuple.Item3, tuple.Item4);
	};

	tupled = GetMemoizer(tupled);

	return (t1, t2, t3, t4) => tupled(new Tuple<T1, T2, T3, T4>(t1, t2, t3, t4));
}

And this concludes our implementation of memoizers. See? It wasn’t that hard. And most importantly, if any problems are found, they are likely to be fixed in all four versions simultaneously.

Tags: , ,

Categories: Technical

«
»

Leave a Reply

* Mandatory fields


− one = 3

Submit Comment