Python中的系列求和

Question

我有一个5000个元素的一维矩阵(A)，我想对这些数据进行一系列的求和，使结果(矩阵"B")也是一个5000元素长的1D矩阵，其中每个元素Bi是元素Ai和Ai之前所有元素的总和。

下面的代码是我到目前为止所掌握的。该代码并没有完全减少它，因为该系列中每个求和的运行时间随着求和数(索引值)的减少而减少，直到进程在完成之前(即，在到达第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'th和与(i-1)'th和加上A的i'th和相同。

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

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

Answer 2

您可以利用这样一个事实，即B[i-1]是它前面所有数字的总和。这意味着下一个元素(B[i])就是B[i-1]+A[i]。这将节省迭代过程中通过A[0]到A[i]的迭代。

下面是一个可以这样做的函数：

def sumMatrix(A):
    #Define the return array, B, populated with 0
    B = [0]
    #Iterate through the provided array, A
    for number in A:
        #Set the next element to the sum of the last element in B
        #  and the next number in A
        B.append(B[-1] + number)
    #Return B, removing the 0 in the first element
    return B[1:]

#Call the function with the numbers from 1 to 5,000,000 and output
#  the result
print(sumMatrix(range(5000000)))

希望这会有所帮助:)