Elegant pythonic cumsum

Question

What would be an elegant and pythonic way to implement cumsum?
Alternatively - if there'a already a built-in way to do it, that would be even better of course...

cumsum as in http://docs.scipy.org/doc/numpy/reference/generated/numpy.cumsum.html ? — , Feb 13 '12 at 10:06
http://docs.python.org/dev/library/itertools.html#itertools.accumulate — ChessMaster, Feb 13 '12 at 10:20

score 47 · Accepted Answer · edited Feb 17 '16 at 08:50

47

It's available in Numpy:

>>> import numpy as np
>>> np.cumsum([1,2,3,4,5])
array([ 1,  3,  6, 10, 15])

Or use itertools.accumulate since Python 3.2:

>>> from itertools import accumulate
>>> list(accumulate([1,2,3,4,5]))
[ 1,  3,  6, 10, 15]

If Numpy is not an option, a generator loop would be the most elegant solution I can think of:

def cumsum(it):
    total = 0
    for x in it:
        total += x
        yield total

Ex.

>>> list(cumsum([1,2,3,4,5]))
>>> [1, 3, 6, 10, 15]

edited Feb 17 '16 at 08:50

ankostis

8,579
3
47
61

answered Feb 13 '12 at 10:06

Fred Foo

355,277
75
744
836

Please share each algorithm run complexity – Noa Yehezkel Jun 16 '20 at 10:38

score 6 · Answer 2 · answered Feb 25 '13 at 00:00

My idea was to use reduce in a functional manner:

from operator import iadd
reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), [1, 2, 3, 4, 5], [0])[1:]
>>> [1, 3, 6, 10, 15]

iadd from the operator module has the unique property of doing an in-place addition and returning the destination as a result.

If that [1:] copy makes you cringe, you could likewise do:

from operator import iadd
reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm),
       [1, 2, 3, 4, 5], ([], 0))[0]
>>> [1, 3, 6, 10, 15]

But I discovered that locally the first example is much faster and IMO generators are more pythonic than functional programming like 'reduce':

reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm), values_ten, ([], 0))[0]
Average: 6.4593828736e-06
reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm), values_mil, ([], 0))[0]
Average: 0.727404361961
reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), values_ten, [0])[1:]
Average: 5.16271911336e-06
reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), values_mil, [0])[1:]
Average: 0.524223491301
cumsum_rking(values_ten)
Average: 1.9828751369e-06
cumsum_rking(values_mil)
Average: 0.234241141632
list(cumsum_larsmans(values_ten))
Average: 2.02786211569e-06
list(cumsum_larsmans(values_mil))
Average: 0.201473119335

Here's the benchmark script, YMMV:

from timeit import timeit

def bmark(prog, setup, number):
    duration = timeit(prog, setup=setup, number=number)
    print prog
    print 'Average:', duration / number

values_ten = list(xrange(10))
values_mil = list(xrange(1000000))

from operator import iadd

bmark('reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm), \
values_ten, ([], 0))[0]',
      setup='from __main__ import iadd, values_ten', number=1000000)
bmark('reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm), \
values_mil, ([], 0))[0]',
      setup='from __main__ import iadd, values_mil', number=10)

bmark('reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), \
values_ten, [0])[1:]',
      setup='from __main__ import iadd, values_ten', number=1000000)
bmark('reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), \
values_mil, [0])[1:]',
      setup='from __main__ import iadd, values_mil', number=10)

def cumsum_rking(iterable):
    values = list(iterable)
    for pos in xrange(1, len(values)):
        values[pos] += values[pos - 1]
    return values

bmark('cumsum_rking(values_ten)',
      setup='from __main__ import cumsum_rking, values_ten', number=1000000)
bmark('cumsum_rking(values_mil)',
      setup='from __main__ import cumsum_rking, values_mil', number=10)

def cumsum_larsmans(iterable):
    total = 0
    for value in iterable:
        total += value
        yield total

bmark('list(cumsum_larsmans(values_ten))',
      setup='from __main__ import cumsum_larsmans, values_ten', number=1000000)
bmark('list(cumsum_larsmans(values_mil))',
      setup='from __main__ import cumsum_larsmans, values_mil', number=10)

And here's my Python version string:

Python 2.7 (r27:82525, Jul  4 2010, 09:01:59) [MSC v.1500 32 bit (Intel)] on win32

Xavier Guihot · Answer 3 · 2019-04-27T19:32:30.627

Starting Python 3.8, and the introduction of assignment expressions (PEP 572) (:= operator), we can use and increment a variable within a list comprehension:

total = 0
[total := total + x for x in [1, 2, 3 ,4, 5]]
# [1, 3, 6, 10, 15]

This:

Initializes a variable total to 0 which symbolizes the cumulative sum
For each item, this both:
- increments total with the current looped item (total := total + x) via an assignment expression
- and at the same time, maps x to the new value of total

P2bM · Answer 4 · 2012-02-13T18:28:47.257

4

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

# Using list comprehention
cumsum = [sum(a[:i+1]) for i in range(len(a))]           # [1, 3, 6, 10, 15]

# Using map()
cumsum = map(lambda i:  sum(a[:i+1]), range(len(a)))     # [1, 3, 6, 10, 15]

edited Feb 13 '12 at 18:28

