Soma ponderada dos últimos N números

19

Suponha que estamos recebendo números em um fluxo. Depois que cada número é recebido, uma soma ponderada dos últimos N números precisa ser calculada, onde os pesos são sempre os mesmos, mas arbitrários.

Com que eficiência isso pode ser feito se tivermos permissão para manter uma estrutura de dados para ajudar no cálculo? Podemos fazer algo melhor que Θ(N) , ou seja, recalcular a soma cada vez que um número é recebido?

Por exemplo: Suponhamos que os pesos são W=W1,W2,W3,W4 . Em um ponto que tem a lista dos últimos N números eu1=uma,b,c,d> , e a soma ponderada S1=w1a+w2b+w3c+w4d .

Quando um outro número, e , é recebida, que actualizar a lista para obter L2=b,c,d,e e é preciso calcular S2=w1b+w2c+w3d+w4e .

Consideração sobre o uso da FFT Um caso especial desse problema parece ser solucionável com eficiência, empregando a Transformada rápida de Fourier. Aqui, nós calcular as somas ponderadas em múltiplos de N . Em outras palavras, nós recebemos N números e só então podemos calcular as N somas ponderadas correspondentes . Para fazer isso, precisamos de números anteriores N - 1 (para os quais as somas já foram computadas) e N novos números, no total de 2 números N - 1 .SNNNN1N2N1

Se esse vetor de números de entrada e o vetor de peso definem os coeficientes dos polinômios P ( x ) e Q ( x ) , com os coeficientes em Q invertidos, vemos que o produto P ( x ) × Q ( x ) é um polinômio cujos coeficientes na frente de x N - 1 até x 2 N - 2 são exatamente as somas ponderadas que buscamos. Estes podem ser calculados usando FFT em Θ ( N logWP(x)Q(x)QP(x)×Q(x)xN1x2N2 , que nos dá uma média de Θ ( log ( N ) ) por número de entrada.Θ(Nlog(N))Θ(log(N))

No entanto, essa não é uma solução para o problema, conforme declarado, porque é necessário que a soma ponderada seja computada com eficiência cada vez que um novo número for recebido - não podemos atrasar o cálculo.

Ambroz Bizjak
fonte
Observe que você pode usar o LaTeX aqui.
Raphael
As entradas são provenientes de alguma distribuição conhecida? Eles possuem propriedades matemáticas úteis? Se não o fizerem, é improvável que isso seja possível (a menos que alguém seja capaz de encontrar uma forma bem organizada e fechada que seja computável sublinear - eu certamente não consigo encontrar uma). Além disso, as aproximações estão OK? Esse pode ser um caminho a percorrer, se for útil para você.
RDN
Os filtros FIR fazem isso, portanto seu design será relevante.
Adriann
@RDN Coloquei esta questão como uma curiosidade, não tenho uma aplicação prática em mente.
Ambroz Bizjak

Respostas:

6

Aqui está uma elaboração da sua abordagem. A cada iteração, usamos o algoritmo FFT para calcular m valores da convolução no tempo O ( n log n ) , assumindo que os valores m subsequentes sejam zero. Em outras palavras, estamos computando n - 1 i = 0 w i a t - i + k ,mmO(nlogn)m onde w i são os n pesos (ou os pesos reversos), a i é a sequência de entrada, t é o tempo atual e a t ' =

i=0n1wiati+k,0km1,
winait para t " > t .at=0t>t

Para cada um dos seguintes iterações, que são capazes de calcular a convolução necessário em tempo O ( m ) (o i th iteração precisa de tempo S ( i ) ). Portanto, o tempo amortizado é O ( m ) + O ( n log n / m ) . Isso é minimizado escolhendo m = mO(m)iO(i)O(m)+O(nlogn/m) , que fornece um tempo de execução amortizado deO(m=nlogn.O(nlogn)

Podemos melhorar isso para o pior caso de tempo de execução de dividindo o cálculo em partes. Fixm, e definir b T , P , o = m - 1 Σ i = 0 W p m + i uma T m - i + o ,O(nlogn)m Cada C T , p depende apenas de 2 m de entradas, portanto pode ser calculada no tempo O ( m log m ) . Além disso, dado C t / m - p , p para 0 p n

bT,p,o=i=0m1wpm+iaTmi+o,CT,p=bT,p,0,,bT,p,m1.
CT,p2mO(mlogm)Ct/mp,p , podemos calcular a convolução no tempo O ( n / m + m ) . Portanto, o plano é manter a lista C t / m - p , p ,0pn/m1O(n/m+m) Para cada período de m entradas, precisamos atualizar n / m delas. Cada atualização leva tempo O ( m log m ) ; portanto, se espalharmos essas atualizações uniformemente, cada entrada ocupará o trabalho O ( ( n / m 2 ) m log m ) = O ( ( n / m ) log m )
Ct/mp,p,0pn/m1.
mn/mO(mlogm)O((n/m2)mlogm)=O((n/m)logm) . Juntamente com o cálculo da própria convolução, a complexidade do tempo por entrada é O((n/m)logm+m)m=nlognO(nlogn)
Yuval Filmus
fonte
Solução maravilhosa, obrigado, eu não tinha muita certeza se isso poderia ser feito.
precisa saber é o seguinte
E funciona! Implementação C: ideone.com/opuoMj
Ambroz Bizjak
Meh, estava faltando o último trecho de código que na verdade faz com que o cálculo seja quebrado, corrigido aqui ideone.com/GRXMAZ .
Ambroz Bizjak
Na minha máquina, esse algoritmo começa a ser mais rápido que o algoritmo simples, com cerca de 17.000 pesos. Para um pequeno número de pesos, é lento. Referência: ideone.com/b7erxu
Ambroz Bizjak 21/03
Muito impressionante que você realmente implementou isso! Você provavelmente deseja otimizarm. A escolham=nregistroné apenas um guia aproximado e pode não ser o ideal. Você tentou executar o algoritmo com diferentes valores dem?
Yuval Filmus 22/03