Suma ponderada de los últimos N números

19

Supongamos que estamos recibiendo números en una secuencia. Después de recibir cada número, se debe calcular una suma ponderada de los últimos N números, donde los pesos son siempre los mismos, pero arbitrarios.

¿Cuán eficiente puede hacerse esto si se nos permite mantener una estructura de datos para ayudar con el cálculo? ¿Podemos hacer algo mejor que Θ(N) , es decir, volver a calcular la suma cada vez que se recibe un número?

Por ejemplo: Supongamos que los pesos son W=w1,w2,w3,w4 . En un momento tenemos la lista de los últimos N números L1=a,b,c,d> , y la suma ponderada S1=w1a+w2b+w3c+w4d .

Cuando otro número, e es recibido,, actualizamos la lista para obtener L2=b,c,d,e y tenemos que calcular S2=w1b+w2c+w3d+w4e .

Consideración usando FFT Un caso especial de este problema parece resolverse eficientemente empleando la Transformada Rápida de Fourier. Aquí, calculamos las sumas pesadas S en múltiplos de N . En otras palabras, recibimos N números y solo entonces podemos calcular las N sumas pesadas correspondientes . Para hacer esto, necesitamos N1 números pasados ​​(para los cuales ya se han calculado sumas), y N nuevos números, en total 2N1 números.

Si este vector de números de entrada y el vector de peso W definen los coeficientes de los polinomios P(x) y Q(x) , con los coeficientes en Q invertidos, vemos que el producto P(x)×Q(x) es un polinomio cuyos coeficientes delante de xN1 hasta x2N2 son exactamente las sumas ponderadas que buscamos. Estos se pueden calcular utilizando FFT en Θ(Nlog(N)) tiempo, que nos da un promedio deΘ(log(N))tiempo por número de entrada.

Sin embargo, esta no es una solución al problema como se indicó, porque se requiere que la suma ponderada se calcule eficientemente cada vez que se recibe un nuevo número; no podemos retrasar el cálculo.

Ambroz Bizjak
fuente
Tenga en cuenta que puede usar LaTeX aquí.
Raphael
¿Las entradas provienen de alguna distribución conocida? ¿Tienen alguna propiedad matemática útil? Si no lo hacen, entonces es poco probable que esto sea posible (a menos que alguien pueda encontrar una forma cerrada ordenada que sea computable sublineal; ciertamente no puedo encontrar una). Además, ¿están bien las aproximaciones? Ese podría ser un camino a seguir si es útil para usted.
RDN
Los filtros FIR hacen esto, por lo que su diseño será relevante.
adrianN
@RDN Planteé esta pregunta como una curiosidad, no tengo una aplicación práctica en mente.
Ambroz Bizjak

Respuestas:

6

Aquí hay una elaboración de su enfoque. Cada iteraciones, utilizamos el algoritmo FFT para calcular los valores de la convolución en el tiempo , suponiendo que los valores subsiguientes sean cero. En otras palabras, estamos calculando donde son los pesos (o los pesos inversos), es la secuencia de entrada, es la hora actual y para .m O ( n log n ) m n - 1 i = 0 w i a t - i + k ,mmO(nlogn)mw i n a i t a t = 0 t > t

i=0n1wiati+k,0km1,
winaitat=0t>t

Para cada uno de los siguientes iteraciones, somos capaces de calcular la convolución requerida en el tiempo (el ésimo iteración necesita tiempo ). Entonces el tiempo amortizado es . Esto se minimiza eligiendo , que proporciona un tiempo de ejecución amortizado de .mO(m)iO(i)O(m)+O(nlogn/m)m=nlognO(nlogn)

Podemos mejorar esto al peor tiempo de ejecución de dividiendo el cálculo en partes. Arregle , y defina Cada depende solo de entradas de , por lo que se puede calcular en el tiempo . Además, dado para , podemos calcular la convolución en el tiempo . Por lo tanto, el plan es mantener la lista Para cada período deO(nlogn)m

bT,p,o=i=0m1wpm+iaTmi+o,CT,p=bT,p,0,,bT,p,m1.
CT,p2mO(mlogm)Ct/mp,p0pn/m1O(n/m+m)
Ct/mp,p,0pn/m1.
mentradas, necesitamos actualizar de estas. Cada actualización lleva tiempo , por lo que si distribuimos estas actualizaciones de manera uniforme, cada entrada tomará trabajo . Junto con el cálculo de la propia convolución, la complejidad de tiempo por entrada es . Al elegir como antes, esto da .n/mO(mlogm)O((n/m2)mlogm)=O((n/m)logm)O((n/m)logm+m)m=nlognO(nlogn)
Yuval Filmus
fuente
Maravillosa solución, gracias, no estaba realmente seguro de si se puede hacer.
Ambroz Bizjak
¡Y funciona! Implementación de C: ideone.com/opuoMj
Ambroz Bizjak
Meh, me faltaba ese último bit de código que realmente hace que rompa el cálculo, arreglado aquí ideone.com/GRXMAZ .
Ambroz Bizjak
En mi máquina, este algoritmo comienza a ser más rápido que el algoritmo simple en alrededor de 17000 pesos. Para pequeñas cantidades de pesas es lento. Benchmark: ideone.com/b7erxu
Ambroz Bizjak
¡Muy impresionante que realmente hayas implementado esto! Probablemente desee optimizar sobre . La opción es solo una guía aproximada, y podría no ser óptima. ¿Intentaste ejecutar el algoritmo con diferentes valores de ? m = m mm=nlognm
Yuval Filmus