somma ponderata degli ultimi numeri N

Question

Si supponga che stiamo ricevendo i numeri in un ruscello. A seguito della ricezione ogni numero, una somma ponderata degli ultimi $ N $ numeri deve essere calcolato, dove i pesi sono sempre le stesse, ma arbitrario.

Come efficiente può questo fatto, se c'è permesso di mantenere una struttura di dati per aiutare con il calcolo? Possiamo fare meglio di $ \ Theta (N) $, vale a dire ricalcolare la somma ogni volta che un numero viene ricevuto?

Ad esempio: Supponiamo che i pesi sono $ W = \ Langle W_1, w_2, w_3, w_4 \ rangle $. A un certo punto abbiamo la lista delle ultime $ N $ numeri $ L_1 = \ langle a, b, c, d \ rangle> $, e la somma ponderata $ S_1 = W_1 * a + w_2 * b + w_3 * c + w_4 * d $.

Quando si riceve un altro numero, $ e $, abbiamo aggiornare l'elenco per ottenere $ L_2 = \ Langle b, c, d, e \ rangle $ e abbiamo bisogno di calcolare $ S_2 = W_1 * b + w_2 * c + w_3 * d + w_4 * e $.

Considerazione tramite FFT Un caso particolare di questo problema sembra essere risolvibile in modo efficiente utilizzando Fast Fourier Transform. Qui, calcoliamo le somme pesate $ S $ in multipli di $ N $. In altre parole, noi riceviamo $ n $ numeri e solo allora possiamo calcolare il corrispondente $ N $ pesava somme. Per fare questo, abbiamo bisogno di $ N-1 $ passato numeri (per i quali sono già state calcolate le somme), e $ N $ nuovi numeri, in totale $ 2N-1 $ numeri.

Se questo vettore di numeri in ingresso e il vettore dei pesi $ W $ definiscono i coefficienti dei polinomi $ P (x) $ e $ Q (x) $, con coefficienti di $ Q $ invertita, vediamo che il prodotto $ P (x) \ times Q (x) $ è un polinomio i cui coefficienti di fronte a $ x ^ {N-1} $ fino a $ x ^ {2N-2} $ sono esattamente le somme ponderate che cerchiamo. Questi possono essere calcolate utilizzando FFT a $ \ Theta (N * \ log (N)) $ tempo, che ci dà una media di $ T (\ log (N)) $ volta al numero di ingresso.

Questa non è però una soluzione del problema come detto, perché è richiesto che la somma ponderata è calcolata in modo efficiente ogni Ora un nuovo numero ricevuto -. Non possiamo ritardare il calcolo

Answer 1

Ecco un'elaborazione del vostro approccio. Ogni $ m $ iterazioni, si usa l'algoritmo FFT per calcolare $ m $ valori della convoluzione nel tempo $ O (n \ log n) $, assumendo che le successive $ valori $ m sono pari a zero. In altre parole, stiamo calcolando $$ \ Sum_ {i = 0} ^ {n-1} w_i a_ {t-i + k}, \ quad 0 \ leq k \ leq m-1, $$ dove $ $ w_i sono i pesi $ n $ (o pesi inversa), $ a_i $ è la sequenza di input, $ t $ è il tempo attuale, e $ a_ {t '} = 0 $ per $ t'> t $ .

Per ciascuna delle seguenti $ m $ iterazioni, siamo in grado di calcolare la convoluzione richiesto nel tempo $ O (m) $ (il $ i $ esimo iterazione ha bisogno di tempo $ O (i) $). Quindi il tempo ammortizzato è di $ O (m) + O (n \ log n / m) $. Questo è ridotto al minimo scegliendo $ m = \ sqrt {\ n log n} $, che dà una ammortizzati tempo di $ in esecuzione O (\ sqrt {\ n log n}) $.

Possiamo migliorare questo caso peggiore tempo di $ O (\ sqrt {n \ log n}) $ esecuzione rompendo il calcolo in parti. Fissare $ m $, e definire $$ 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}. $$ Ogni $ C_ {T, p} $ dipende soltanto $ 2 milioni di ingressi $, in modo che possa essere calcolata in tempo $ O (m \ log m) $. Inoltre, data $ C _ {\ lfloor t / m \ rfloor-p, p} $ per $ 0 \ leq p \ leq n / m-1 $, possiamo calcolare la convoluzione nel tempo $ O (n / m + m) $ . Il piano è quindi quello di mantenere la lista $$ C _ {\ lfloor t / m \ rfloor-p, p}, \ quad 0 \ leq p \ leq n / m-1. $$ Per ogni periodo di $ M $ ingressi, abbiamo bisogno di aggiornare $ n / m $ di questi. Ogni aggiornamento richiede tempo $ O (m \ log m) $, quindi se abbiamo diffuso in modo uniforme questi aggiornamenti, ogni ingresso assumerà il lavoro $ O ((n / m ^ 2) m \ log m) = O ((n / m ) \ log m) $. Insieme con il calcolo della convoluzione stesso, la complessità temporale per ingresso è di $ O ((n / m) \ log m + m) $. Scegliendo $ m = \ sqrt {\ n log n} $ come prima, questo dà $ O (\ sqrt {\ n log n}) $.