38

我正在尝试为具有任意数量参数的函数创建一个记忆接口，但我失败了，我觉得我的解决方案不是很灵活。我试图为一个函数定义一个接口，该接口在执行时会自动记忆，每个函数都必须实现这个接口。这是一个带有两个参数的指数移动平均函数的示例：

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
}

这是我对该功能的测试：

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 错误...我总是忘记在秒表上调用 Reset！

我也看到了另一种记忆方法......它不提供 n 参数记忆，但我使用接口的方法并没有多大优势，因为我必须为每个函数编写一个类。有没有一种合理的方法可以将这些想法合并成更强大的东西？我想让记住一个函数更容易，而不是让用户为他们打算使用的每个函数编写一个类。

4

5 回答 5

87

这个怎么样？首先编写一个单参数记忆器：

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;
    };
}

直截了当。现在写一个函数元组：

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

和一个去重器：

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();
}

要编写一个三参数 memoizer，只需遵循以下模式：制作一个 3-tuplifier、一个 3-untuplifier 和一个 3-memoizer。

当然，如果您不需要它们，则无需将 tuplifiers 命名为方法：

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));
}

更新：如果没有元组类型，您会问该怎么办。你可以自己写；这并不难。或者您可以使用匿名类型：

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});
}

光滑，嗯？

更新：C# 7 现在在语言中内置了值元组；使用它们而不是滚动你自己的或使用匿名类型。

于 2010-05-17T20:37:38.080 回答
3

首先，您需要sw.Reset()在测试之间调用。否则，您第二次测试的结果将与第一次测试的时间相加。

其次，您可能不应该在比较器上的覆盖中使用vals.GetHashCode()，因为这将导致您为将评估为覆盖GetHashCode()的对象获取不同的哈希码。现在，我会担心确保等效对象始终获得相同的哈希码，而不是试图获得代码的均匀分布。如果哈希码不匹配，将永远不会被调用，因此您最终将多次处理相同的参数。trueEqualsEquals

于 2010-05-17T19:42:14.980 回答
3

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重置秒表。

于 2010-05-17T19:39:44.313 回答
2

替代（元组和匿名类型）方法可能如下：

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 函数，您可以轻松地为任意数量的 args 构建扩展。

于 2012-03-15T07:53:08.450 回答
1

我最初来这里只是为了寻找一种无参数函数的抽象记忆方法。这不完全是问题的答案，但想分享我的解决方案，以防其他人来寻找简单的案例。

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 的超酷Dump方法轻松测试功能。

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 类，否则它将无法工作！

于 2013-01-16T15:28:01.747 回答