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.
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?
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 * ré
Lorsqu'un autre nombre, , est reçu, nous mettons à jour la liste pour obtenir et nous devons calculer .
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 en multiples de . En d'autres termes, nous recevons nombres et ce n'est qu'alors que nous pouvons calculer les sommes pondérées correspondantes . Pour ce faire, nous avons besoin de nombres antérieurs (pour lesquels des sommes ont déjà été calculées) et nouveaux nombres, au total nombres.
Si ce vecteur de nombres d'entrée et le vecteur de poids définissent les coefficients des polynômes et , avec les coefficients dans inversés, on voit que le produit est un polynôme dont les coefficients devant jusqu'à sont exactement les sommes pondérées recherchées. Ceux-ci peuvent être calculés en utilisant la FFT en temps , ce qui nous donne une moyenne de 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.
la source
Réponses:
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 .m m m n - 1 ∑ i = 0 w i a t - i + k ,O(nlogn) m
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 .m O(m) i O(i) O(m)+O(nlogn/m) m=nlogn−−−−−√ O(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
la source