如何在列表中找到数字的累计和？

Question

time_interval = [4, 6, 12]

我想将数字相加，例如[4, 4+6, 4+6+12]，以获得列表t = [4, 10, 22]。

我尝试了以下方法：

t1 = time_interval[0]
t2 = time_interval[1] + t1
t3 = time_interval[2] + t2
print(t1, t2, t3)  # -> 4 10 22

- user2259323

---

请参见https://dev59.com/rWox5IYBdhLWcg3wWjHQ - hpaulj

Answer 1

如果你需要处理类似这样的数组并进行大量数值计算，我建议使用numpy，其中包含一个累计求和函数cumsum：

import numpy as np

a = [4,6,12]

np.cumsum(a)
#array([4, 10, 22])

Numpy在这种情况下通常比纯Python更快，相对于@Ashwini的accumu, 请参考：

In [136]: timeit list(accumu(range(1000)))
10000 loops, best of 3: 161 us per loop

In [137]: timeit list(accumu(xrange(1000)))
10000 loops, best of 3: 147 us per loop

In [138]: timeit np.cumsum(np.arange(1000))
100000 loops, best of 3: 10.1 us per loop

但是如果你只在一个地方使用numpy，可能没有必要依赖它。

- askewchan

---

这应该有一个以列表开头的 np.cumsum 情况，以考虑转换时间。 - hpaulj

@hpaulj 的观点很好，对于那些从（或目标是）一个“列表”开始的人，我不建议使用 numpy。 - askewchan

我认为numpy并不是最快的。https://dev59.com/r2Uo5IYBdhLWcg3woAqu#39534850 - Chris_Rands

同意，正如我之前提到的。避免出现像你和@hpaulj这样的反应，这就是为什么我在回答的第一行和最后一行中试图限制其范围的原因 :-/ - askewchan

@alex：使用timeit，“如果未给出-n，则通过尝试连续的10的幂次来计算适当数量的循环，直到总时间至少为0.2秒。”如果您希望有所不同，可以提供-n 1000使它们都等效。 - askewchan

Answer 2

在Python 2中，您可以像这样定义自己的生成器函数：

def accumu(lis):
    total = 0
    for x in lis:
        total += x
        yield total

In [4]: list(accumu([4,6,12]))
Out[4]: [4, 10, 22]

在Python 3.2以上版本中，您可以使用itertools.accumulate()函数：

In [1]: lis = [4,6,12]

In [2]: from itertools import accumulate

In [3]: list(accumulate(lis))
Out[3]: [4, 10, 22]

- Ashwini Chaudhary

---

“PEP 572 -- 赋值表达式”（预计于 Python 3.8 中推出）提供了一个有趣的替代方案 total = 0; partial_sums = [total := total + v for v in values]。然而，我仍然认为 accumulate 更快。 - Steven Rumbalski

@StevenRumbalski，我个人认为这是有史以来最糟糕的PEP。够糟糕的了... - Ashwini Chaudhary

@AshwiniChaudhary：这个例子可能让PEP看起来比它实际上更糟糕。它有一些非常易读和非常有用的应用。例如，if (value := some_dict.get(key)) is not None: ... 可以避免臭名昭著的双重查找。或者在带有 if 过滤器的列表推导中，像 [func_result for x in xs if satisfies_property(func_result := f(x))]，这也避免了函数 f(x) 的臭名昭著的双重评估。 - bluenote10

Answer 3

尝试使用itertools.accumulate()函数。

import itertools  

list(itertools.accumulate([1,2,3,4,5]))
# [1, 3, 6, 10, 15]

- Vani S

---

你不需要传递 operator.add，因为默认的操作是加法。 - Eugene Yarmash

Answer 4

我使用Python 3.4对排名前两名的答案进行了基准测试，我发现在许多情况下，itertools.accumulate比numpy.cumsum快得多，往往要快得多。然而，正如您从评论中所看到的，这并非总是如此，并且难以全面地探索所有选项。（如果您有其他有趣的基准测试结果，请随意添加评论或编辑此帖子。）

