Взвешенная сумма последних n чисел

Question

Предположим, мы получаем цифры в потоке. После получения каждого числа необходимо рассчитать взвешенную сумму последних чисел $ N $, где веса всегда одинаковы, но произвольны.

Насколько эффективно это можно сделать, если нам разрешено сохранить структуру данных, чтобы помочь с вычислением? Можем ли мы сделать лучше, чем $ theta (n) $, т.е. перечисляя сумму каждый раз, когда получается число?

Например: предположим, что веса $ 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 $.

Когда получен другой номер, $ e $, мы обновляем список, чтобы получить $ l_2 = langle b, c, d, e rangle $, и нам нужно вычислить $ s_2 = w_1*b+w_2*c+w_3* D+W_4*E $.

Рассмотрение с использованием FFTОсобый случай этой проблемы, по -видимому, эффективно решается, используя быстрое преобразование Фурье. Здесь мы рассчитываем взвешенные суммы $ S $ в кратных $ N $. Другими словами, мы получаем числа $ N $, и только тогда мы можем вычислить соответствующие взвешенные суммы $ n $. Для этого нам нужны номера $ N-1 $ прошлых (для которых уже рассчитывались суммы) и новые номера $ N $, в общей сложности 2N-1 $ номера.

Если этот вектор входных чисел и вектор веса $ w $ определяет коэффициенты полиномов $ p (x) $ и $ q (x) $, с коэффициентами в $ q $ обратно, мы видим, что продукт $ p (x ) Times Q (x) $-это полином, чьи коэффициенты перед $ x^{n-1} $ до $ x^{2n-2} $-это именно то взвешенные суммы, которые мы ищем. Они могут быть рассчитаны с использованием FFT в $ theta (n* log (n)) $ времени, что дает нам в среднем $ θ ( log (n)) $ времени на входное число.

Это, однако, не решение проблемы, как указано, потому что требуется, чтобы взвешенная сумма была эффективно рассчитана каждый Время получено новое число - мы не можем отложить вычисление.

Answer 1

Вот разработка вашего подхода. Каждые итерации $ M $ мы используем алгоритм FFT для вычисления значений $ M $ в свертке во времени $ O (n log n) $, предполагая, что последующие значения $ m $ равны нулю. Другими словами, мы вычисляем $$ sum_ {i = 0}^{n-1} w_i a_ {t-i+k}, Quad 0 leq k leq m-1, $$, где $ w_i $ Являются ли веса $ n $ (или обратные веса), $ a_i $ - это последовательность ввода, $ t $ - это текущее время, а $ a_ {t '} = 0 $ для $ t'> t $.

Для каждой из следующих итераций $ M $ мы можем рассчитать необходимую свертку во времени $ O (M) $ ($ i $ th итерация требует времени $ O (i) $). Таким образом, амортизированное время - $ o (m) + o (n log n/m) $. Это сводится к минимуму путем выбора $ m = sqrt {n log n} $, что дает амортизированное время выполнения $ o ( sqrt {n log n}) $.

Мы можем улучшить это до худшего времени выполнения $ O ( sqrt {n log n}) $, разбив вычисление на части. Исправить $ m $, и определить $$ 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} $ зависит только от входов в $ 2M $, поэтому его можно рассчитать во времени $ O (M log M) $. Кроме того, учитывая $ c _ { lfloor t/m rfloor-p, p} $ за $ 0 leq p leq n/m-1 $, мы можем вычислить свертку во времени $ o (n/m + m) $ Анкет Таким образом, план состоит в том, чтобы поддерживать список $$ c _ { lfloor t/m rfloor-p, p}, Quad 0 leq p leq n/m-1. $$. Для каждого периода $ M $ входы нам необходимо обновить $ n/m $ их. Каждое обновление требует времени $ o (m log m) $, поэтому, если мы распределим эти обновления равномерно, каждый вход займет работу $ o ((n/m^2) m log m) = o ((N/M ) log m) $. Вместе с вычислением самой свертки, сложности времени на вход - $ O ((N/M) log M + M) $. Выбор $ m = sqrt {n log n} $ Как раньше, это дает $ o ( sqrt {n log n}) $.