c# - C# / C++ 中的缓存或预先计算的不可变函数

Question

通过“不可变函数”或“不可变方法”，我的意思是一个函数，如果你给它相同的参数，它的结果永远不会改变。

当您想缓存不可变函数的预计算值时，我很想知道是否有人知道更通用或更简洁的解决方案。

让我用一个简单的例子来解释我的意思：

//Let's assume that ComputeStuff() returns a widely used value 
//and that 
//1. It is immutable (it will always return the same result)
//2. its performance is critical, and it cannot be accepted to compute
//   the result at each call, because the computation is too slow
//I show here a way to solve the problem, based on a cached result.
//(this example works in a case of a method with no arguments. 
// A hash would be required in order to store multiple precomputed results 
//depending upon the arguments)
private string mComputeStuff_Cached = null;
public string ComputeStuff()
{
  if (mComputeStuff_Cached != null)
    return mComputeStuff_Cached ;

  string result;
  //
  // ...
  //Do lots of cpu intensive computation in order to compute "result" 
  //or whatever you want to compute
  //(for example the hash of a long file)
  //...
  //

  mComputeStuff_Cached  = result;
  return mComputeStuff_Cached ;
}

注意：
- 我添加了标签 C++ 作为 C++ 中的解决方案，我也会感兴趣
- “不可变函数”的概念对于数据库开发人员来说很常见，因为函数可以定义为“不可变”或“在事务中不可变”（这是提高查询性能的好方法）。

提前致谢

Answer 1

“记忆化”在这里可能是一个有用的术语。那里有一些记忆库（我可以发誓在boost中有一个，但我现在找不到它）。对“memoize”或“memoization”进行网络搜索，您选择的语言会显示一些命中。

这是 Wikibooks 中的一篇简洁文章：优化 C++/通用优化技术/记忆化

Answer 2

你可以尝试这样的事情：

#include <functional>
#include <type_traits>
#include <map>
#include <tuple>

//requires c++14
auto add_function_cache = [](auto fun) {
    using fun_type = decltype(fun);
    return ([=](auto... run_args){
        using fun_return_type = std::result_of_t<fun_type(decltype(run_args)...)>;
        static std::map<
            std::tuple<decltype(run_args)...>,
            fun_return_type
        > result_cache;
        std::tuple<decltype(run_args)...> tuple(run_args...);
        if (result_cache.find(tuple) == result_cache.end()) {
            fun_return_type rv = fun(run_args...);
            result_cache[tuple] = rv; 
            return rv; 
        }   
        else {
            return result_cache[tuple];
        }   
    }); 
};

template <typename R, class... Args> auto
add_function_cache_old(std::function<R(Args...)> fun)
-> std::function<R(Args...)>
{
    std::map<std::tuple<Args...>, R> cache;
    return [=](Args... args) mutable  {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end()) {
            R rv = fun(args...);
            cache[t] = rv; 
            return rv; 
        }   
        else {
            return cache[t];
        }   
    };  
};

然后按如下方式使用它：

//function_cache - usage
auto fib_cache = add_function_cache(&fib);

//function_cache_old - usage
function<decltype(fib)> fib_fn = &fib;
auto fib_cache_old = add_function_cache_old(fib_fn);

fib_cache(10);
fib_cache(10);

这个想法是创建一个函数，该函数将函数（fun）作为参数并返回另一个函数。返回的函数包装 fun 并为结果提供映射表单输入参数（run_args）。所以它与 fun 具有相同的签名，在地图（缓存）中查找给定参数（run_args）的结果。然后它返回缓存的值或由 fun 计算的结果。显然，如果查找不成功，必须将 fun 的结果添加到缓存中。

问候

简

Answer 3

好吧，使用委托Func<T>可以使它更可重用，而不需要多态性/继承 - 但在 C# 中没有更多的“内置”：

using System;
static class Program {
    static void Main() {
        var func = CachedFunc.Create(() => int.Parse(Console.ReadLine()));

        Console.WriteLine(func.Value);
        Console.WriteLine(func.Value);
    }
}
static class CachedFunc {
    public static CachedFunc<T> Create<T>(Func<T> func) {
        return new CachedFunc<T>(func);
    }
}
class CachedFunc<T> {
    T value;
    Func<T> func;
    public CachedFunc(Func<T> func){
        if (func == null) throw new ArgumentNullException("func");
        this.func = func;
    }
    public T Value {
        get {
            if (func != null) {
                value = func();
                func = null;
            }
            return value;
        }
    }
    public static explicit operator T(CachedFunc<T> func) {
        return func.Value; }
}

Answer 4

C++ 解决方案将与您概述的非常相似，不同之处仅在于const合格的公共接口和（一些）mutable成员的令人兴奋的组合：

class Computer {
    mutable string cache;
  public:
    // I wouldn't call it ComputeXXX
    // since I want to hide the implementation
    // details from my client: for the client
    // there is no change in state due to a call
    // to this function
    const string& StringVal() const {
         if (cache.empty()) {
                // compute cache
         }
         return cache;
    }
    // ...
};              

Answer 5

你可以让它稍微不那么冗长：

private string mComputeStuff_Cached = null;
public string ComputeStuff()
{
  if (mComputeStuff_Cached == null) {
    string result;
    //
    // ...
    //Do lots of cpu intensive computation in order to compute "result" 
    //or whatever you want to compute
    //(for example the hash of a long file)
    //...
    //

    mComputeStuff_Cached  = result;
  }

  return mComputeStuff_Cached ;
}

关于此类模式的其他说明：

• 如果您使用 C++ 和这样的方法const，则无法修改成员，因为它们也被视为const在该方法的上下文中。但是，您可以通过将需要修改的成员标记为 来覆盖它mutable。
• “语义常量”和“按位常量”之间存在差异。当作者将某事标记为const时，它们通常表示“语义 const”（这就是您在本例中的意思），但编译器只能强制执行“按位 const”。
• const方法通常给调用者的印象是它们可以同时从多个线程调用，因为它们没有副作用。在这种类型的模式中，您有“按位”的副作用，但没有“语义”的副作用。因此，如果多个线程可能调用这样的方法，则必须在内部保护此初始化。

Answer 6

您可以使您的成员变量可变（关键字）。

这将允许一个 const 成员函数修改这个值。我一直使用它来缓存中间结果。

Answer 7

您可以在 C++ 中几乎逐字重写此代码

class CClass
{

  private:
     std::string* mComputeStuff_Cached;

  public:
     CClass()
       mComputeStuff_Cached(NULL)
     {

     }

     ~CClass()
     {
           delete mComputeStuff_Cached;
     }


     std::string ComputeStuff()
     {
         if (mComputeStuff_Cached != NULL)
         {
             return mComputeStuff_Cached
         }
         else
         {
             std::string calcedAnswer;
             ...
             // store away answer
             mComputeStuff_Cached = new std::string(calcedAnswer);
         }
     }
};

我不确定检查 mComputeStuff_Cached 是否为空（）是否足够。可能 empty() 是一个合法缓存的结果。

Answer 8

您可以static在函数内使用关键字。它只会计算一次：

std::string GetWidelyUsedValue()
{
   static std::string value = ComputeStuff() ;
   return value ;
}

std::string ComputeStuff()
{
   // Compute the string here.
}