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 * x function 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 = 1 k = 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 * scale function get_s(index): // Scale back for reading return s_vec[index] / scale
IMHO 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.