使用元组实现快速记忆化

Question

我想使用记忆化来加速类似以下代码的执行（只有少量可能的参数值会被调用）：

double MyFun(double a,double b,int c,char d)
{
    double a = cpu_intensive_pure_function_1(a,c,d);
    double b = cpu_intensive_pure_function_2(b,c,d);
    return a+b;
}

一种可能性是将 args 封装到 Tuple 对象中，并使用 Dictionary（Dotnet 的新版本已为您完成元组的哈希）。

Dictionary<Tuple<double,double,int,char>,double> MyFunCache = new Dictionary<Tuple<double,double,int,char>,double> ();
double MyFun(double a,double b,int c,char d)
{
    var tmp = Tuple<double,double,int,char>(a,b,c,d);
    if(MyFunCache.ContainsKey(tmp))
    {
         return MyFunCache[tmp];
    }

    double a = cpu_intensive_pure_function_1(a,c,d);
    double b = cpu_intensive_pure_function_2(b,c,d);
    return a+b;
}

但这样需要每次调用函数时创建一个元组对象，似乎很浪费，有没有更好的方法？是否有某些已经保存参数的东西可以使用？

- Radost

---

@TripleAccretion 虽然“缓存”是一个通用的术语，但在这个问题中描述的纯函数的特殊情况通常被称为"记忆化"。此外，Tuple比较的实现应该已经自行处理了哈希冲突，所以这不应该是一个问题。 - janw

如果您使用 ValueTuple，那么您就不会遭受内存分配的影响。 - Sean

另外一件事情：对受影响的函数进行剖析，看是否存在某些操作对性能有明显影响。只有当影响较大时，才需要进行优化。 - janw

术语是“记忆化”，不是“记忆化”。 - Wyck

@JanWichelmann “CPU密集型函数”只被调用一次，但缓存会被检查数百万次。对于那些被频繁调用的东西进行小的改进仍然非常重要。 - Radost

Answer 1

您可以使用一个ValueTuple。此外，记得在获取计算值后更新缓存：

Dictionary<(double,double,int,char) ,double> MyFunCache = new Dictionary<(double,double,int,char) ,double> ();
double MyFun(double a,double b,int c,char d)
{
    var key = (a,b,c,d);
    if(MyFunCache.TryGetValue(key, out var cachedResult))
    {
         return cachedResult;
    }

    double a = cpu_intensive_pure_function_1(a,c,d);
    double b = cpu_intensive_pure_function_2(b,c,d);

    MyFunCache.Add(key, a+ b);
    return a+b;
}

- Sean