generate list of partially accumulated values

[Steven D'Aprano]

On Sun, 16 Sep 2007 09:56:04 +0000, cesco wrote:

> Hi,
> 
> I have the following list:
> l = [1, 2, 3, 4]
> and I'd like to obtain a list like the following: 
> l_partial_sum = [1, 3, 6, 10] 
> (that is [1, 1+2, 1+2+3, 1+2+3+4])
> 
> Is there a simple way to accomplish this?

Yes, use a loop. Put it into a function:

def partial_sums(L):
    if not L:
        return []
    ps = [None]*len(L)
    ps[0] = L[0]
    for i in xrange(1, len(L)):
        ps[i] = ps[i-1] + L[i]
    return ps

>>> l = [1, 2, 3, 4]
>>> partial_sums(l)
[1, 3, 6, 10]


Here's a one-liner that give the same result:

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


Which is better, the one-liner using a super-fast built-in function 
written in C, or the multi-line function using just slow Python code?

(Hint: I wouldn't be asking the question if the "obvious" answer was 
right.)

Measure, don't guess!

>>> import timeit
>>> 
>>> timeit.Timer("partial_sums(l)", 
... "from __main__ import partial_sums; l = range(1000)").timeit(1000)
1.3528358936309814
>>> timeit.Timer("[sum(l[0:i]) for i in xrange(len(l)+1)][1:]", 
... "l = range(1000)").timeit(1000)
41.276183843612671

The one-liner is thirty times slower than the function. Can you explain 
why?

(Hint: how many times does it add numbers? How many times does it copy 
parts of the list?)



-- 
Steven.