优化昂贵函数的调用次数

Question

我有一个 mainFun，它有四个参数 x、a、b 和 c，所有参数都是矢量值并且可能是变化的长度。此函数调用 expensiveFun 的计算量很大，因此 我想减少对 expensiveFun 的调用次数。需要为 x[i]、a[i]、b[i]、c[i] 中的每个值调用此函数，如果 a、b 或 c 的长度较短，那么它们需要是 "wrapped"（它们的索引是模 a[i % a.size()]）。最好为 x 的每个可能的不同值（即所有整数 0,...,max(x)）预先计算 expensiveFun，然后只填写输出 out out[i] = precomputedValues[x[i]]。如果 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}

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

Answer 1

Memoize 你的函数。

为 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<...> 缺少通用哈希函数。 This Q&A 提供解决此问题的解决方案。

优化昂贵函数的调用次数

Optimizing the number of calls to expensive function

c++

algorithm

performance

combinatorics