优化昂贵函数调用的次数

Question

优化昂贵函数调用的次数

3

我有一个mainFun函数，它接受四个参数x，a，b和c，这些参数都是向量值，长度可能不同。该函数调用了一个计算成本高昂的函数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具有相同的长度(如下面的示例所示)，则可以轻松实现这一点，但如果它们长度不同，则会变得复杂。是否有任何方法使长度不同的参数向量更加有效率呢？

下面提供了一个可重现的示例代码，仅用于示例。

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}

目前输出并不重要，因为这里的主要问题是有效地处理大小不同的参数向量。

- Tim

如果 a_size == b_size 成立，通常情况下 b_size == a_size 也成立 :-P 也许你想说的是 c_size？ - j_random_hacker

@j_random_hacker，确实这就是我想表达的意思。 - Tim

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

记忆化你的函数。

当你计算出一个由a，b和c组合而成的向量时，将其存储在一个std::unordered_map中。下一次当你看到相同的组合时，你可以检索到已经计算好的向量——这是通过以计算速度为代价来使用计算机内存的经典方法。

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];
}

这样，您将永远不会对 {a, b, c} 的任何组合计算expensiveFunMemo超过一次。

您的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<...>缺少通用哈希函数。此问答提供了解决此问题的方法。