List comprehension for running total

Question

I want to get a running total from a list of numbers.

For demo purposes, I start with a sequential list of numbers using range

a = range(20)

runningTotal = []
for n in range(len(a)):
    new = runningTotal[n-1] + a[n] if n > 0 else a[n]
    runningTotal.append(new)

# This one is a syntax error
# runningTotal = [a[n] for n in range(len(a)) if n == 0 else runningTotal[n-1] + a[n]]

for i in zip(a, runningTotal):
    print "{0:>3}{1:>5}".format(*i)

yields

  0    0
  1    1
  2    3
  3    6
  4   10
  5   15
  6   21
  7   28
  8   36
  9   45
 10   55
 11   66
 12   78
 13   91
 14  105
 15  120
 16  136
 17  153
 18  171
 19  190

As you can see, I initialize an empty list [], then append() in each loop iteration. Is there a more elegant way to this, like a list comprehension?

Answer 1

I'm not sure about 'elegant', but I think the following is much simpler and more intuitive (at the cost of an extra variable):

a = range(20)

runningTotal = []

total = 0
for n in a:
  total += n
  runningTotal.append(total)

The functional way to do the same thing is:

a = range(20)
runningTotal = reduce(lambda x, y: x+[x[-1]+y], a, [0])[1:]

...but that's much less readable/maintainable, etc.

@Omnifarous suggests this should be improved to:

a = range(20)
runningTotal = reduce(lambda l, v: (l.append(l[-1] + v) or l), a, [0])

...but I still find that less immediately comprehensible than my initial suggestion.

Remember the words of Kernighan: "Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it."

Answer 2

A list comprehension has no good (clean, portable) way to refer to the very list it's building. One good and elegant approach might be to do the job in a generator:

def running_sum(a):
  tot = 0
  for item in a:
    tot += item
    yield tot

to get this as a list instead, of course, use list(running_sum(a)).

Answer 3

If you're able to use numpy (http://numpy.scipy.org/), there's a built-in function to do this: cumsum.

import numpy
tot = numpy.cumsum(a)

Answer 4

I would use a coroutine for this:

def runningTotal():
    accum = 0
    yield None
    while True:
        accum += yield accum

tot = runningTotal()
next(tot)
running_total = [tot.send(i) for i in xrange(N)]

Answer 5

This can be implemented in 2 lines in Python.

Using a default parameter eliminates the need to maintain an aux variable outside, and then we just do a map to the list.

def accumulate(x, l=[0]): l[0] += x; return l[0];
map(accumulate, range(20))

Answer 6

This is inefficient as it does it every time from beginning but possible it is:

a = range(20)
runtot=[sum(a[:i+1]) for i,item in enumerate(a)]
for line in zip(a,runtot):
    print line

Answer 7

You are looking for two things: fold (reduce) and a funny function that keeps a list of the results of another function, which I have called running. I made versions both with and without an initial parameter; either way these need to go to reduce with an initial [].

def last_or_default(list, default):
    if len(list) > 0:
        return list[-1]
    return default

def initial_or_apply(list, f, y):
    if list == []:
        return [y]
    return list + [f(list[-1], y)]

def running_initial(f, initial):
    return (lambda x, y: x + [f(last_or_default(x,initial), y)])

def running(f):
    return (lambda x, y: initial_or_apply(x, f, y))

totaler = lambda x, y: x + y
running_totaler = running(totaler)
running_running_totaler = running_initial(running_totaler, [])

data = range(0,20)
running_total = reduce(running_totaler, data, [])
running_running_total = reduce(running_running_totaler, data, [])

for i in zip(data, running_total, running_running_total):
    print "{0:>3}{1:>4}{2:>83}".format(*i)

These will take a long time on really large lists due to the + operator. In a functional language, if done correctly, this list construction would be O(n).

Here are the first few lines of output:

0   0                      [0]
1   1                   [0, 1]
2   3                [0, 1, 3]
3   6             [0, 1, 3, 6]
4  10         [0, 1, 3, 6, 10]
5  15     [0, 1, 3, 6, 10, 15]
6  21 [0, 1, 3, 6, 10, 15, 21]