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

Question

I'm trying to create a memoization interface for functions with arbitrary number of arguments, but I'm failing miserably I feel like my solution is not very flexible. I tried to define an interface for a function which gets memoized automatically upon execution and each function will have to implement this interface. Here is an example with a two parameter Exponential Moving Average function:

class EMAFunction:IFunction {     Dictionary<List<object>, List<object>> map;      class EMAComparer : IEqualityComparer<List<object>>     {         private int _multiplier = 97;          public bool Equals(List<object> a, List<object> b)         {             List<object> aVals = (List<object>)a[0];             int aPeriod = (int)a[1];              List<object> bVals = (List<object>)b[0];             int bPeriod = (int)b[1];              return (aVals.Count == bVals.Count) && (aPeriod == bPeriod);         }          public int GetHashCode(List<object> obj)         {             // Don't compute hash code on null object.             if (obj == null)             {                 return 0;             }              List<object> vals = (List<object>) obj[0];             int period = (int) obj[1];              return (_multiplier * period.GetHashCode()) + vals.Count;          }     }      public EMAFunction()     {         NumParams = 2;         Name = "EMA";         map = new Dictionary<List<object>, List<object>>(new EMAComparer());     }     #region IFunction Members      public int NumParams     {         get;         set;     }      public string Name     {         get;         set;     }      public object Execute(List<object> parameters)     {         if (parameters.Count != NumParams)             throw new ArgumentException("The num params doesn't match!");          if (!map.ContainsKey(parameters))         {             //map.Add(parameters,             List<double> values = new List<double>();             List<object> asObj = (List<object>)parameters[0];             foreach (object val in asObj)             {                 values.Add((double)val);             }             int period = (int)parameters[1];              asObj.Clear();             List<double> ema = TechFunctions.ExponentialMovingAverage(values, period);             foreach (double val in ema)             {                 asObj.Add(val);             }             map.Add(parameters, asObj);         }         return map[parameters];     }      public void ClearMap()     {         map.Clear();     }      #endregion } 

Here are my tests of the function:

private void MemoizeTest() {     DataSet dataSet = DataLoader.LoadData(DataLoader.DataSource.FROM_WEB, 1024);     List<String> labels = dataSet.DataLabels;      Stopwatch sw = new Stopwatch();     IFunction emaFunc = new EMAFunction();     List<object> parameters = new List<object>();     int numRuns = 1000;     long sumTicks = 0;     parameters.Add(dataSet.GetValues("open"));     parameters.Add(12);      // First call      for(int i = 0; i < numRuns; ++i)     {         emaFunc.ClearMap();// remove any memoization mappings         sw.Start();         emaFunc.Execute(parameters);         sw.Stop();         sumTicks += sw.ElapsedTicks;         sw.Reset();     }     Console.WriteLine("Average ticks not-memoized " + (sumTicks/numRuns));       sumTicks = 0;     // Repeat call     for (int i = 0; i < numRuns; ++i)     {         sw.Start();         emaFunc.Execute(parameters);         sw.Stop();         sumTicks += sw.ElapsedTicks;         sw.Reset();     }     Console.WriteLine("Average ticks memoized " + (sumTicks/numRuns)); } 

Update:
Thanks for pointing out my n00bish error... I always forget to call Reset on the stopwatch!

I've seen another approach to memoization as well... it doesn't offer n-argument memoization, but my approach with the Interface is not much more advantageous since I have to write a class for each function. Is there a reasonable way that I can merge these ideas into something more robust? I want to make it easier to memoize a function without making the user write a class for each function that they intend to use.

Answer 1

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.