Somme pondérée des derniers N nombres

19

Supposons que nous recevions des nombres dans un flux. Après la réception de chaque numéro, une somme pondérée des derniers chiffres doit être calculée, où les poids sont toujours les mêmes, mais arbitraires.N

Dans quelle mesure cela peut-il être fait efficacement si nous sommes autorisés à conserver une structure de données pour faciliter le calcul? Pouvons-nous faire mieux que , c'est-à-dire recalculer la somme chaque fois qu'un nombre est reçu?Θ(N)

Par exemple: supposons que les poids soient . À un moment donné, nous avons la liste des derniers N nombres L_1 = \ langle a, b, c, d \ rangle> , et la somme pondérée S_1 = w_1 * a + w_2 * b + w_3 * c + w_4 * d .N L 1 = a , b , c , d > S 1 = w 1 * a + w 2 * b + w 3 * c + w 4 * W=w1,w2,w3,w4NL1=a,b,c,d>S1=w1a+w2b+w3c+w4d

Lorsqu'un autre nombre, e , est reçu, nous mettons à jour la liste pour obtenir L2=b,c,d,e et nous devons calculer S2=w1b+w2c+w3d+w4e .

Considération à l'aide de la FFT Un cas spécial de ce problème semble être résolu efficacement en utilisant la transformée de Fourier rapide. Ici, on calcule les sommes pesaient S en multiples de N . En d'autres termes, nous recevons N nombres et ce n'est qu'alors que nous pouvons calculer les N sommes pondérées correspondantes . Pour ce faire, nous avons besoin de N1 nombres antérieurs (pour lesquels des sommes ont déjà été calculées) et N nouveaux nombres, au total 2N1 nombres.

Si ce vecteur de nombres d'entrée et le vecteur de poids W définissent les coefficients des polynômes P(x) et Q(x) , avec les coefficients dans Q inversés, on voit que le produit P(x)×Q(x) est un polynôme dont les coefficients devant xN1 jusqu'à x2N2 sont exactement les sommes pondérées recherchées. Ceux-ci peuvent être calculés en utilisant la FFT en temps Θ(Nlog(N)) , ce qui nous donne une moyenne de Θ(log(N)) temps par numéro d'entrée.

Ce n'est cependant pas une solution au problème comme indiqué, car il est nécessaire que la somme pondérée soit calculée efficacement à chaque fois qu'un nouveau numéro est reçu - nous ne pouvons pas retarder le calcul.

Ambroz Bizjak
la source
Notez que vous pouvez utiliser LaTeX ici.
Raphael
Les entrées proviennent-elles d'une distribution connue? Ont-ils des propriétés mathématiques utiles? S'ils ne le font pas, il est peu probable que cela soit possible (à moins que quelqu'un ne puisse trouver une forme fermée nette qui soit calculable par sublinéarité - je ne peux certainement pas en trouver une). De plus, les approximations sont-elles OK? C'est peut-être une façon de procéder si cela vous est utile.
RDN
Les filtres FIR font cela, donc leur conception sera pertinente.
adrianN
@RDN J'ai posé cette question par curiosité, je n'ai pas d'application pratique en tête.
Ambroz Bizjak

Réponses:

6

Voici une élaboration de votre approche. Toutes les itérations, nous utilisons l'algorithme FFT pour calculer valeurs de la convolution dans le temps , en supposant que les valeurs suivantes sont nulles. En d'autres termes, nous calculons où sont les poids (ou les poids inverses), est la séquence d'entrée, est l'heure actuelle et pour .mmm n - 1 i = 0 w i a t - i + k ,O(nlogn)m

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

Pour chacune des itérations suivantes, nous sommes capables de calculer la convolution requise en temps (la ème itération a besoin du temps ). Le temps amorti est donc . Ceci est minimisé en choisissant , ce qui donne un temps d'exécution amorti de .mO(m)iO(i)O(m)+O(nlogn/m)m=nlognO(nlogn)

Nous pouvons améliorer cela au temps d'exécution le plus défavorable de en divisant le calcul en parties. Fixe et définit Chaque ne dépend que de entrées, il peut donc être calculé dans le temps . Aussi, étant donné pour , nous pouvons calculer la convolution dans le temps . Le plan est donc de maintenir la liste Pour chaque période 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.
mentrées, nous devons mettre à jour de ceux-ci. Chaque mise à jour prend du temps , donc si nous répartissons ces mises à jour uniformément, chaque entrée prendra du travail . Avec le calcul de la convolution elle-même, la complexité temporelle par entrée est . En choisissant comme précédemment, cela donne .n/mO(mlogm)O((n/m2)mlogm)=O((n/m)logm)O((n/m)logm+m)m=nlognO(nlogn)
Yuval Filmus
la source
Merveilleuse solution, merci, je ne savais pas vraiment si cela pouvait être fait.
Ambroz Bizjak
Et il fonctionne! Implémentation
Ambroz Bizjak
Meh, il me manquait ce dernier morceau de code qui fait en fait casser le calcul, fixé ici ideone.com/GRXMAZ .
Ambroz Bizjak
Sur ma machine, cet algorithme commence à être plus rapide que l'algorithme simple à environ 17000 poids. Pour un petit nombre de poids, il est lent. Indice de référence: ideone.com/b7erxu
Ambroz Bizjak
Très impressionnant que vous ayez réellement implémenté cela! Vous souhaitez probablement optimiser sur . Le choix n'est qu'un guide approximatif et peut ne pas être optimal. Avez-vous essayé d'exécuter l'algorithme avec différentes valeurs de ? m = m mm=nlognm
Yuval Filmus