python - 高效的二维 cumsum

Question

假设我有一个这样的数组

>>> a = np.arange(1,8).reshape((1,-1))
>>> a
array([[1, 2, 3, 4, 5, 6, 7]])

并且我想为 a 中的每个项目创建“接下来的 4 个项目的总和”。也就是说，我的预期输出是

1,       2,      3, 4, 5, 6, 7, 8
1+2,     2+3,     ...
1+2+3    2+3+4    ...
1+2+3+4  2+3+4+5  ...

即包含的矩阵

1, 2, 3, 4, 5, 0, 0, 0
3, 5, 7, 9, 11,0, 0, 0
6, 9, 12,15,18,0, 0, 0
10,14,18,21,26,0, 0, 0

由于无法对最后 3 项正确执行 cumsum 操作，因此我希望那里有一个 0。我知道如何做一个 cumsum。事实上，数组是

a[:4].cumsum().reshape((-1,1)); a[1:5].cumsum().reshape((-1,1))...

水平堆叠。但是，我不知道如何以有效的方式执行此操作。这样做的好的矢量化 numpy 方法是什么？我也对 scipy 包持开放态度，只要它们在效率或可读性方面优于 numpy。

Answer 1

您可以使用称为 summed area table 的技术的更简单变体来高效地进行计算。 ，在图像处理应用中也称为积分图像。首先，您计算并存储求和面积表，这是第一行的完整累积总和，前面添加了 0:

a = np.arange(1, 8)
cs = np.concatenate(([0], np.cumsum(a)))

现在您可以将“下一个 n 项的总和”创建为 cs[:n] - cs[:-n]:

>>> for n in range(1, 5):
...     print n, '-->', (cs[n:] - cs[:-n])[:4]
...
1 --> [1 2 3 4]
2 --> [3 5 7 9]
3 --> [ 6  9 12 15]
4 --> [10 14 18 22]

您需要将它们正确地排列成您想要的形状，但是一旦完成原始计算，您就可以通过一次减法来计算输出的每一项，这几乎是最高效的。