Desviación estándar de cómputo en un flujo

Utilizando Python, suponga que estoy ejecutando una cantidad conocida de elementos I , y tengo la capacidad de calcular cuánto tiempo lleva procesar cada una t , así como un total acumulado del tiempo empleado en procesar T y la cantidad de elementos procesados ​​de manera lejos c . Actualmente estoy calculando el promedio sobre la marcha A = T / c pero esto puede desviarse por ejemplo un solo elemento que tarda un tiempo extraordinariamente largo en procesarse (unos segundos en comparación con unos pocos milisegundos).

Me gustaría mostrar una desviación estándar en ejecución. ¿Cómo puedo hacer esto sin mantener un registro de cada t ?

Utilizo el Método de Welford , que da resultados más precisos. Este enlace apunta al resumen de John D. Cook . Aquí hay un párrafo de él que resume por qué es un enfoque preferido:

Esta mejor manera de calcular la variación se remonta a un artículo de 1962 de BP Welford y se presenta en El arte de la progtwigción de computadoras de Donald Knuth, Vol. 2, página 232, 3ª edición. Aunque esta solución se conoce desde hace décadas, no hay suficientes personas que la conozcan. La mayoría de las personas probablemente no se dan cuenta de que calcular la varianza de la muestra puede ser difícil hasta la primera vez que calculan una desviación estándar y obtienen una excepción por tomar la raíz cuadrada de un número negativo.

Como se describe en el artículo de Wikipedia sobre la desviación estándar , es suficiente realizar un seguimiento de las siguientes tres sums:

 s0 = sum(1 for x in samples) s1 = sum(x for x in samples) s2 = sum(x*x for x in samples) 

Estas sums se actualizan fácilmente a medida que llegan nuevos valores. La desviación estándar se puede calcular como

 std_dev = math.sqrt((s0 * s2 - s1 * s1)/(s0 * (s0 - 1))) 

Tenga en cuenta que esta forma de calcular la desviación estándar puede estar mal condicionada numéricamente si sus muestras son números de punto flotante y la desviación estándar es pequeña en comparación con la media de las muestras. Si espera muestras de este tipo, debe recurrir al método de Welford (ver la respuesta aceptada).

Basado en el algoritmo de Welford :

 import numpy as np class OnlineVariance(object): """ Welford's algorithm computes the sample variance incrementally. """ def __init__(self, iterable=None, ddof=1): self.ddof, self.n, self.mean, self.M2 = ddof, 0, 0.0, 0.0 if iterable is not None: for datum in iterable: self.include(datum) def include(self, datum): self.n += 1 self.delta = datum - self.mean self.mean += self.delta / self.n self.M2 += self.delta * (datum - self.mean) @property def variance(self): return self.M2 / (self.n - self.ddof) @property def std(self): return np.sqrt(self.variance) 

Actualice la varianza con cada nueva pieza de datos:

 N = 100 data = np.random.random(N) ov = OnlineVariance(ddof=0) for d in data: ov.include(d) std = ov.std print(std) 

Verifique nuestro resultado contra la desviación estándar calculada por numpy:

 assert np.allclose(std, data.std())