Gewichtete Summe der letzten N Zahlen

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

Wie effizient kann dies durchgeführt werden, wenn wir eine Datenstruktur zur Unterstützung der Berechnung beibehalten dürfen? Können wir etwas Besseres tun als , dh die Summe jedes Mal neu berechnen, wenn eine Zahl empfangen wird? $\Theta(N)$

Beispiel: Angenommen, die Gewichte lauten . An einem Punkt haben wir die Liste der letzten Zahlen und die gewichtete Summe . $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$

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

Berücksichtigung der Verwendung von FFT Ein Sonderfall dieses Problems scheint durch die Verwendung der schnellen Fourier-Transformation effizient lösbar zu sein. Hier berechnen wir die gewogenen Summen ein Vielfaches von . Mit anderen Worten, wir erhalten Zahlen und können nur dann die entsprechenden gewogenen Summen berechnen . Dazu benötigen wir vergangene Zahlen (für die bereits Summen berechnet wurden) und neue Zahlen, insgesamt Zahlen. $S$ $N$ $N$ $N$ $N-1$ $N$ $2N-1$

Wenn dieser Vektor von Eingangszahlen und der Gewichtsvektor die Koeffizienten der Polynome und , wobei die Koeffizienten in umgekehrt sind, sehen wir, dass das Produkt ist Polynom, dessen Koeffizienten vor bis zu genau die gewichteten Summen sind, die wir suchen. Diese können mithilfe der FFT in berechnet werden. Dies ergibt einen Durchschnitt von average Zeit pro eingegebener Zahl. $W$ $P(x)$ $Q(x)$ $Q$ $P(x)\times Q(x)$ $x^{N-1}$ $x^{2N-2}$ $\Theta(N*\log (N))$ $Θ(\log (N))$

Dies ist jedoch keine Lösung für das angegebene Problem, da es erforderlich ist, dass die gewichtete Summe bei jedem Empfang einer neuen Zahl effizient berechnet wird - wir können die Berechnung nicht verzögern.

algorithms data-structures online-algorithms Ambroz Bizjak
quelle

Beachten Sie, dass Sie hier LaTeX verwenden können .

Raphael

Kommen die Eingaben von einer bekannten Distribution? Haben sie nützliche mathematische Eigenschaften? Wenn dies nicht der Fall ist, ist es unwahrscheinlich, dass dies möglich ist (es sei denn, jemand kann eine ordentliche geschlossene Form finden, die sublinear berechenbar ist - ich kann sicherlich keine finden). Sind auch Annäherungen in Ordnung? Das könnte ein Weg sein, wenn es für Sie überhaupt nützlich ist.

RDN

FIR-Filter tun dies, damit ihr Design relevant ist.

adrianN

@RDN Ich habe diese Frage aus Neugier gestellt und habe keine praktische Anwendung im Sinn.

Ambroz Bizjak

Antworten:

Hier ist eine Ausarbeitung Ihres Ansatzes. Alle Iterationen verwenden wir den FFT - Algorithmus zur Berechnung - Werte der Faltung in der Zeit , unter der Annahme , dass die nachfolgenden Werte sind Null. Mit anderen Worten, wir berechnen wobei die Gewichte sind (oder die umgekehrten Gewichte), ist die Eingabesequenz, ist die aktuelle Zeit und für . $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$

Für jede der folgenden Iterationen, wir sind in der Lage die erforderliche Faltung in der Zeit zu berechnen (der - ten Iteration benötigt Zeit ). Die amortisierte Zeit ist also . Dies wird durch Auswahl von minimiert , was eine amortisierte Laufzeit von ergibt . $m$ $O(m)$ $i$ $O(i)$ $O(m) + O(n\log n/m)$ $m = \sqrt{n\log n}$ $O(\sqrt{n\log n})$

Wir können dies auf die Worst-Case-Laufzeit von verbessern, indem wir die Berechnung in Teile zerlegen. Fixiere und definiere Jedes hängt nur von Eingaben ab, sodass es in der Zeit berechnet werden kann . Wenn für , können wir auch die Faltung in der Zeit berechnen . Es ist daher geplant, die Liste Für jeden Zeitraum von $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$ Eingänge müssen wir von diesen aktualisieren . Jede Aktualisierung benötigt Zeit . Wenn wir diese Aktualisierungen also gleichmäßig verteilen, nimmt jede Eingabe Arbeit auf. . Zusammen mit der Berechnung der Faltung selbst beträgt die Zeitkomplexität pro Eingabe . Wenn Sie wie zuvor wählen, erhalten Sie .

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
quelle

Wunderbare Lösung, danke, ich war mir nicht wirklich sicher, ob es geht.

Ambroz Bizjak

Und es funktioniert! C-Implementierung: ideone.com/opuoMj

Ambroz Bizjak

Meh, mir fehlte das letzte Stück Code, durch das die Berechnung tatsächlich unterbrochen wird . Dies wurde hier behoben : ideone.com/GRXMAZ .

Ambroz Bizjak

Auf meinem Computer ist dieser Algorithmus ab etwa 17000 Gewichten schneller als der einfache Algorithmus. Bei kleinen Gewichtsmengen ist es langsam. Benchmark: ideone.com/b7erxu

Ambroz Bizjak

Sehr beeindruckend, dass Sie dies tatsächlich umgesetzt haben! Sie möchten wahrscheinlich über optimieren . Die Auswahl von ist nur eine grobe Richtlinie und möglicherweise nicht optimal. Haben Sie versucht, den Algorithmus mit verschiedenen Werten von auszuführen?

m

$m$

m = \sqrt{n \log n}

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

m

$m$

Yuval Filmus