answered Feb 13 '12 at 17:44

P2bM

1,038
6
9

7

While this is nice and easy, be warned that on a large list this will be very slow! :) – Rusty Rob Feb 14 '12 at 07:32

score 3 · Answer 5 · answered Dec 15 '14 at 23:47

3

def cumsum(a):
     return map(lambda x: sum( a[0:x+1] ), range( 0, len(a) ))

cumsum([1,2,3])

> [1, 3, 6]

answered Dec 15 '14 at 23:47

user2437016

158
1
3

score 2 · Answer 6 · answered Feb 13 '12 at 10:20

2

in place:

a=[1,2,3,4,5]
def cumsum(a):
    for i in range(1,len(a)):
        a[i]+=a[i-1]

cumsum(a)
print a
"[1, 3, 6, 10, 15]"

answered Feb 13 '12 at 10:20

Rusty Rob

16,489
8
100
116

score 1 · Answer 7 · answered Feb 13 '12 at 10:09

1

for loops are pythonic

def cumsum(vec):
    r = [vec[0]]
    for val in vec[1:]:
        r.append(r[-1] + val)
    return r

answered Feb 13 '12 at 10:09

Simon Bergot

10,378
7
39
55

score 1 · Answer 8 · answered Feb 13 '12 at 10:15

1

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

def cumsum(a):
    a=iter(a)
    cc=[next(a)]
    for i in a:
        cc.append(cc[-1]+i)
    return cc

print cumsum(a)
"[1, 3, 6, 10, 15]"

answered Feb 13 '12 at 10:15

Rusty Rob

16,489
8
100
116

score 1 · Answer 9 · answered Feb 13 '12 at 10:21

1

a=[1,2,3,4,5]
def cumsum(a):
    b=a[:]
    for i in range(1,len(a)):
        b[i]+=b[i-1]
    return b

print cumsum(a)
"[1, 3, 6, 10, 15]"

answered Feb 13 '12 at 10:21

Rusty Rob

16,489
8
100
116

score 0 · Answer 10 · answered Nov 17 '18 at 18:01

I have updated @GrantJ 's answer and have timed everything with Python 3 in Jupyter. I have added in the following simple accumulate example:

def cumsum_acc(iterable):
    return accumulate(iterable)

The timings show that this approach is the fastest:

reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm), values_ten, ([], 0))[0]
Average: 4.18553415873987e-06
reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm), values_mil, ([], 0))[0]
Average: 0.4559302114011018
reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), values_ten, [0])[1:]
Average: 3.3726942356950078e-06
reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), values_mil, [0])[1:]
Average: 0.4217967894903154
cumsum_rking(values_ten)
Average: 2.2734952410773416e-06
cumsum_rking(values_mil)
Average: 0.24106813411868303
list(cumsum_larsmans(values_ten))
Average: 1.5819200433296032e-06
list(cumsum_larsmans(values_mil))
Average: 0.17061943569953542
list(cumsum_acc(values_ten))
Average: 9.456979988264607e-07
list(cumsum_acc(values_mil))
Average: 0.11057746014014924

The code behind it (by GrantJ, modified for Python 3):

from timeit import timeit
from itertools import accumulate
from functools import reduce

def bmark(prog, setup, number):
    duration = timeit(prog, setup=setup, number=number)
    print(prog)
    print('Average:', duration / number)

values_ten = list(range(10))
values_mil = list(range(1000000))

from operator import iadd

bmark('reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm), \
values_ten, ([], 0))[0]',
      setup='from __main__ import iadd, reduce, values_ten', number=1000000)
bmark('reduce(lambda acc, itm: (iadd(acc[0], [acc[1] + itm]), acc[1] + itm), \
values_mil, ([], 0))[0]',
      setup='from __main__ import iadd, reduce, values_mil', number=10)

bmark('reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), \
values_ten, [0])[1:]',
      setup='from __main__ import iadd, reduce, values_ten', number=1000000)
bmark('reduce(lambda acc, itm: iadd(acc, [acc[-1] + itm]), \
values_mil, [0])[1:]',
      setup='from __main__ import iadd, reduce, values_mil', number=10)

def cumsum_rking(iterable):
    values = list(iterable)
    for pos in range(1, len(values)):
        values[pos] += values[pos - 1]
    return values

bmark('cumsum_rking(values_ten)',
      setup='from __main__ import cumsum_rking, values_ten', number=1000000)
bmark('cumsum_rking(values_mil)',
      setup='from __main__ import cumsum_rking, values_mil', number=10)

def cumsum_larsmans(iterable):
    total = 0
    for value in iterable:
        total += value
        yield total

bmark('list(cumsum_larsmans(values_ten))',
      setup='from __main__ import cumsum_larsmans, values_ten', number=1000000)
bmark('list(cumsum_larsmans(values_mil))',
      setup='from __main__ import cumsum_larsmans, values_mil', number=10)

def cumsum_acc(iterable):
    return accumulate(iterable)

bmark('list(cumsum_acc(values_ten))',
      setup='from __main__ import cumsum_acc, accumulate, values_ten', number=1000000)
bmark('list(cumsum_acc(values_mil))',
      setup='from __main__ import cumsum_acc, accumulate, values_mil', number=10)

Elegant pythonic cumsum

10 Answers10

Linked