Ważona suma ostatnich N liczb

Załóżmy, że otrzymujemy liczby w strumieniu. Po otrzymaniu każdej liczby należy obliczyć ważoną sumę ostatnich liczb, przy czym wagi są zawsze takie same, ale dowolne. $N$

Jak skutecznie można to zrobić, jeśli pozwolimy zachować strukturę danych, która pomoże w obliczeniach? Czy możemy zrobić coś lepszego niż , tj. Przeliczać sumę za każdym razem, gdy liczba jest odbierana? $\Theta(N)$

Na przykład: Załóżmy, że wagi to . W pewnym momencie mamy listę ostatnich liczb i ważoną sumę . $W= \langle w_1, w_2, w_3, w_4\rangle$ $N$ $L_1= \langle a, b, c, d \rangle>$ $S_1=w_1*a+w_2*b+w_3*c+w_4*d$

Po otrzymaniu innej liczby, , aktualizujemy listę, aby uzyskać i musimy obliczyć . $e$ $L_2= \langle b,c,d,e\rangle$ $S_2=w_1*b+w_2*c+w_3*d+w_4*e$

Rozważanie przy użyciu FFT Szczególny przypadek tego problemu wydaje się być do rozwiązania w wyniku skutecznego zastosowania szybkiej transformacji Fouriera. Tutaj obliczania sumy ważonych wielokrotność . Innymi słowy, otrzymujemy liczb i tylko wtedy możemy obliczyć odpowiednie ważonych sum. Aby to zrobić, potrzebujemy przeszłych liczb (dla których sumy zostały już obliczone) i nowych liczb, łącznie liczb. $S$ $N$ $N$ $N$ $N-1$ $N$ $2N-1$

Jeśli ten wektor liczb wejściowych i wektor ciężaru określają współczynniki wielomianów i , przy współczynnikach w odwróconym , widzimy, że iloczyn jest a wielomian, którego współczynniki przed do są dokładnie ważonymi sumami, których szukamy. Można je obliczyć za pomocą FFT w czasie , co daje nam średni czas na liczbę wejściową. $W$ $P(x)$ $Q(x)$ $Q$ $P(x)\times Q(x)$ $x^{N-1}$ $x^{2N-2}$ $\Theta(N*\log (N))$ $Θ(\log (N))$

Nie jest to jednak rozwiązanie problemu, jak stwierdzono, ponieważ wymagane jest, aby suma ważona była obliczana wydajnie za każdym razem, gdy otrzymywana jest nowa liczba - nie możemy opóźniać obliczeń.

algorithms data-structures online-algorithms

— Ambroz Bizjak
źródło

Pamiętaj, że możesz używać LaTeX tutaj.

— Raphael

Czy dane wejściowe pochodzą z jakiejś znanej dystrybucji? Czy mają jakieś przydatne właściwości matematyczne? Jeśli nie, to jest mało prawdopodobne, że jest to możliwe (chyba że ktoś jest w stanie znaleźć zgrabną zamkniętą formę, która jest obliczeniem sublinearnym - z pewnością nie mogę jej znaleźć). Czy przybliżenia są w porządku? To może być jeden sposób, jeśli w ogóle ci się przyda.

— RDN

Robią to filtry FIR , więc ich konstrukcja będzie odpowiednia.

— adrianN

@RDN Zadałem to pytanie jako ciekawość, nie mam na myśli praktycznego zastosowania.

— Ambroz Bizjak

Oto opracowanie twojego podejścia. Każdy iteracji używamy algorytm do obliczania FFT wartości zwoju w czasie , przy założeniu, że kolejne wartości zero. Innymi słowy, gdzie są wagami (lub wagi odwrotne), jest sekwencją wprowadzania, jest bieżącym czasem, a dla . $m$ $m$ $O(n\log n)$ $m$

\sum_{i = 0}^{n - 1} w_{i} a_{t - i + k}, 0 \leq k \leq m - 1,

