Посчитать потоковые среднее и дисперсию, не помещающиеся в память
stream — итерируемое число значений, слишком большое для списка; пройти по нему можно лишь один раз. Верните (mean, variance), используя выборочную дисперсию (делите на n - 1). Примените онлайн-алгоритм Уэлфорда, чтобы один проход с памятью O(1) оставался численно устойчивым.
Для менее чем двух значений верните дисперсию 0.0.
def running_mean_var(stream) -> tuple[float, float]:
# ваш код здесьНапишите реализацию.
Уэлфорд держит счётчик, среднее и сумму квадратов отклонений M2, обновляя их на каждом элементе за один проход с памятью O(1). Выборочная дисперсия — M2 / (n - 1). Он избегает наивной sum(x**2) - sum(x)**2 / n, что катастрофически сокращается.
- ✗Брать сумму квадратов минус квадрат суммы — катастрофическое вычитание
- ✗Буферизовать весь поток, срывая цель памяти O(1)
- ✗Делить на n вместо n-1 для выборочной дисперсии
- →Почему наивная формула двух сумм теряет точность?
- →Как слить два независимо посчитанных частичных состояния?
Welford keeps n, the running mean, and M2 (the running sum of squared deviations from the current mean). Each element nudges the mean, and M2 accumulates the product of the deviations before and after that nudge.
def running_mean_var(stream):
n = 0
mean = 0.0
m2 = 0.0
for x in stream:
n += 1
delta = x - mean
mean += delta / n
m2 += delta * (x - mean)
if n < 2:
return (mean, 0.0)
return (mean, m2 / (n - 1))It is one pass and O(1) memory, and — unlike sum(x**2) - sum(x)**2 / n — it never subtracts two huge nearly-equal numbers, so it stays accurate even when the values are large and the variance is small.
