Optimizing the number of calls to expensive function

Question

I have an mainFun that takes four parameters x, a, b, and c, all vector-valued and possibly of varying length. This function calls expensiveFun that is computationally expensive so I'd like to reduce the number of calls to expensiveFun. This function needs to be called for each value in x[i], a[i], b[i], c[i] and if a, b, or c are of shorter length, then they need to be "wrapped" (their index is in modulo a[i % a.size()]). It would be the best to precompute the expensiveFun for each possible distinct value of x (i.e. all integers 0,...,max(x)) and then just fill-in the output out by out[i] = precomputedValues[x[i]]. This can be easily achieved if a, b, and c have the same length (example below), but it gets ugly if they are not. Is there any way to make it more efficient for case when the lengths of parameter vectors differ?

Below I provide a reproducible example. It's a simplified code, written just to serve as example.

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

Example input:

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}

Parameters should be folded so that they become:

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}

The output is not important at the moment since the main issue in here is about efficiently dealing with varying-size parameter vectors.

If `a_size == b_size` holds, it's often the case that `b_size == a_size` does too :-P Maybe you meant `c_size`? — j_random_hacker, Nov 08 '16 at 13:02

score 5 · Accepted Answer · edited May 23 '17 at 12:19

Memoize your function.

Once you compute a vector for a combination of a, b, and c, store it in an std::unordered_map. The next time you see the same combination, you retrieve the vector that you have already computed - the classic approach of paying with computer memory for computation speed-up.

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

This way you would never compute expensiveFunMemo for any combination of {a, b, c} more than once.

Your mainFun becomes simpler, too:

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

Note: this solution uses std::map<K,V> instead of std::unordered_map<K,V> because std::tuple<...> lacks a generic hash function. This Q&A offers a solution to fix this problem.

Should this compile without errors? I get `error: no match for 'operator[]' (operand types are 'std::unordered_map, std::vector >' and 'std::tuple')` ... — Tim, Nov 08 '16 at 14:42
@Tim I think this is because `std::tuple<...>` lacks a hash function. Using `std::map` instead of `std::unordered_map` should fix this problem. — Sergey Kalinichenko, Nov 08 '16 at 15:01

Optimizing the number of calls to expensive function

1 Answers1