3

我有一个函数，f(a,b)它接受两个输入。我不知道将使用a和的哪些值。b我可以在内存上有点浪费（我关心速度）。我希望能够检查 的输出f(a,b)是否已经交付，如果是，则再次交付该输出，而无需重新运行该f(a,b)流程。

在 Python 中使用装饰器很容易做到这一点，但 C++ 在我这里是遥不可及的。

4

5 回答 5

7

我会使用一个std::map（或者可能是一个std::unordered_map），它的键是一个std::pair，或者可能使用一个地图的地图。

在这种情况下，C++11 的改进可能会有所帮助。或者也许是一些 Boost 的东西。

于 2012-04-11T19:37:34.567 回答
3

海报问：

我希望能够检查 f(a,b) 的输出是否已经交付，如果是，则再次交付该输出，而无需重新运行 f(a,b) 流程。

在 C++ 中使用std::map. 函数恰好有两个参数这一事实意味着我们可以std::pair用来描述它们。

#include <map>
#include <iostream>

uint64_t real_f(int a, int b) {
  std::cout << "*";
  // Do something tough:
  return (uint64_t)a*b;
}

uint64_t memo_f(int a, int b) {
  typedef std::pair<int, int> key;
  typedef std::map<key, uint64_t> map;
  static map m;
  key k(a,b);
  map::iterator it = m.find(k);
  if(it == m.end()) {
    return m[k] = real_f(a, b);
  }
  return it->second;
}

int main () {
  std::cout << memo_f(1, 2) << "\n";
  std::cout << memo_f(3, 4) << "\n";
  std::cout << memo_f(1, 2) << "\n";
  std::cout << memo_f(3, 4) << "\n";
  std::cout << memo_f(5, 6) << "\n";
}

上述程序的输出是：

*2
*12
2
12
*30

没有星号的行代表缓存的结果。

于 2012-04-11T20:14:45.930 回答
1

使用 C++11，您可以使用任务和期货。让f成为你的功能：

int f(int a, int b)
{
    // Do hard work.
}

然后你会安排函数执行，它会返回一个返回值的句柄。这个句柄被称为未来：

template <typename F>
std::future<typename std::result_of<F()>::type>
schedule(F f)
{
    typedef typename std::result_of<F()>::type result_type;
    std::packaged_task<result_type> task(f);
    auto future = task.get_future();

    tasks_.push_back(std::move(task)); // Queue the task, execute later.
    return std::move(future);
}

然后，您可以按如下方式使用此机制：

auto future = schedule(std::bind(&f, 42, 43)); // Via std::bind.
auto future = schedule([&] { f(42, 43); });    // Lambda alternative.

if (future.has_value())
{
    auto x = future.get();  // Blocks if the result of f(a,b) is not yet availble.
    g(x);
}

免责声明：我的编译器不支持任务/期货，所以代码可能有一些粗糙的边缘。

于 2012-04-11T19:55:29.950 回答
0

关于这个问题的要点是计算 f(a,b) 和保留某种查找表以缓存结果之间的 CPU 和 RAM 的相对开销。

由于 128 位索引长度的详尽表（还）不可行，我们需要将查找空间减少到可管理的大小 - 如果在您的应用程序内部没有一些考虑，这是无法完成的：

  • 函数输入的实际使用空间有多大？里面有图案吗？
  • 时间成分呢？您是否希望重复计算彼此接近或沿时间线分布？
  • 分布情况如何？您是否假设索引空间的一小部分会消耗大部分函数调用？

我会简单地从一个固定大小的元组数组(a,b, f(a,b))和线性搜索开始。根据上面询问的模式，您可能想要

  • 窗口滑动它（在缓存未命中时删除最旧的）：这对本地化重复有好处
  • 具有(a,b,f(a,b),count)最小计数的元组被驱逐的元组 - 这对非本地化事件有好处
  • 有一些关键功能确定缓存中的位置（这有利于小索引空间的使用）
  • 高德纳或谷歌可能想到的任何其他东西

如果查找机制变得越来越复杂，您可能还希望根据查找机制对重复计算进行基准测试：std::map并且朋友不是免费的，即使他们是高质量的实现。

于 2012-04-11T20:21:38.460 回答
0

唯一简单的方法是使用std::map. std::unordered_map不起作用。我们不能std::pair在无序映射中用作键。您可以执行以下操作，

std::map<pair<int, int>, int> mp; 

int func(int a, int b)
{
  if (mp.find({a, b}) != mp.end()) return mp[{a, b}];
  // compute f(a, b)...
  mp[{a, b}] = // computed value;
  return mp[{a, b}];
}
于 2021-03-04T02:17:51.920 回答