C# Memoization of functions with arbitrary number of arguments [closed]

How about this? First write a one-argument memoizer:

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

Straightforward. Now write a function tuplifier:

static Func<Tuple<A, B>, R> Tuplify<A, B, R>(this Func<A, B, R> f)
{
    return t => f(t.Item1, t.Item2);
}

And a detuplifier:

static Func<A, B, R> Detuplify<A, B, R>(this Func<Tuple<A, B>, R> f)
{
    return (a, b) => f(Tuple.Create(a, b));
}

and now a two-argument memoizer is easy:

static Func<A, B, R> Memoize<A, B, R>(this Func<A, B, R> f)
{
    return f.Tuplify().Memoize().Detuplify();
}

To write a three-argument memoizer just keep following this pattern: make a 3-tuplifier, a 3-untuplifier, and a 3-memoizer.

Of course, if you don't need them, there's no need to make the tuplifiers nominal methods:

static Func<A, B, R> Memoize<A, B, R>(this Func<A, B, R> f)
{
    Func<Tuple<A, B>, R> tuplified = t => f(t.Item1, t.Item2);
    Func<Tuple<A, B>, R> memoized = tuplified.Memoize();
    return (a, b) => memoized(Tuple.Create(a, b));
}

UPDATE: You ask what to do if there is no tuple type. You could write your own; it's not hard. Or you could use anonymous types:

static Func<T, R> CastByExample<T, R>(Func<T, R> f, T t) { return f; }

static Func<A, B, R> Memoize<A, B, R>(this Func<A, B, R> f)
{
    var example = new { A=default(A), B=default(B) };
    var tuplified = CastByExample(t => f(t.A, t.B), example);
    var memoized = tuplified.Memoize();
    return (a, b) => memoized(new {A=a, B=b});
}

Slick, eh?

UPDATE: C# 7 now has value tuples built in to the language; use them rather than rolling your own or using anonymous types.

First, you need to call sw.Reset() between your tests. Otherwise your results for the second test will be in addition to the time from the first.

Second, you probably shouldn't use vals.GetHashCode() in your GetHashCode() override on the comparer, as this will lead you to getting different hash codes for objects that would evaluate to true for your Equals override. For now, I would worry about making sure that equivalent objects always get the same hash code rather than trying to get an even distribution of the codes. If the hash codes don't match, Equals will never be called, so you'll end up processing the same parameters multiple times.

StopWatch.Stop does not reset the stopwatch so you are accumulating time on each start/stop.

For example

  Stopwatch sw = new Stopwatch();

  sw.Start();
  System.Threading.Thread.Sleep(100);
  sw.Stop();
  Debug.WriteLine(sw.ElapsedTicks);

  sw.Start();
  System.Threading.Thread.Sleep(100);
  sw.Stop();
  Debug.WriteLine(sw.ElapsedTicks);

Gives the following results

228221
454626

You can use StopWatch.Restart (Framework 4.0) to restart the stopwatch each time, or if not Framework 4.0, you can use StopWatch.Reset to reset the stopwatch.

C# Memoization of functions with arbitrary number of arguments [closed]

Related

Recent Posts