# Optimizing the exponential smoothing of a big array

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.

• It is not clear to me which problem you trying to solve. `s_vec` is modified in a specific manner by `smooth_once`. It seems `smooth_once` is called in a specific context which you did not describe. Doesn't that context need the intermediate values of the whole `s_vec`, as it was calculated by `smooth_once`? – Doc Brown May 17 '16 at 12:34
• `smooth_once` is called very frequently with unpredictable index and x. `s_vec` is "large" (think 1M entries), but I need to check its values only infrequently. Iterating 1M entries for each call to `smooth_once` is a performance killer. – Laurent Grégoire May 17 '16 at 12:39

After thinking twice about your solution, I am sure that your algorithm works well. IMHO it could be seen as a variant of lazy evaluation. Here is another variant.

Change `smooth_once` so it only puts the pairs `(index,x)` into a queue (lets call the arrays `indexes` and `xs`).

``````function smooth_once(index, x):
indexes.append(index)
xs.append(x)
``````

Here is the method to calculcate the smoothing for the whole queue at once:

``````function nth_smooth(indexes, xs):
n = size(indexes)  // equal to size(xs)
if n==0:
return
cn = (1-alpha) ** n // (1-alpha) to the power of n
for s in s_vec:
s = s * cn
c=1
for i = 0 to n-1:
s_vec[indexes[i]] += alpha * xs[i] *c
c = c * (1-alpha)
``````

And here is the method to retrieve the result:

``````function get_s(index):
nth_smooth(indexes,xs)
indexes.clear()
xs.clear()
return s_vec[index]
``````

I guess it is not too hard to understand why this works, it simply replaces the repeated multiplications of `s_vec` with `1-alpha` by one multiplication with `(1-alpha) ** n`, and adds the "x*alpha" additions afterwards, taking the influence of `1-alpha` to those pertubances into account.

However, if this will be faster or slower than your own proposal depends on the number of calls of `smooth_once` before the next `get_s` occurs, compared to the frequency of having the condition `scale > scale_max` fulfilled (in your variant).

• With this solution you can't read values of `s_vec` anytime during the smoothing sequence. Since my read/write sequence is not predictable this can't work. I'll update my question to add this context. – Laurent Grégoire May 18 '16 at 7:21
• @LaurentGrégoire: see my edit – Doc Brown May 18 '16 at 13:18
• Your other solution is really nice. I think picking the best method will also depend on alpha: for small alpha (k~=1) the "dynamic rescale" would work best as down-scaling will not happen often; for large alpha the "smooth Q" will perform better. In my specific case alpha is very low and the smooth/get pattern is interleaved a lot. – Laurent Grégoire May 18 '16 at 13:49