I have a large set of values (let's say 1M entries) where I need to apply an exponential smoothing algorithm, but only incrementing one value at a time (all others decay to zero). The trivial implementation would be (pseudo-code):function smooth_once(index, x):    // Decay everything    for s in s_vec:        s = s * (1 - alpha)    // Only increase one value, for the other x=0    s_vec[index] += alpha * xfunction get_s(index):    return s_vec[index]This is rather slow, as every element of s_vec need to be scanned at every iteration, whereas only one need to be incremented. Also, I only need to check few values from s_vec from time to time (much less frequently than the frequency at which smooth_once is called).Note: the smoothing and read sequence is unpredictable, and is usually interleaved, for example:smooth_once(6573, 1.23)get_s(8892)smooth_once(3345, 2.45)smooth_once(6874, 1.10)get_s(3345)get_s(1254)...etc...In order to speed up this, I was thinking of multiplying the x value by a factor (scale) which is multiplied every time, and dividing everything when the factor grows too large. Basically, this boils down to rescale everything by an exponentially-incrementing factor.scale = 1k = 1 / (1 - alpha)function optimized_smooth(index, x):    // Rescale everything    scale = scale * k    if scale > scale_max:        // Switch back scale to 1        for s in s_vec:            s = s / scale        scale = 1    s_vec[index] = v + alpha * x * scalefunction get_s(index):    // Scale back for reading    return s_vec[index] / scaleIMHO this would be much faster (assuming k is not too large), as you only need to scan s_vec when the scale overflow and you rescale the whole array.What do you think of this method?Is this already known and has a name?Apart from loosing a few bits of precision on the values (depending on beta_max), do you see any drawbacks?Addendum. A small demo program shows that both algorithms end up with the same result on a controlled sequence of smoothing indexes.
Optimizing the exponential smoothing of a big array
algorithms;performance;math;algorithm analysis