Tim - 1 year ago 64

C++ Question

I have an

`mainFun`

`x`

`a`

`b`

`c`

`expensiveFun`

`expensiveFun`

`x[i]`

`a[i]`

`b[i]`

`c[i]`

`a`

`b`

`c`

`a[i % a.size()]`

`expensiveFun`

`x`

`out`

`out[i] = precomputedValues[x[i]]`

`a`

`b`

`c`

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.

Answer Source

*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::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;
}
```