python - Python 中的级数求和

Question

我有一个包含 5 000 000 个元素的一维矩阵 (A)，我想对这些数据进行一系列求和，以便结果(矩阵“B”)也是一个 5 000 000 个元素长的一维矩阵，其中每个元素 B[i] 是元素 A[i] 与 A[i] 之前的所有元素之和。

下面的代码是我到目前为止所拥有的。该代码并没有完全缩短它，因为执行系列中每个求和的运行时间随着求和次数(索引值)的增加而减少，直到进程最终在完成之前自行终止(即，在达到第 500 万个索引之前)。

有没有更有效的方法来总结这么长的系列？也许有一个 python 函数可以做到这一点吗？

import numpy as np
# Create the fake data:
A = np.arange(5000000)
B = np.zeros([5000000])
for i in np.arange(5000000):
    B[i] = np.sum(A[0:i])

Answer 1

您所描述的称为累积求和，NumPy 有一个内置函数:

B = np.cumsum(A)

如果您想自己编写它，则应该使用属性B[i] = B[i-1] + A[i]。也就是说，第 i 个总和等于第 (i-1) 个总和加上 i 个值 A:

B = np.zeros(5000000)
for i in xrange(1, 5000000):
    B[i] = B[i-1] + A[i]

这具有 O(n) 复杂度，而不是您问题中的算法的 O(n²) 复杂度。另请注意，我使用的是 xrange 而不是 np.arange。这在执行循环时效果更好，因为 xrange 一次生成一个整数，这意味着它比 np.arange 消耗更少的内存。