Get the corresponding sums of parts of a list

Question

I have a list [0, 1, 2, 3, 4, 5, 6] and I sum its parts so that:

l = [0, 1, 2, 3, 4, 5, 6] -> 21

l = [1, 2, 3, 4, 5, 6] -> 21

l = [2, 3, 4, 5, 6] -> 20

l = [3, 4, 5, 6] -> 18

l = [4, 5, 6] -> 15

l = [5, 6] -> 11

l = [6] -> 6

l = [] -> 0

So, I get the corresponding sums of the list's parts: [21, 21, 20, 18, 15, 11, 6, 0]

The code I use is:

[sum(l[i:]) for i in range(len(l) + 1)]

But, for lists with range greater than 100000 the code slows down significantly.

Any idea why and how to optimize it?

you are reusing precomputed values. I suggest you use cumulative sum — WiseDev, Jun 18 '19 at 09:25
Each time you're calculating new sum - while the sums overlap. Count from the last element, either manually or using cumulative sum of the list.. — h4z3, Jun 18 '19 at 09:26
[`np.cumsum`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.cumsum.html). — meowgoesthedog, Jun 18 '19 at 09:27

score 8 · Answer 1 · answered Jun 18 '19 at 09:29

I would suggest itertools.accumulate for this (which i recall is faster than np.cumsum), with some list reversing to get your desired output:

>>> from itertools import accumulate
>>> lst = [0, 1, 2, 3, 4, 5, 6]
>>> list(accumulate(reversed(lst)))[::-1]
[21, 21, 20, 18, 15, 11, 6]

(you can trivially add 0 to the end if needed)

Arkistarvh Kltzuonstev · Accepted Answer · 2019-06-18T10:01:12.077

This might help to reduce calculation time for big lists :

l = [0, 1, 2, 3, 4, 5, 6]
output = list(np.cumsum(l[::-1]))[::-1]+[0]

Output :

[21, 21, 20, 18, 15, 11, 6, 0]

Here is one comparison over performance for four different methods, all of which does the same thing :

from timeit import timeit

def sum10(l):
    from itertools import accumulate
    return list(accumulate(reversed(l)))[::-1]+[0]

def sum11(l):
    from itertools import accumulate
    return list(accumulate(l[::-1]))[::-1]+[0]


def sum20(l):
    from numpy import cumsum
    return list(cumsum(l[::-1]))[::-1]+[0]

def sum21(l):
    from numpy import cumsum
    return list(cumsum(list(reversed(l))))[::-1]+[0]

l = list(range(1000000))
iter_0 = timeit(lambda: sum10(l), number=10)  #0.14102990700121154
iter_1 = timeit(lambda: sum11(l), number=10)  #0.1336850459993002
nump_0 = timeit(lambda: sum20(l), number=10)  #0.6019859320003889
nump_1 = timeit(lambda: sum21(l), number=10)  #0.3818727100006072

`+l[0]` is the wrong thing to do here i think they mean `+0` *always* even if the list does not start with `0` — Chris_Rands, Jun 18 '19 at 09:56
also, i can't replicate your timings at all on ipython https://pastebin.com/x3U1q0nZ — Chris_Rands, Jun 18 '19 at 09:57

Felipe Sulser · Answer 3 · 2019-06-18T09:30:12.480

1

There is no clean way of doing it with list comprehensions as far as I know.

This code will work without any other libraries:

def cumulative_sum(a):
  total= 0
  for item in a:
    total += item
    yield total

list(cumulative_sum(listname))

From Python 3.8 on, there is a new operator that might help:

[(x, total := total + x) for x in items]

edited Jun 18 '19 at 09:30

answered Jun 18 '19 at 09:29

Felipe Sulser

1,185
8
19

1

That's walrus operator ! – Arkistarvh Kltzuonstev Jun 18 '19 at 09:29

Get the corresponding sums of parts of a list

3 Answers3