C＃用任意数量的参数记忆函数
我试图为任意数量的参数创build一个memoization接口，但我很失败，我觉得我的解决scheme不是很灵活。 我试图为一个函数定义一个接口，在执行时会自动记忆，每个函数都必须实现这个接口。 这里是一个双参数指数移动平均函数的例子：
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 } 这是我对这个函数的testing：
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)); }
更新：
感谢您指出我的n00bish错误…我总是忘记调用秒表重置！
我也看到了另一种memoization的方法 …它不提供n-argument memoization，但我的方法与接口没有太多的优势，因为我必须为每个函数编写一个类。 有没有一种合理的方法可以将这些想法合并成更强大的东西？ 我想简化一个函数而不用让用户为每个他们打算使用的函数写一个类。
这个怎么样？ 首先写一个单参数的记忆：
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; }; }
直截了当。 现在写一个函数tuplifier：
static Func<Tuple<A, B>, R> Tuplify<A, B, R>(this Func<A, B, R> f) { return t => f(t.Item1, t.Item2); }
和一个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)); }
现在有两个参数的记忆是很容易的：
static Func<A, B, R> Memoize<A, B, R>(this Func<A, B, R> f) { return f.Tuplify().Memoize().Detuplify(); }
要写一个三个参数的记忆器，只需要遵循这个模式：制作一个3-tuplifier，一个3-unuplifier和一个3-memoizer。
当然，如果你不需要它们，那么就没有必要制作一些名副其实的方法：
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)); }
更新：你问如果没有元组types，该怎么办。 你可以写自己的; 这并不难。 或者你可以使用匿名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(tA, tB), example); var memoized = tuplified.Memoize(); return (a, b) => memoized(new {A=a, B=b}); }
油滑，呃？
更新：C＃7现在具有内置的语言的值元组; 使用它们而不是滚动自己的或使用匿名types。
首先，你需要在你的testing之间调用sw.Reset() 。 否则，第二次testing的结果将是第一次testing的结果。
其次，你可能不应该在比较器的GetHashCode()覆盖中使用vals.GetHashCode() ，因为这将导致你得到不同的哈希代码，对于你的Equals重写会评估为true对象。 现在，我担心确保等价对象总是得到相同的散列码，而不是试图获得均匀分布的代码。 如果哈希代码不匹配， Equals永远不会被调用，所以最终会多次处理相同的参数。
StopWatch.Stop不会重置秒表，以便在每次启动/停止时积累时间。
例如
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);
给出以下结果
228221 454626
您可以使用StopWatch.Restart （Framework 4.0）每次重新启动秒表，或者如果不是Framework 4.0，则可以使用StopWatch.Reset重置秒表。
（元组和匿名types）方法可能如下：
static void Main(string[] args) { var func = Memoize<int, int, int>(Func); Console.WriteLine(func(3)(4)); Console.WriteLine(func(3)(5)); Console.WriteLine(func(2)(5)); Console.WriteLine(func(3)(4)); } //lets pretend this is very-expensive-to-compute function private static int Func(int i, int j) { return i + j; } private static Func<TArg1, Func<TArg2, TRes>> Memoize<TArg1, TArg2, TRes>(Func<TArg1, TArg2, TRes> func) { Func<TArg1, Func<TArg2, TRes>> func1 = Memoize((TArg1 arg1) => Memoize((TArg2 arg2) => func(arg1, arg2))); return func1; } private static Func<TArg, TRes> Memoize<TArg, TRes>(Func<TArg, TRes> func) { var cache = new Dictionary<TArg, TRes>(); return arg => { TRes res; if( !cache.TryGetValue(arg, out res) ) { Console.WriteLine("Calculating " + arg.ToString()); res = func(arg); cache.Add(arg, res); } else { Console.WriteLine("Getting from cache " + arg.ToString()); } return res; }; }
基于这两个Memoize funcs，您可以轻松地为您想要的任意数量的参数构build扩展。
我最初来到这里只是寻找一个无参数函数的抽象记忆方法。 这不是问题的答案，而是想分享我的解决scheme，以防其他人来寻找这个简单的案例。
public static class MemoizationExtensions { public static Func<R> Memoize<R>(this Func<R> f) { bool hasBeenCalled = false; // Used to determine if we called the function and the result was the same as default(R) R returnVal = default(R); return () => { // Should be faster than doing null checks and if we got a null the first time, // we really want to memoize that result and not inadvertently call the function again. if (!hasBeenCalled) { hasBeenCalled = true; returnVal = f(); } return returnVal; }; } }
如果您使用LinqPad ，则可以使用以下代码通过使用LinqPad的超酷转储方法轻松testingfunction。
new List<Func<object>>(new Func<object>[] { () => { "Entered func A1".Dump(); return 1; }, () => { "Entered func A2".Dump(); return default(int); }, () => { "Entered func B1".Dump(); return String.Empty; }, () => { "Entered func B2".Dump(); return default(string); }, () => { "Entered func C1".Dump(); return new {Name = String.Empty}; }, () => { "Entered func C2".Dump(); return null; }, }) .ForEach(f => { var f1 = MemoizationExtensions.Memoize(f); Enumerable .Range(1,3) .Select(i=>new {Run=i, Value=f1()}) .Dump(); });
PS您将需要在LinqPad脚本的代码中包含MemoizationExtensions类，否则将无法工作！
