缓存优化与多态性

Question

假设我有一个计算器类，它使用std::function对象实现策略模式，如下所示(参见Scott，有效C++：55种改进程序和设计的特定方法)：

class Calculator
{
public:
  ...
  std::vector<double> Calculate(double x, double y)
  {
     std::vector<double> res;
     for(const Function& f : functions)
        res.push_back(f(x,y));
     return res;
  }

private:
  std::vector<Function> functions;
};

哪里

typedef std::function<double(double,double)> Function;

下面是我面临的问题:假设函数f和g (都是Function类型)在内部执行昂贵和相同的计算，以获得最终结果。为了提高效率，可以将所有公共数据封装在一个struct中，计算一次并作为参数提供给它们。然而，这种设计有几个缺陷。例如，这将导致Function签名的更改，这可能导致不必要的参数传递给某些函数实现。此外，这些公共和内部数据不再对代码中的其他组件隐藏，这会损害代码的简单性。

我想讨论以下优化策略:实现一个类CacheFG，它：

1. 定义一个Update方法，该方法使用给定的双x和y来计算其内部数据；以及
2. 定义Check方法，以确定其当前内部数据是否使用给定的双倍x和y计算。

然后，我们可以做的是让f和g共享类CacheFG的一个公共实例，这可以使用std::shared_ptr构造来完成。因此，下面将使用辅助函数f和g_aux创建f_aux和g_aux函数。

double f_aux(double x, double y, const std::shared_ptr<CacheFG>& cache)
{
   if(not cache->Check(x,y))
      cache->Update(x,y);
   ...
}

std::shared_ptr<CacheFG> cache;
Function f = std::bind(f_aux, _1, _2, cache);
Function g = std::bind(g_aux, _1, _2, cache);

我的问题是：(1)这是一种安全的优化方法吗？(2)是否有更好的方法来解决这个问题？

编辑:经过几个答案之后，我发现我在这里的意图是在C++中实现一种回忆法。我注意到，仅最后计算的状态对我的目的来说就足够了。

多亏了DeadMG，我现在将在这里写一个与他的方法相比的改进。他的想法包括与可变模板一起使用回忆录技巧。我只是提供了一个小小的修改，在这里我使用构造std::decay<Args>::type来确保只使用非引用类型的tuple的定义。否则，带有const引用参数的函数将导致编译错误。

template<typename Ret, typename... Args>
std::function<Ret(Args...)> MemoizeLast(std::function<Ret(Args...)> f)
{
    std::tuple<typename std::decay<Args>::type...> cache;
    Ret result = Ret();
    return [=](Args... args) mutable -> Ret
    {
        if(std::tie(args...) == cache)
            return Ret(result);
        cache = std::make_tuple(args...);
        return result = f(args...);
    };
}

为了防止result的移动，当提供的args被缓存时，返回它的副本(return Ret(result))。

Answer 1

为什么要创建自己的类？您没有必要无法重新创建unordered_map的接口。该功能可以添加为基于std::function和std::unordered_map的可重用算法。我已经有一段时间没有使用各种模板了，但我希望您能理解这个想法。

template<typename Ret, typename... Args> 
std::function<Ret(Args...)> memoize(std::function<Ret(Args...)> t) {
    std::unordered_map<std::tuple<Args...>, Ret> cache;
    return [=](Args... a) mutable -> Ret {
        if (cache.find(std::make_tuple(a...)) != cache.end())
            return cache[std::make_tuple(a...)];
        else
            return cache[std::make_tuple(a...)] = t(a...);
    };
}

我不记得std::hash本机是否支持元组。如果没有，您可能需要添加它，或者使用std::map来支持它们。

编辑:嗯，我没注意到你想共享缓存。嗯，这应该不是一个太难的问题，只要把一个unordered_map成员放在计算器中并通过引用传递它，但是这样做的语义似乎有点.很奇怪。

再次编辑:只是最近的价值？甚至更简单。

template<typename Ret, typename... Args> 
std::function<Ret(Args...)> memoize_last(std::function<Ret(Args...)> t) {
    std::tuple<Args...> cache;
    Ret result;
    return [=](Args... a) mutable -> Ret {
        if (std::tie(a...) == cache)
            return result;
        cache = std::make_tuple(a...);
        return result = t(a...);
    };
}

如果您想要在多个函数之间共享，那么修改是相同的--只需在类中声明它并作为引用传入。

Answer 2

在优化措施之前。然后，如果您确实以相同的值执行了许多计算，那么创建这个缓存对象。我想在CacheFG::get(x, y)中隐藏缓存检查和更新，并像const auto value = cache->get(x,y)一样使用它。