Canceling a recursion tree
SHORT How can I reduce (optimize) the number of operations required in my code?
LONGER . For research, I programmed a set of equations in C ++ to output the sequence if it matches the model. The innermost part of the code uses this function called MANY times at runtime:
int Weight(int i, int q, int d){
int j, sum = 0;
if (i <= 0)
return 0;
else if (i == 1)
return 1;
for (j = 1; j <= d; j++){
sum += Weight((i - j), q, d);
}
sum = 1 + ((q - 1) * sum);
return sum;
}
Therefore, based on the size of the variable d
, the size of the index, i
and how many times this function is called in the rest of the code, a lot of redundant computation is performed. How can I reduce the number of calculations?
Ideally, for example, after a calculation Weight(5, 3, 1)
, how would I tell the computer to substitute in its value, and not recalculate its value when I call Weight(6, 3, 1)
, given that the function is defined recursively?
Will multidimensional vectors work in this case for storing values? Should I just print the values in the file to read? I have yet to run into overflow with the input sizes I give them, but does tail recursion help optimize it?
Note. I am still learning to program and am amazed that I was even able to get a model in the first place.
source to share
You can use memoization
int WeightImpl(int i, int q, int d); // forward declaration
// Use memoization and use `WeightImpl` for the real computation
int Weight(int i, int q, int d){
static std::map<std::tuple<int, int, int>, int> memo;
auto it = memo.find(std::make_tuple(i, q, d));
if (it != memo.end()) {
return it->second;
}
const int res = WeightImpl(i, q, d);
memo[std::make_tuple(i, q, d)] = res;
return res;
}
// Do the real computation
int WeightImpl(int i, int q, int d){
int j, sum = 0;
if (i <= 0)
return 0;
else if (i == 1)
return 1;
for (j = 1; j <= d; j++){
sum += Weight((i - j), q, d); // Call the memoize version to save intermediate result
}
sum = 1 + ((q - 1) * sum);
return sum;
}
Note. When you use a recursive call, you have to be careful about which version to call in order to truly remember each intermediate computation. What I mean is that the recursive function needs to be modified to not call itself, but the memoize version of the function. For a non-recursive function, memoization can be performed without changing the actual function.
source to share
You can use an array to store intermediate values. For example, for some d and q, there is an array that contains the Weight (i, q, d) value at index i.
If you initialize the elements of the array to -1, you can do this in your function like
if(sum_array[i] != -1){ // if the value is pre-calculated
sum += sum_array[i];
}
else{
sum += Weight((i - j), q, d);
}
source to share