sum over everything after each element in an array

Question

I have a numPy array e.g. arr = [1, 2, 3, 4] and I want to sum over the elements after each element resulting in s = [10, 9, 7, 4].

In a loop, that can be done as:

for i in range(arr.size):
    if i == 0:
        s[i] = np.sum(arr)
    else:
        s[i] = np.sum(arr[:-i])

Answer 1

You can use numpy's cumulative sum function for this. You need to reverse the original array first, and then reverse the result to get it in the order you want:

a = np.array([1,2,3,4])
np.flip(np.cumsum(np.flip(a)))  # array([10,  9,  7,  4], dtype=int32)

Alternatively use [::-1] to reverse:

np.cumsum(a[::-1])[::-1]

The answers to this question include a full discussion of different options for calculating a cumulative sum in python. itertools.accumulate seems a good option in Python 3.2 or newer.

Answer 2

You can use numpy's ufuncs and their accumulate function to get the desired output.

np.add.accumulate(arr[::-1])[::-1]

Answer 3

Here's a concise (albeit costly) way to do it:

arr = [1, 2, 3, 4] 
s   = np.sum(np.triu(arr),1)

Although it is a non-procedural (conceptual) approach using only matrix operators, it is by far the slowest solution.

I played around with the various solutions proposed here, and a few of my own to see which approach would be fastest. Here are the results:

subFromSum     0.06761518699999997  @Sarcoma
procedural     0.07242122200000001  @Alain T.
generator      0.08231979099999998  @Sarcoma
recursive      0.10890062199999995  @Alain T.
arraySum       0.1370264969999999   @JosepJoestar
listComp       0.13318894400000003  @student
iterAccumulate 0.14017220000000008  @Stuart (linked in comment)
funcReduce     0.1828948370000001   @Alain T.
npAccumulate   0.23582439700000002  @user2699  
npCumSum       0.60332129           @Suart
npSumTriu      1.951785406          @Alain T.

All the numpy functions come dead last on a small list.

The same test performed on a much larger array: [1,2,3,4]*100 (repeated 10000 times instead of 100000) gives different results reflecting the scalability of these solutions:

iterAccumulate 0.12888180999999932  @Stuart (linked in comment)
generator      0.24920542199999995  @Sarcoma
procedural     0.2719608119999999   @Alain T.
npCumSum       0.27731459299999983  @Suart
npAccumulate   0.30234721600000114  @user2699
subFromSum     0.339745362          @Sarcoma
funcReduce     1.845360363000001    @Alain T.
recursive      2.2268321760000003   @Alain T.
npSumTriu      3.234387397999999    @Alain T.
listComp       6.1435246800000005   @student
arraySum       6.342716752          @JosepJoestar

numpy starts to show its power on large arrays but still not the best for this type of problem. The itertools module (accumulate) seems to be the most scalable approach.

Here are the functions ...

from timeit import timeit

array = [1, 2, 3, 4] 

# Subtracting from sum :: @Sarcoma
# timeit: 0.6
def subFromSum(arr):
    total = sum(arr)
    result = []
    for value in arr:
        result.append(total)
        total -= value
    return result
print("subFromSum    ", timeit(lambda :subFromSum(array), number=100000))


# Procedure for-loop assigning list items
# timeit: 0.07
def procedural(arr): 
    result = arr.copy()
    total  = 0
    index  = len(arr)-1 
    for value in reversed(arr):
        total += value
        result[index] = total
        index -= 1
    return result
print("procedural    ", timeit(lambda :procedural(array), number=100000))

# generator :: @Sarcoma
# timeit: 0.08
def gen(a):
    r = 0
    for x in a:
        r += x
        yield r
def generator(arr):
    return [*gen(arr[::-1])][::-1]
print("generator     ", timeit(lambda : generator(array), number=100000))


