Tim - 1 year ago 79
C++ Question

# Optimizing the number of calls to expensive function

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.

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::unordered_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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download