Как ускорить алгоритм скользящего среднего?

Question

[AlexNew22]

Как ускорить алгоритм скользящего среднего?

const arr = [9, 3, 2, 0, 1, 5, 1, 0, 0]
const step = 3

function movingAverage(array, windowSize) {
  const result = []
  for(let i = 0; i < array.length - windowSize + 1; ++i) {
  	const sum = array.slice(i, windowSize + i).reduce((acc, val) => acc + val, 0)
    const middle = sum/windowSize
    result.push(middle)
  }
  return result
}
console.log(movingAverage(arr, step))

Answer 1

[Rsa97]

const movingAverage = (data, windowSize) => {
  let sum = data.slice(0, windowSize).reduce((acc, cur) => acc + cur, 0);
  const result = [sum / windowSize];
  for (let i = windowSize; i < data.length; i += 1) {
    sum = sum - data[i - windowSize] + data[i];
    result.push(sum / windowSize);
  }
  return result;
};
console.log(movingAverage([9, 3, 2, 0, 1, 5, 1, 0, 0], 3));
// Array(7) [ 4.666666666666667, 1.6666666666666667, 1, 2, 2.3333333333333335, 2, 0.3333333333333333 ]

Comments

[AlexNew22]

Спасибо!
Где можно почитать логику действий данного решения?
Т.е. для чего нам нужна изначальная сумма и нулевое значение в массиве?
И почему вычисление происходит так sum = sum - data[i - windowSize] + data[i]?

[Wataru]

AlexNew22, Вместо среднего вычисляется сумма в скользящем окне. Среднее же вычисляется как сумма, деленная на количество чисел в окне. Для пересчета суммы при сдвиге окна надо лишь добавить одно новое число справа и убрать отдно старое число слева.

Answer 2

[mayton2019]

Для расчета среднего нам нужна сумма элементов и количество. Количество - это константа.

Сумма конечно меняется. Но если у нас уже есть расчитанная сумма от 1 000 000 элементов то
следующее скользящее среднее будет не сильно отличаться. Нужно от сумма забрать первый элемент
и добавить элемент с индексом 1 000 001. Это и есть оптимизация.

Тоесть первая итерация расчитывается полностью. Следующая - на основании предыдущей. Как в численных
методах.