一些计时...

对于短列表，accumulate约快4倍：

from timeit import timeit

def sum1(l):
    from itertools import accumulate
    return list(accumulate(l))

def sum2(l):
    from numpy import cumsum
    return list(cumsum(l))

l = [1, 2, 3, 4, 5]

timeit(lambda: sum1(l), number=100000)
# 0.4243644131347537
timeit(lambda: sum2(l), number=100000)
# 1.7077815784141421

对于更长的列表，accumulate 的速度大约快3倍：

l = [1, 2, 3, 4, 5]*1000
timeit(lambda: sum1(l), number=100000)
# 19.174508565105498
timeit(lambda: sum2(l), number=100000)
# 61.871223849244416

如果未将NumPy数组转换为列表，使用accumulate函数仍然比使用其它方式快大约2倍：

from timeit import timeit

def sum1(l):
    from itertools import accumulate
    return list(accumulate(l))

def sum2(l):
    from numpy import cumsum
    return cumsum(l)

l = [1, 2, 3, 4, 5]*1000

print(timeit(lambda: sum1(l), number=100000))
# 19.18597290944308
print(timeit(lambda: sum2(l), number=100000))
# 37.759664884768426

如果你把导入语句放在两个函数外面, 但仍然返回一个numpy array, accumulate 仍然快近2倍:

from timeit import timeit
from itertools import accumulate
from numpy import cumsum

def sum1(l):
    return list(accumulate(l))

def sum2(l):
    return cumsum(l)

l = [1, 2, 3, 4, 5]*1000

timeit(lambda: sum1(l), number=100000)
# 19.042188624851406
timeit(lambda: sum2(l), number=100000)
# 35.17324400227517

- Chris_Rands

---

如果考虑到购票和安全检查的时间，人们不会指望飞机比火车更快地穿越城市。同样，如果你不想接受返回一个 array 数组的话，你也不应该使用 numpy 来处理只有五个项目的列表 list 。如果这个列表真的很短，那么它们的运行时间无关紧要——依赖性和可读性肯定更重要。但是，对于包含大量统一数字数据类型的列表，使用 numpy 的数组会更加合适，通常会更快。 - askewchan

@askewchan，我不仅仅是针对短列表进行操作，而且OP的问题要求输出一个列表而不是numpy数组。也许您可以编辑您的答案，以便更清楚地说明每种用法的适用情况 :) - Chris_Rands

@askewchan 实际上，我已经编辑了我的答案，并进行了更详细的比较。除非我忽略了什么，否则我绝不认为numpy更快？ - Chris_Rands

哦，是的确实如此 :) 我不会说你忽略了什么，但是在没有考虑输入和输出的情况下进行比较很难。你的 sum2 函数中大部分时间可能都用在将 l 转换为数组上了。尝试分别计时 a = np.array(l) 和 np.cumsum(a)。然后尝试 a = np.tile(np.arange(1, 6), 1000) 和 l = [1,2,3,4,5]*1000。在执行其他数值处理（例如首次创建或加载 l）的程序中，你的工作数据可能已经在一个数组中，并且创建过程是一个恒定的成本。 - askewchan

@askewchan 我和你有同样的想法，因此我计时了 a = np.array(l)。对于长列表/数组，在不进行转换为列表的情况下，使用numpy数组作为输入的sum2在我的电脑上比sum1快5倍。 - Mantxu

请为每个实现添加运行时复杂度。 - Noa Yehezkel

Answer 5

看哪：

a = [4, 6, 12]
reduce(lambda c, x: c + [c[-1] + x], a, [0])[1:]

将输出（与预期相同）：

[4, 10, 22]

- wonder.mice

---

效率低下。重复执行 c + [c[-1] + x] 的总开销会随输入长度的平方级别增加。 - user2357112

