C # Воспоминание функций с произвольным числом аргументов

Я пытаюсь создать интерфейс memoization для функций с произвольным количеством аргументов, но я терплю неудачу. Я чувствую, что мое решение не очень гибкое. Я попытался определить интерфейс для функции, которая автоматически запоминается после выполнения, и каждая функция должна будет реализовать этот интерфейс. Вот пример с двумя параметрами: функция экспоненциального скользящего среднего:

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

Вот мои тесты функции:

 private void MemoizeTest() { DataSet dataSet = DataLoader.LoadData(DataLoader.DataSource.FROM_WEB, 1024); List labels = dataSet.DataLabels; Stopwatch sw = new Stopwatch(); IFunction emaFunc = new EMAFunction(); List parameters = new List(); 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 … Я всегда забываю вызвать Reset на секундомере!

Я также видел другой подход к memoization … он не предлагает n-аргумент memoization, но мой подход с интерфейсом не намного более выгоден, так как я должен написать class для каждой функции. Есть ли разумный способ объединить эти идеи в нечто более надежное? Я хочу, чтобы было легче запоминать функцию, не заставляя пользователя писать class для каждой функции, которую они намереваются использовать.

Как насчет этого? Сначала напишите memoizer с одним аргументом:

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

Непосредственная. Теперь напишите функцию tuplifier:

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

И разделитель:

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

и теперь memoizer с двумя аргументами легко:

 static Func Memoize(this Func f) { return f.Tuplify().Memoize().Detuplify(); } 

Чтобы написать трехфакторный memoizer, просто следуйте этому шаблону: создайте 3-tullifier, 3-untuplifier и 3-memoizer.

Разумеется, если вы им не нужны, нет необходимости использовать номинальные методы tuplifiers:

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

UPDATE: вы спрашиваете, что делать, если нет типа кортежа. Вы можете написать свой собственный; это не трудно. Или вы можете использовать анонимные типы:

 static Func CastByExample(Func f, T t) { return f; } static Func Memoize(this Func 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 имеет кортежи значений, встроенные в язык; используйте их, а не сворачивайте свои собственные или используя анонимные типы.

Во-первых, вам нужно вызвать sw.Reset() между вашими тестами. В противном случае ваши результаты для второго теста будут в дополнение к времени от первого.

Во-вторых, вы, вероятно, не должны использовать vals.GetHashCode() в вашем vals.GetHashCode() GetHashCode() на компараторе, так как это приведет к получению разных хеш-кодов для объектов, которые будут оцениваться как true для вашего Equals override. На данный момент я буду беспокоиться о том, чтобы эквивалентные объекты всегда получали один и тот же хеш-код, а не пытались получить равномерное распределение кодов. Если hash-коды не совпадают, 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 для сброса секундомера.

Альтернативный (для кортежей и анонимных типов) подход может быть следующим:

 static void Main(string[] args) { var func = Memoize(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> Memoize(Func func) { Func> func1 = Memoize((TArg1 arg1) => Memoize((TArg2 arg2) => func(arg1, arg2))); return func1; } private static Func Memoize(Func func) { var cache = new Dictionary(); 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, вы можете легко создавать расширения для столько аргументов, сколько пожелаете.

Сначала я пришел сюда только для поиска абстрактного метода memoization для функции без параметров. Это не совсем ответ на вопрос, но я хотел поделиться своим решением в случае, если кто-то другой ищет простой случай.

 public static class MemoizationExtensions { public static Func Memoize(this Func 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, вы можете использовать следующий код, чтобы легко проверить функциональность с помощью метода Super Cool Dump LinqPad.

 new List>(new Func[] { () => { "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 Вам нужно будет включить class MemoizationExtensions в код скрипта LinqPad, иначе он не сработает!