Gewichtete Summe der letzten N Zahlen

Question

Angenommen, wir empfangen Zahlen in einem Stream.Nachdem jede Zahl empfangen wurde, muss eine gewichtete Summe der letzten $N$ Zahlen berechnet werden, wobei die Gewichte immer gleich, aber willkürlich sind.

Wie effizient kann dies geschehen, wenn wir eine Datenstruktur beibehalten dürfen, die bei der Berechnung hilft?Können wir es besser machen als $ heta(N)$, d.h.Die Summe jedes Mal neu berechnen, wenn eine Zahl empfangen wird?

Zum Beispiel:Angenommen, die Gewichte sind $W= \langle w_1, w_2, w_3, w_4 angle$.An einem Punkt haben wir die Liste der letzten $N$ Zahlen $L_1= \langle a, b, c, d angle>$ und die gewichtete Summe $S_1=w_1*a+w_2*b+w_3*c+w_4 *d$.

Wenn eine andere Zahl, $e$, empfangen wird, aktualisieren wir die Liste, um $L_2= \langle b,c,d,e angle$ zu erhalten, und wir müssen $S_2=w_1*b+w_2*c+w_3* berechnen. d+w_4*e$.

Überlegung zur Verwendung von FFTEin Spezialfall dieses Problems scheint durch den Einsatz der schnellen Fourier-Transformation effizient lösbar zu sein.Hier berechnen wir die gewogenen Summen $S$ in Vielfachen von $N$.Mit anderen Worten: Wir erhalten N-Zahlen und können erst dann die entsprechenden N-Gewichtssummen berechnen.Dazu benötigen wir $N-1$ vergangene Zahlen (für die bereits Summen berechnet wurden) und $N$ neue Zahlen, insgesamt also $2N-1$ Zahlen.

Wenn dieser Vektor der Eingabezahlen und der Gewichtsvektor $W$ die Koeffizienten der Polynome $P(x)$ und $Q(x)$ definieren, wobei die Koeffizienten in $Q$ umgekehrt sind, sehen wir, dass das Produkt $P(x ) imes Q(x)$ ist ein Polynom, dessen Koeffizienten vor $x^{N-1}$ bis zu $x^{2N-2}$ genau die gewichteten Summen sind, die wir suchen.Diese können mittels FFT in $ heta(N*\log (N))$ Zeit berechnet werden, was uns einen Durchschnitt von $Θ(\log (N))$ Zeit pro Eingabezahl ergibt.

Dies ist jedoch keine Lösung des genannten Problems, da es erforderlich ist, dass die gewichtete Summe effizient berechnet wird jede Sobald eine neue Nummer eintrifft, können wir die Berechnung nicht verzögern.

Answer 1

Hier finden Sie eine Ausarbeitung Ihres Ansatzes.Bei jeder $m$-Iteration verwenden wir den FFT-Algorithmus, um $m$-Werte der Faltung in der Zeit $O(n\log n)$ zu berechnen, unter der Annahme, dass die nachfolgenden $m$-Werte Null sind.Mit anderen Worten, wir berechnen $$ sum_ {i = 0}^{n-1} w_i a_ {t-i+k}, quad 0 leq k leq m-1, $$, wo $ w_i $ sind die $ n $ Gewichte (oder die umgekehrten Gewichte), $ a_i $ ist die Eingabesequenz, $ t $ ist die aktuelle Zeit und $ a_ {t '} = 0 $ für $ t'> t $.

Für jede der folgenden $m$-Iterationen können wir die erforderliche Faltung in der Zeit $O(m)$ berechnen (die $i$-te Iteration benötigt Zeit $O(i)$).Die amortisierte Zeit beträgt also $O(m) + O(n\log n/m)$.Dies wird durch die Wahl von $m = \sqrt{n\log n}$ minimiert, was eine amortisierte Laufzeit von $O(\sqrt{n\log n})$ ergibt.

Wir können dies auf die Laufzeit im ungünstigsten Fall von $O(\sqrt{n\log n})$ verbessern, indem wir die Berechnung in Teile aufteilen.Fix $ m $ und definiere $$ b_ {t, p, o} = 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}.$$ Jeweils $ c_ {t, p} $ hängt nur von $ 2 Millionen $ Inputs ab, sodass es rechtzeitig $ O (M log m) $ berechnet werden kann.Außerdem können wir bei gegebenem $C_{\lfloor t/m floor-p,p}$ für $0 \leq p \leq n/m-1$ die Faltung in der Zeit $O(n/m + m)$ berechnen .Der Plan besteht daher darin, die Liste $$ c _ { lfloor t/m rfloor-p, p}, quad 0 leq p leq n/m-1 zu verwalten.$$ Für jeden Zeitraum von M $ Inputs müssen wir $ N/M $ von diesen aktualisieren.Jede Aktualisierung benötigt Zeit $O(m\log m)$. Wenn wir diese Aktualisierungen also gleichmäßig verteilen, wird jede Eingabe Arbeit $O((n/m^2) m\log m) = O((n/m) in Anspruch nehmen ) \log m)$.Zusammen mit der Berechnung der Faltung selbst beträgt die Zeitkomplexität pro Eingabe $O((n/m)\log m + m)$.Wenn man wie zuvor $m = \sqrt{n\log n}$ wählt, erhält man $O(\sqrt{n\log n})$.