reduce 对于一次性的累加求和很好用，但如果您正在进行大量对cumsum函数的调用，则生成器将有助于“预处理”您的 cumulative_sum 值，并且可以在每个后续调用中以 O(1) 的时间复杂度访问它们。 - Scott Skiles

Answer 6

赋值表达式（在Python 3.8中新增）提供了另一种解决这个问题的方法：

time_interval = [4, 6, 12]

total_time = 0
cum_time = [total_time := total_time + t for t in time_interval]

- Steven Rumbalski

Answer 7

你可以使用简单的 for 循环在线性时间内计算累积和列表：

def csum(lst):
    s = lst.copy()
    for i in range(1, len(s)):
        s[i] += s[i-1]
    return s

time_interval = [4, 6, 12]
print(csum(time_interval))  # [4, 10, 22]

标准库的itertools.accumulate可能是一个更快的选择（因为它是用C实现的）：

from itertools import accumulate
time_interval = [4, 6, 12]
print(list(accumulate(time_interval)))  # [4, 10, 22]

- Eugene Yarmash

Answer 8

自从Python 3.8开始使用赋值表达式，因此像这样的事情变得更容易实现了。

nums = list(range(1, 10))
print(f'array: {nums}')

v = 0
cumsum = [v := v + n for n in nums]
print(f'cumsum: {cumsum}')

生成

array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
cumsum: [1, 3, 6, 10, 15, 21, 28, 36, 45]

相同的技术可以应用于查找累积乘积、平均值等。

p = 1
cumprod = [p := p * n for n in nums]
print(f'cumprod: {cumprod}')

s = 0
c = 0
cumavg = [(s := s + n) / (c := c + 1) for n in nums]
print(f'cumavg: {cumavg}')

结果在

cumprod: [1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
cumavg: [1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0]

- Viacheslav Zhukov

Answer 9

这个问题的答案取决于列表的长度和性能，可能会有许多不同的答案。我能想到一个非常简单的方法，即使没有考虑性能影响：

a = [1, 2, 3, 4]
a = [sum(a[0:x]) for x in range(1, len(a)+1)]
print(a)

[1, 3, 6, 10]

使用列表推导式可以做到这一点，这可能会相当有效，只是在这里我将多次添加子数组，您可能可以改进它并使其更简单！

祝你好运！

- Aashish Chaubey

---

这种方法的时间复杂度为 O(n²)，因此仅在处理小型列表时才使用它有意义。 - Eugene Yarmash

Answer 10

如果您想在2.7中使用一种不需要numpy的pythonic方式，这是我做的方法。

l = [1,2,3,4]
_d={-1:0}
cumsum=[_d.setdefault(idx, _d[idx-1]+item) for idx,item in enumerate(l)]

现在让我们试一下，并将其与所有其他实现进行测试。

import timeit, sys
L=list(range(10000))
if sys.version_info >= (3, 0):
    reduce = functools.reduce
    xrange = range


def sum1(l):
    cumsum=[]
    total = 0
    for v in l:
        total += v
        cumsum.append(total)
    return cumsum


def sum2(l):
    import numpy as np
    return list(np.cumsum(l))

def sum3(l):
    return [sum(l[:i+1]) for i in xrange(len(l))]

def sum4(l):
    return reduce(lambda c, x: c + [c[-1] + x], l, [0])[1:]

def this_implementation(l):
    _d={-1:0}
    return [_d.setdefault(idx, _d[idx-1]+item) for idx,item in enumerate(l)]


# sanity check
sum1(L)==sum2(L)==sum3(L)==sum4(L)==this_implementation(L)
>>> True    

# PERFORMANCE TEST
timeit.timeit('sum1(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.001018061637878418

timeit.timeit('sum2(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.000829620361328125

timeit.timeit('sum3(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.4606760001182556 

timeit.timeit('sum4(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.18932826995849608

timeit.timeit('this_implementation(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.002348129749298096

- Cobry