c – 缓存优化和多态性

假设我有一个使用std :: function对象实现策略模式的计算器类,如下所示(参见Scott Meyers,Effective 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的签名发生更改,这可能导致将不必要的参数传递给某些函数实现.而且,这些公共和内部数据不再隐藏在代码中的其他组件中,这可能会损害代码的简单性.

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

>定义一个Update方法,用一对给定的双精度x和y计算其内部数据;和
>定义Check方法以确定其当前内部数据是否使用给定的一对x和y计算.

那么我们可以做的是使f和g共享一个CacheFG类的公共实例,这可以使用std :: shared_ptr结构来完成.因此,下面将使用辅助函数f_aux和g_aux创建f和g函数.

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,我现在写这里只是改进了他的方法.他的想法包括使用variadic templates的memoization技术.我只是稍微修改一下,我使用构造std :: decay< Args> :: type来确保仅使用非引用类型定义元组.否则,具有const-reference参数的函数将导致编译错误.

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

为了防止结果的移动,当提供的args是缓存的args时,返回它的副本(返回Ret(结果)).

解决方法:

为什么要创建自己的课程?您无需重新创建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...);
    };
}

如果要在多个函数之间共享,则更改是相同的 – 只需在类中声明它并作为引用传入.

上一篇:c – 为什么使用虚拟表而不是函数指针?


下一篇:侵犯隐私 – C标准如何处理它?