$\sum_{i=0}^{n-1} w_i a_{t-i+k}, \quad 0 \leq k \leq m-1,$

w_{i}

$w_i$

n

$n$

a_{i}

$a_i$

t

$t$

a_{t^{'}} = 0

$a_{t'} = 0$

t^{'} > t

$t' > t$

Dla każdego z poniższych iteracji, że są w stanie wyliczyć wymagane splot w czasie (The tą iterację potrzebuje czasu, ). Tak więc zamortyzowany czas wynosi . Można to zminimalizować, wybierając , co daje zamortyzowany czas działania . $m$ $O(m)$ $i$ $O(i)$ $O(m) + O(n\log n/m)$ $m = \sqrt{n\log n}$ $O(\sqrt{n\log n})$

Możemy to poprawić do najgorszego czasu działania , dzieląc obliczenia na części. Napraw i zdefiniuj Każde zależy tylko od wejść, więc można je obliczyć w czasie . Ponadto, biorąc pod uwagę dla , możemy obliczyć splot w czasie . Dlatego planuje się utrzymanie listy Dla każdego okresu $O(\sqrt{n\log n})$ $m$

b_{T, p, o} = \sum_{i = 0}^{m - 1} w_{p m + i} a_{T m - i + o}, C_{T, p} = b_{T, p, 0}, \dots, b_{T, p, m - 1} .

$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}.$

C_{T, p}

$C_{T,p}$

2 m

$2m$

O (m \log m)

$O(m\log m)$

C_{⌊ t / m ⌋ - p, p}

$C_{\lfloor t/m \rfloor-p,p}$

0 \leq p \leq n / m - 1

$0 \leq p \leq n/m-1$

O (n / m + m)

$O(n/m + m)$

C_{⌊ t / m ⌋ - p, p}, 0 \leq p \leq n / m - 1.

$C_{\lfloor t/m \rfloor-p,p}, \quad 0 \leq p \leq n/m-1.$

m

$m$ dane wejściowe, musimy zaktualizować z nich. Każda aktualizacja zajmuje czas , więc jeśli rozłożymy te aktualizacje równomiernie, każde wejście zajmie pracę . Wraz z obliczeniem samego splotu złożoność czasowa na wejście wynosi . Wybranie jak poprzednio, daje .

n / m

$n/m$

O (m \log m)

$O(m\log m)$

O ((n / m^{2}) m \log m) = O ((n / m) \log m)

$O((n/m^2) m\log m) = O((n/m) \log m)$

O ((n / m) \log m + m)

$O((n/m)\log m + m)$

m = \sqrt{n \log n}

$m = \sqrt{n\log n}$

O (\sqrt{n \log n})

$O(\sqrt{n\log n})$

— Yuval Filmus
źródło

Cudowne rozwiązanie, dzięki, nie byłem do końca pewien, czy da się to zrobić.

— Ambroz Bizjak

I to działa! Implementacja C: ideone.com/opuoMj

— Ambroz Bizjak

Meh, brakowało mi tego ostatniego fragmentu kodu, który faktycznie powoduje, że zrywa on obliczenia, naprawione tutaj ideone.com/GRXMAZ .

— Ambroz Bizjak

Na mojej maszynie ten algorytm zaczyna być szybszy niż prosty algorytm o wadze około 17000. W przypadku małej liczby ciężarków jest powolny. Benchmark: ideone.com/b7erxu

— Ambroz Bizjak

Bardzo imponujące, że faktycznie to zaimplementowałeś! Prawdopodobnie chcesz zoptymalizować ponad . Wybór jest jedynie orientacyjnym przewodnikiem i może nie być optymalny. Czy próbowałeś uruchomić algorytm z różnymi wartościami ?

m

$m$

m = \sqrt{n \log n}

$m = \sqrt{n\log n}$

m

$m$

— Yuval Filmus