CODEWITHSUNDEEP
pythonpython-3.xpython-2.7for-looplogic
Harry Daniels
Harry Daniels

Reputation: 580

"cumulative" subtraction of list elements in python

I'm writing a function which does the following:

for a given list: X, return a list of x[1] - x[0], x[2] - (x[1] - x[0]), x[3] - ( x[2] - (x[1] - x[0]) and so on.

I have a for loop which achieves this perfectly fine but was curious if there was a better way to do this? I'm conscience that my list X can be very large, so speed and efficiency is paramount.

test = [25, 30, 50, 60, 100, 1000, 100000]

diff = test[0]
output = []
for i in range(len(test) -1):
    x1 = test[i + 1] - diff
    output.append(x1)
    diff = x1

output

Thanks!

Upvotes: 0

Views: 494

Answers (2)

Andrej Kesely
Andrej Kesely

Reputation: 195468

There's minor speed-up with itertools.accumulate:

i = accumulate(test, lambda acc, v: v - acc)
next(i)
output = [*i]
print(output)

Prints:

[5, 45, 15, 85, 915, 99085]

Benchmark (using one million item list with ascending elements):

from random import randint
from itertools import accumulate

from timeit import timeit

test = sorted([randint(10, 100_000) for _ in range(1_000_000)])

def f1():
    diff = test[0]
    output = []
    for i in range(len(test) -1):
        x1 = test[i + 1] - diff
        output.append(x1)
        diff = x1

    return output


def f2():
    i = accumulate(test, lambda acc, v: v - acc)
    next(i)
    output = [*i]
    return output


t1 = timeit(lambda: f1(), number=1)
t2 = timeit(lambda: f2(), number=1)

print(t1)
print(t2)

Prints on my machime (AMD 2400G, Python 3.8):

0.23373416997492313
0.19420667097438127

Upvotes: 1

Dominic D
Dominic D

Reputation: 1808

Using numpy (hopefully that's ok):

output =  list(np.cumsum((-1) ** np.arange(len(test)) * test)[1:] * (-1) ** np.arange(1,len(test)))

It's probably better to split into a couple of lines:

r = (-1) ** np.arange(len(test))
output = list(np.cumsum(r * test)[1:] * r[1:])

From your definition of the outputs:

x[1]-x[0],
x[2] - (x[1]-x[0]) = x[2] - x[1] + x[0],
x[3] - (x[2]-(x[1]-x[0]) = x[3] - x[2] + x[1] - x[0]
...

So this just exploits the fact that you want the cumulative sum of the numbers in test, alternating in whether they are positive or negative.

Upvotes: 0

Related Questions