I am attempting to optimize a C++ algorithm that calculates a set of values with corresponding weights. There are n values, with the first being the most recent and the last being the least recent. There are n weights which do not change.
The formula is as follows:
let x = values
let w = weights
(x1 * w1) + (x2 * w2) + ... + (xn * wn)
Take, for instance, this set of values and weights:
Weights: 0.20, 0.15, 0.10, 0.05, 0.01
Values: 5.40, 2.30, 1.60, 9.10, 1.40
Output: 2.054
Calc: (5.40 * 0.20) + (2.30 * 0.15) + (1.60 * 0.10) + (9.10 * 0.05) + (1.40 * 0.01)
As new values are inserted over time, the older ones are shifted down and eventually removed from the set of values entirely, so if a new value, 5.80, was added, the new data set would be:
Weights: 0.20, 0.15, 0.10, 0.05, 0.01
Values: 5.80, 5.40, 2.30, 1.60, 9.10 [1.40 removed]
Output: 2.371
My algorithm currently has to re-calculate the result every time a new value is added. This is still a very quick operation when the set is small, but I would like to scale this up to much larger sets, and doing so can decrease performance.
I am hoping to be able to somehow exploit a mathematical property in the way the calculations are performed so that each time a new value is added I can avoid having to multiply each value by its weight.
I am by no means a mathematician, but I'm under the impression that, since each existing value is shifted to the right, I could somehow calculate a ratio based on the weights and multiply that with the previous output to decrement it before adding the new value multiplied by the first weight. The rationale is treating this as a geometric series, but my test calculations seem to be off, and the n weights are completely arbitrary in production, so I am not certain if that is a viable solution.
In short, my question is: Is there a way in which I can calculate the new value every time a new value is added without having to iterate over the entire set? I need to be able to (at least closely approximate) the new resulting value when the values are shifted.
Edit: I have found an approximate solution, but there is still a margin of error.
The formula is as follows:
Output 2 = (New Value * Weight 1) + ((Sum Weights 2:5)/(Sum Weights 1-5) * Output 1)
Essentially, the values shift over one space, and I take the ratio of the sum of weights 2-5 to the sum of all weights. Then, I multiply the previous output by that ration and add the new value multiplied by the first weight.
If the new value varies too wildly from the mean the error increases though. I'd like to be able to lower that error if possible.