3

假设我有一个计算器类，它使用std::function以下对象实现策略模式（参见 Scott Meyers，Effective C++：55 Specific Ways to Improvement Your Programs and Designs）：

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和的函数在内部执行昂贵且相同的计算以获得最终结果。为了提高效率，可以将所有公共数据包装在 a 中，计算一次并作为参数提供给它们。然而，这种设计有几个缺陷。例如，这会导致 的签名发生变化，从而导致将不必要的参数传递给某些函数实现。此外，这些通用和内部数据不再对代码中的其他组件隐藏，这可能会损害代码的简单性。gFunctionstructFunction

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

  1. 定义一个方法，用给定的双精度和Update计算其内部数据；和xy
  2. 定义一种Check方法来确定其当前内部数据是否是使用给定的双精度对x和计算的y。

然后可以做的是制作f并g共享一个类的公共实例CacheFG，这可以使用std::shared_ptr构造来完成。因此，下面将是使用辅助函数创建f和g函数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来确保 a 的定义tuple仅具有非引用类型。否则，带有 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...);
    };
}

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

4

2 回答 2

6

Why create your own class? There's no need for you to fail to re-create the interface of unordered_map. This functionality can be added as a re-usable algorithm based on std::function and std::unordered_map. It's been a while since I worked with variadic templates, but I hope you get the idea.

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

I don't recall, offhand, whether std::hash natively supports tuples. If not, you might need to add it, or use std::map which does natively support them.

Edit: Hmm, I didn't notice that you wanted to share the cache. Well, this shouldn't be too difficult a problem, just stick an unordered_map member in Calculator and pass it in by reference, but the semantics of doing so seem a bit... odd.

Edit again: Just the most recent value? Even simpler.

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

If you want to share between several Functions, then the alteration is the same- just declare it in the class and pass in as reference.

于 2012-10-25T11:22:32.287 回答
2

优化之前 - 测量。然后，如果您真的执行许多具有相同值的计算 - 然后创建此缓存对象。我想隐藏缓存检查和更新 CacheFG::get(x, y)并像const auto value = cache->get(x,y).

于 2012-10-25T11:11:47.660 回答