c++ - 优化昂贵函数的调用次数

Question

我有一个 mainFun，它有四个参数 x、a、b 和 c ，所有 vector 值并且可能具有不同的长度。此函数调用计算量很大的 expensiveFun，因此我想减少对 expensiveFun 的调用次数。需要为 x[i]、a[i]、b[i]、c 中的每个值调用此函数[i] 并且如果 a、b 或 c 的长度较短，则需要将它们“包装”(它们的索引是模 a[i % a.size()])。最好为 x 的每个可能的不同值(即所有整数 0,...,max(x))预先计算 expensiveFun，然后仅填充 -在 out[i] = precomputedValues[x[i]] 的输出 out 中。如果 a、b 和 c 具有相同的长度(下面的示例)，这可以很容易地实现，但如果它们不是.当参数 vector 的长度不同时，有什么方法可以使它更有效吗？

下面我提供了一个可重现的例子。这是一个简化的代码，仅作为示例编写。

std::vector<int> expensiveFun(int x, int a, int b, int c) {
  std::vector<int> out(x+1);
  out[0] = a+b*c;
  for (int i = 1; i <= x; i++)
    out[i] = out[i-1] * i + a * (b+c);
  return out;
}

std::vector<int> mainFun(
    std::vector<int> x,
    std::vector<int> a,
    std::vector<int> b,
    std::vector<int> c
) {

  int n = x.size();
  int a_size = a.size();
  int b_size = b.size();
  int c_size = c.size();

  std::vector<int> out(n);

  // easy
  if (a_size == b_size && b_size == a_size) {

    int max_x = 0;
    for (int j = 0; j < n; j++)
      if (x[j] > max_x)
        max_x = x[j];

    for (int i = 0; i < a_size; i++) {
      int max_x = 0;
      for (int j = 0; j < n; j += a_size) {
        if (x[j] > max_x)
          max_x = x[j];
      }
      std::vector<int> precomputedValues = expensiveFun(max_x, a[i], b[i], c[i]);
      for (int j = i; j < n; j += a_size) {
        out[j] = precomputedValues[x[j]];
      }
    }

  // otherwise give up
  } else {

    for (int j = 0; j < n; j++) {
      out[j] = expensiveFun(x[j], a[j % a_size], c[j % c_size], c[j % c_size]).back();
    }

  }

  return out;
}

示例输入:

x = {0, 1, 5, 3, 2, 1, 0, 4, 4, 2, 3, 4, 1}
a = {1, 2, 3}
b = {1, 2}
c = {3, 4, 5, 6}

参数应该折叠成:

x = {0, 1, 5, 3, 2, 1, 0, 4, 4, 2, 3, 4, 1}
a = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1}
b = {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1}
c = {3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3}

目前输出并不重要，因为这里的主要问题是如何有效地处理可变大小的参数 vector 。

Answer 1

Memoize你的功能。

一旦计算出 a、b 和 c 的组合的 vector ，就将其存储在 std::unordered_map 中.下次您看到相同的组合时，您会检索您已经计算过的 vector - 为计算加速支付计算机内存的经典方法。

std::map<std::tuple<int,int,int>,std::vector<int>> memo;

int expensiveFunMemo(int x, int xMax, int a, int b, int c) {
  assert(x <= xMax);
  std::vector<int>& out = memo[std::make_tuple(a, b, c)];
  if (!out.size()) {
    out.push_back(a+b*c);
    for (int i = 1; i <= xMax; i++)
      out.push_back(out[i-1] * i + a * (b+c));
  }
  assert(out.size == xMax+1);
  return out[x];
}

这样你永远不会计算expensiveFunMemo对于 {a, b, c} 的任意组合不止一次。

你的 mainFun也变得更简单:

std::vector<int> mainFun(
    const std::vector<int>& x,
    const std::vector<int>& a,
    const std::vector<int>& b,
    const std::vector<int>& c
) {
  size_t n = x.size();
  size_t a_size = a.size();
  size_t b_size = b.size();
  size_t c_size = c.size();
  std::vector<int> out(n);
  int xMax = *std::max_element(x.begin(), x.end());
  for (size_t j = 0 ; j < n ; j++) {
    out[j] = expensiveFunMemo(x[j], xMax, a[j % a_size], c[j % c_size], c[j % c_size]);
  }
  return out;
}

注意:此解决方案使用 std::map<K,V>而不是 std::unordered_map<K,V>因为std::tuple<...>缺少通用哈希函数。 This Q&A提供解决此问题的解决方案。