Suma ponderada de los N últimos números

Question

Supongamos que estamos recibiendo de los números en una secuencia.Después de cada número se recibe, una suma ponderada de los últimos $$ N de los números debe ser calculado, donde los pesos son siempre los mismos, pero arbitrario.

Cómo de manera eficiente puede este hecho si se nos permite mantener una estructura de datos para ayudar con el cálculo?Podemos hacer mejor que $ heta(N)$, es decir,al volver a calcular la suma de cada vez un número es recibido?

Por ejemplo:Supongamos que los pesos son $W= \langle w_1, w_2, w_3, w_4 angle$.En un momento tenemos la lista de los últimos $N$ de números de $L_1= \langle a, b, c, d angle>$, y la suma ponderada $S_1=w_1*a+w_2*b+w_3*c+w_4*d$.

Cuando otro número, $e$, es recibido, hemos de actualización de la lista para obtener $L_2= \langle b,c,d,e angle$ y tenemos que calcular el $S_2=w_1*b+w_2*c+w_3*d+w_4*e$.

Consideración el uso de la FFT Un caso especial de este problema parece ser resueltos de forma eficiente mediante el empleo de la transformada Rápida de Fourier.Aquí, podemos calcular la cantidad de sumas de $S$ en múltiplos de $N$.En otras palabras, recibimos $$ N números y sólo entonces podemos calcular el correspondiente $N$ pesaba sumas.Para ello, necesitamos $N-1$ últimos números (para que las sumas ya han sido calculadas), y $N$ nuevos números, en total $2N-1$ números.

Si este vector de entrada de números y el peso del vector $W$ definen los coeficientes de los polinomios $P(x)$ y $Q(x)$, con coeficientes en $Q$ invertido, vemos que el producto de $P(x)\las veces Q(x)$ es un polinomio cuyos coeficientes en frente de $x^{N-1}$ a $x^{2N-2}$ son exactamente las sumas ponderadas buscamos.Estas pueden ser calculadas usando la FFT en $ heta(N*\log (N))$ de tiempo, lo que nos da un promedio de $Θ(\log (N))$ de tiempo por el número de entrada.

Este no es sin embargo una solución el problema como se ha dicho, porque se requiere que la suma ponderada se calcula de manera eficiente cada el tiempo de un nuevo número es recibido - no podemos retrasar el cálculo.

Answer 1

Aquí es una elaboración de su enfoque.Cada $m$ iteraciones, utilizamos el algoritmo de la FFT para calcular $m$ valores de la convolución en el tiempo $O(n\log n)$, suponiendo que la posterior $m$ valores son cero.En otras palabras, estamos calculando $$ \sum_{i=0}^{n-1} w_i a_{t-i+k}, \quad 0 \leq k \leq m-1, $$ donde $w_i$ son $n$ pesos (o a la inversa pesos), $a_i$ es la secuencia de entrada, $t$ es el tiempo actual, y $a_{t} = 0$ para $t' > t$.

Para cada uno de los siguientes $m$ iteraciones, somos capaces de calcular la convolución en el tiempo $S(m)$ (la $i$ésima iteración necesita tiempo $O(i)$).Así que la amortizado tiempo es $O(m) + O(n\log n/m)$.Este es minimizado por la elección de $m = \sqrt{n\log n}$, lo que da una amortizado en el tiempo de ejecución de $O(\sqrt{n\log n})$.

Podemos mejorar este al peor de los casos el tiempo de ejecución $O(\sqrt{n\log n})$ por la rotura de la computación en partes.Revisión $m$, y definir $$ b_{T,p,s} = \sum_{i=0}^{m-1} w_{pm+i} a_{Tm-i+o}, \quad C_{T,p} = b_{T,p,0}, \ldots, b_{T,p,m-1}.$$ Cada $C_{T,p}$ sólo depende de us $2 millones$ de entrada, por lo que puede ser calculado en tiempo $O(m\log m)$.También, dado $C_{\lfloor t/m floor-p,p}$ para $0 \leq p \leq n/m-1$, podemos calcular la convolución en el tiempo $O(n/m + m)$.Por ello el plan es mantener la lista $$ C_{\lfloor t/m floor-p,p}, \quad 0 \leq p \leq n/m-1.$$ Para cada período de $m$ entradas, necesitamos actualizar $n/m$ de estos.Cada actualización lleva tiempo $O(m\log m)$, así que si llegamos a la difusión de estas actualizaciones de manera uniforme, cada entrada va a tomar el trabajo $O((n/m^2) m\log m) = O((n/m) \log m)$.Junto con el cómputo de la convolución del mismo, el tiempo por la complejidad de la entrada es $O((n/m)\log m + m)$.La elección de $m = \sqrt{n\log n}$ como antes, esto le da $O(\sqrt{n\log n})$.