C# Memoization of functions with arbitrary number of arguments
- by Lirik
I'm trying to create a memoization interface for functions with arbitrary number of arguments, but I'm failing miserably. The first thing I tried is to define an interface for a function which gets memoized automatically upon execution:
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;
}
// Get length.
int length = obj.Count;
List<object> vals = (List<object>) obj[0];
int period = (int) obj[1];
return (_multiplier * vals.GetHashCode() * period.GetHashCode()) + length;;
}
}
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;
}
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;
}
Console.WriteLine("Average ticks memoized " + (sumTicks/numRuns));
}
The performance is confusing me... I expected the memoized function to be faster, but it didn't work out that way:
Average ticks not-memoized 106,182
Average ticks memoized 198,854
I tried doubling the data instances to 2048, but the results were about the same:
Average ticks not-memoized 232,579
Average ticks memoized 446,280
I did notice that it was correctly finding the parameters in the map and it going directly to the map, but the performance was still slow... I'm either open for troubleshooting help with this example, or if you have a better solution to the problem then please let me know what it is.
