Fast Algorithm for partial sums on a list

Question

I have been learning Python for 2 months now. In order to hone my programming skills, I solve problems on Codewars from time to time.

Task

Codewars kata:

Write a program that takes a list of numbers as an argument and return a list of partial sums.

My Attempt

I wrote a solution that I tested and it works:

def parts_sums(ls):
    length=len(ls)+1
    def gen():
        for elt in range(0,length):
            yield sum(ls[elt:])   
    
    result= list(gen())
    return result

Codewars is rejecting this solution because it's too slow for lists with thousands of numbers.

I have spent an embarrassingly huge amount of time trying to come up with a faster solution with no avail.

How can the algorithm be designed more performant?

Answer 1

A solution with an explicit loop:

result= ls + [0]
for i in range(len(result)-1, 0, -1):
  result[i-1]= result[i] + result[i-1]

Note that it can also be done in-place in ls.

Answer 2

You don't have to compute the sum of a slice at each step, all you have to do is subtract one number from the previous sum.

Here's a pretty naive but straight forward solution, subject to further optimizations.

def part_sums(ls):
    result = [sum(ls)]
    for x in ls:
        result.append(result[-1] - x)
    return result

Answer 3

As commented by Yves Daoust, seems like a suffix sum array with additional zero-element (as sum over empty array).

Suffix Sum

Some notes on Suffix Sum:

Given an array ‘A’ of size N, its suffix sum array is an array of the same size N such that the ith element of the suffix sum array ‘Suffix’ is the sum of all elements of the given array till ith index from the end, i.e Suffix[i] = A[i] + A[i+1] + A[i+2] + … + A[N-1] - (0-Based indexing).

For Example: Given A[] = [3, 4, -1, 2, 5], the suffix sum array S[] is given as - S[0] = 13, S1 = 10, S1 = 6, S3 = 7, S[5] = 5.

i.e. S[] = [13, 10, 6, 7, 5]

See also:

1. Dev.to (2020): Prefix Sum & Suffix Sum - Programming Tools
2. Wikipedia: suffix array (might be related, not sure)

Implementation

Following approach uses these concepts for performance:

• predefined, fix-sized result array (instead of extending or list-comprehension)
• fix-sized loop for i (instead of recursion) to reverse increment
• explicit fast-returning if-branch for inputs with 0 or 1 elements

def suffix_sum(arr):
    result = arr + [0]   # add the zero as last element for this task (copied input)

    n = len(arr)
    if (n <= 1):  # input with 0 or 1 elements returned as is
        return result

    last = n-1  # the last of the input array stays unmodified 

    # iterate by element (last to first):
    for i in range(last, -1, -1):  # step backwards from last to first
        result[i] = result[i+1] + arr[i]   # result-sum = previous-sum + element (increases with each element)

    return result

Results for 3 test-cases:

in: [0, 1, 3, 6, 10]
out:[20, 20, 19, 16, 10, 0]
in: []
out:[0]
in: [1234]
out:[1234, 0]

Notes:

• The reverse-for-loop using a range as in Print a list in reverse order with range()?
• the first element is denoted by -1 as second range-argument

Debug-print each iteration with print(f"{i:2}: {result[i]} = {result[i+1]} + {arr[i]}") shows 4 iterations for example-input [0, 1, 3, 6, 10] with length n=5:

 3: 16 = 10 + 6
 2: 19 = 16 + 3
 1: 20 = 19 + 1
 0: 20 = 20 + 0

Answer 4

You could setup the resulting list starting with the total sum and progressively extend it reducing the last element by values in the original list:

ls = [1, 2, 3, 4, 5, 6]


r = [sum(ls)]
r.extend(r[-1]-n for n in ls)

print(r)
# [21, 20, 18, 15, 11, 6, 0]

Or, using itertools, accumulate the sum backwards and reverse the result:

from itertools import accumulate

r = [*accumulate([0]+ls[::-1])][::-1]

print(r)
# [21, 20, 18, 15, 11, 6, 0]