Эффективная сумма дорогих оконных изделий

Question

Учитывая последовательность чисел a [i] для i = 0 до N-1, я пытаюсь вычислить следующую сумму:

a[0] * a[1] * a[2] +
a[1] * a[2] * a[3] +
a[2] * a[3] * a[4] +
...
a[N-4] * a[N-3] * a[N-2] +
a[N-3] * a[N-2] * a[N-1]

Я хотел бы сделать размер G изумноженная группа (в приведенном выше примере 3) переменный параметр.Тогда результат может быть наивно получен с использованием простого алгоритма O (N * G), который может быть записан в псевдокоде так:

sum = 0
for i from 0 to (N-G-1):
  group_contribution = 1
  for j from 0 to (G-1):
    group_contribution *= a[i+j]
  sum += group_contribution

Однако для больших G очевидно, что этот алгоритм ужаснонеэффективно, особенно если предположить, что числа последовательности a [i] заранее не известны и требуют дорогостоящих вычислений во время выполнения.

По этой причине я рассмотрел использование следующего алгоритма сложности O (N + G), который повторяет значения последовательности a [i] путем вычисления скользящего произведения:

sum = 0
rolling_product = 1
for i from 0 to (G-1):
  rolling_product *= a[i]
sum += rolling_product
for i from G to (N-1):
  rolling_product /= a[i-G]
  rolling_product *= a[i]
  sum += rolling_product

Однако меня беспокоит численная стабильность деления в стандартном представлении с плавающей точкой.

Мне было бы интересно узнать, существует ли стабильный, более быстрый способ вычисления этой суммы.Для меня это похоже на простую числовую задачу, но в настоящее время я не знаю, как это сделать эффективно.

Спасибо за любые идеи!

Answer 1

Да, если вы тщательно вычислите обратные частичные произведения, вам не нужно делить.

def window_products(seq, g):
    lst = list(seq)
    reverse_products = lst[:]
    for i in range(len(lst) - 2, -1, -1):
        if i % g != len(lst) % g:
            reverse_products[i] *= reverse_products[i + 1]
    product = 1
    for i in range(len(lst) - g + 1):
        yield reverse_products[i] * product
        if i % g == len(lst) % g:
            product = 1
        else:
            product *= lst[i + g]


print(list(window_products(range(10), 1)))
print(list(window_products(range(10), 2)))
print(list(window_products(range(10), 3)))

Answer 2

В качестве преамбулы вы можете рассмотреть возможность выполнения некоторых тестовых случаев для обоих алгоритмов и сравнить результаты (например, как относительную ошибку).

Далее, если у вас есть дополнительная память и время, вотстабильный подход во времени и памяти ( N log ₂ G ).Он аналогичен подходу с постоянным временем и линейному пространству к задаче минимального диапазона задача.

Предварительные вычисления продуктов степеней двух

Пусть B [ i ] [ j ] будет произведением 2 ^j элементов a начиная с позиции i , поэтому

B [ i ] [ j ] = a [ i ] × a [ i + 1] × ... × a [я + 2 ^j - 1]

Нас интересует N log ₂ G значения в B , а именно значения для 0 ≤ j ≤ log ₂ G .Мы можем вычислить каждое из этих значений в O (1), так как

B [ i ] [ j ] = B [ i ] [ j - 1] × B [ i + 2 ^{j - 1} ] [ j - 1]

Вычисление суммы

Чтобы вычислить один член в сумме, мы разлагаем G на куски степени двух.Например, если G = 13, то первый член будет

a [0] × ... × a [12] = ( a [0] × ... × a [7]) × ( a [8] × ... × a [11])× a [12] = B [0] [3] × B [8] [2] × B [12][0]

Каждый из членов O ( N ) может быть вычислен за O (log ₂ G ), таким образом, общеесложность нахождения суммы составляет O ( N log ₂ G ).

Answer 3

Создайте новую последовательность b, где b [0] = a [0] * a [1] * a [2] * ... a [G-1] и т. Д.

Теперь у вас естьболее простая проблема, где для вычисления суммы значений b вы можете поддерживать общее значение, и каждый раз, когда вы добавляете значение, вычитаете b [0], добавляете новое значение и сдвигаете их все вниз на единицу (используя круговой буфер, чтобы ничего не двигалось).[Тип кода скользящего среднего скользящего окна]

Сохраните кэш последних значений G a [], и вычисление нового значения для добавления к концу - это всего лишь операции O (G), и вы только когда-либо вычисляете [я] один раз.

Answer 4

Ваш прокатный продукт - хорошая идея, но, как вы говорите, у него проблемы со стабильностью.Я бы исправил это следующим образом:

• Отдельно используйте аналогичную систему для отслеживания количества нулей и отрицательных чисел.Это целочисленные суммы, поэтому проблем со стабильностью нет.
• Вместо расчета скользящего продукта для всех a[i], рассчитайте скользящую сумму из log(abs(a[i])), исключая нули.Тогда, когда вам нужен продукт, это (num_zeros > 0 ? 0.0 : exp(log_sum)) * sign.Это позаботится о серьезной нестабильности.
• Пока вы генерируете выходные данные из вашего умного скользящего алгоритма log_sum, вы должны одновременно создавать fresh log_sum, из которого вы не вычличто-нибудь.Когда количество элементов в этой новой сумме достигнет G, перезапишите свой скользящий llog_sum с этим числом и обнулите его до нуля.Это удалит все ошибки округления, которые могут накапливаться в долгосрочной перспективе.