algorithm - 昂贵的滚动窗产品的有效总和

Question

给定 i = 0 到 N-1 的数字序列 a[i]，我试图计算以下总和:

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)))