Как эффективно вычислять среднее значение "на лету" (скользящее среднее)?

Я придумал этот

n=1;
curAvg = 0;
loop{
  curAvg = curAvg + (newNum - curAvg)/n;
  n++;
}

Я думаю, что основные моменты этого пути:
- Он избегает больших чисел (и возможного переполнения, если вы суммируете, а затем разделите)
- вы сохраняете один регистр (не нужно хранить сумму)

Проблема может быть связана с суммирующей ошибкой - но я предполагаю, что в общем случае должны быть сбалансированные числа округления и округления вниз, чтобы ошибка не суммировалась резко.

Вы видите какие-либо подводные камни в этом решении? Есть ли у вас лучшее предложение?

Ответ 1

Ваше решение - это, по сути, "стандартное" оптимальное онлайн-решение для поддержания средней скорости работы без хранения больших сумм, а также при запуске "онлайн", т.е. вы можете обрабатывать только одно число за раз, не возвращаясь к другим номерам, и вы используете только постоянное количество дополнительной памяти. Если вы хотите немного оптимизированное решение с точки зрения числовой точности за счет "онлайн", то при условии, что ваши номера будут неотрицательными, затем сначала сортируйте свои номера от самых маленьких до крупнейших, а затем обработайте их в этом порядке, так же, как и сейчас. Таким образом, если вы получите кучу чисел, которые на самом деле малы по равному, а затем вы получите одно большое число, вы сможете точно вычислить среднее значение без underflow, а не если вы обработали большое число в первую очередь.

Ответ 2

Формула выше - вздор. Простая математика и точность определяли бы:

n - это счетчик итераций, AV работает в среднем, newVal - новое значение

инициализация n=0, AV=0

( (AV * n) + newVal ) / (n+1) = AV

Нет ярлыка, вы должны иметь все числа и делить их на количество итераций, однако вы можете перестроить одно из чисел, зная, какая итерация это, это тотализатор для ведения общей суммы или повтора -калькулировать его. Время для перевычисления стоит дорого, стоимость хранения номера, вероятно, низкая стоимость с точки зрения памяти, а код для повторного вычисления, безусловно, будет больше, чем место памяти для хранения всего итерации.