高效的轧制窗产品的总和

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