# recursive concatenation
# timeit: 0.11
def recursive(arr,size=None):
    size = (size or len(arr))
    value = arr[size-1]
    if size == 1 : return [value]
    previous = recursive(arr,size-1)
    return previous + [value+previous[-1]]
print("recursive     ", timeit(lambda :recursive(array), number=100000))

# iterative array sum()  :: @JosepJoestar
# timeit: 0.14
def arraySum(arr):
    s = []
    for i in range(len(arr)):
        s.append(sum(arr[i:]))
    return s
print("arraySum      ", timeit(lambda : arraySum(array), number=100000))

# list comprehension :: @student
# timeit: 0.13
def listComp(arr):
    return [sum(arr[i:]) for i in range(len(arr))]
print("listComp      ", timeit(lambda : listComp(array), number=100000))

# accumulate() function form itertools
# timeit: 0.14
def iterAccumulate(arr): 
    from itertools import accumulate
    return list(accumulate(arr[::-1]))[::-1]
print("iterAccumulate", timeit(lambda : iterAccumulate(array), number=100000))

# assigning list items using functools' reduce() function
# timeit: 0.18
def funcReduce(arr):
    from functools import reduce
    return reduce(lambda a,v: a + [a[-1]-v], arr[1:], [sum(arr)])
print("funcReduce    ", timeit(lambda : funcReduce(array), number=100000))

# npAccumulate() function form numpy :: @ user2699
# timeit: 0.24
def mpAccumulate(arr):
    import numpy as np
    return np.add.accumulate(arr[::-1])[::-1]
print("npAccumulate  ", timeit(lambda : mpAccumulate(array), number=100000))

# numpy's cumsum() function
# timeit: 0.55
def npCumSum(arr): 
    from numpy import cumsum
    return cumsum(arr[::-1])[::-1]
print("npCumSum      ", timeit(lambda : npCumSum(array), number=100000))

# conceptual matrix operations (using numpy)
# timeit: 2.05
def npSumTriu(arr): 
    import numpy as np
    return np.sum(np.triu(arr),1)
print("npSumTriu     ", timeit(lambda : npSumTriu(array), number=100000))

Answer 4

Sum once, append the current total t to the result array r and deduct the current value a.

arr = [1, 2, 3, 4]

t = sum(arr)
r = []
for a in arr:
    r.append(t)
    t -= a

print r

It's not a Numpy array though, is that bit important?

Some other answers appear to sum the remainder of the on each iteration. Which seems inefficient to me.

As pointed out by @User2699 reversing the array and simply adding the numbers together is the most efficient way to accomplish this.

The fastest way I could find to do that is with a generator:

def gen(a):
    r = 0
    for x in a:
        r += x
        yield r


def reverse_sum_with_generator(arr):
    return [*gen(arr[::-1])][::-1]

Update

I found it interesting how much faster Numpy Arrays appeared to be with the Numpy based scripts. So I ran some further tests to see why that was.

What I realised is that I hadn't taken in to account the way the lists were being generated. Each method for creating the lists has a different amount of overhead which for the most part accounts for the difference in speeds. The standout exception being np.arange() which is much faster with Numpy based scripts.

Benchmarks: https://repl.it/repls/SumEachItemAfter

Benchmark Gist: https://gist.github.com/sarcoma/8fc4b87c3cf649d6ef9af92bffe5a771

Answer 5

I think that you mean after instead of before. To sum the elements after each element do the following:

s = []
for i in range(len(arr)):
    s.append(sum(arr[i:]))

Or you can also use the list comprehension notation to make it shorter and much more elegant:

s = [sum(arr[i:]) for i in range(len(arr))]

However, this may lead to bad performance when list is big enough. The best solution in terms of efficiency would be to iterate over the list backwards computing only the sum of the last element seen and the current one, as the last is the sum of all its previous ones:

s = list(arr) # Avoid copying reference if modify arr is not desired

# Iterate from last position - 1, until first position, descending
for i in range(len(arr) - 2, -1, -1):
    s[i] += s[i + 1]