algorithm - 高效组合昂贵的卷帘窗产品

给定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

然而，我关心的是标准浮点表示中除法的数值稳定性。
我想知道是否有一种稳定、快速的方法来计算这个和。对我来说，这是一项基本的数字任务，但目前我还不知道如何有效地完成它。
谢谢你的意见！

最佳答案

是的，如果你仔细计算反偏积，你不需要除法。

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