Listenverständnis für laufende Summe

Question

Ich möchte eine laufende Summe aus einer Liste von Zahlen erhalten.

Zu Demonstrationszwecken beginne ich mit einer fortlaufenden Liste von Zahlen mit 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)

ergibt

  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

Wie Sie sehen können, initialisiere ich eine leere Liste [] entonces append() in jeder Schleifeniteration. Gibt es einen eleganteren Weg zu diesem, wie eine Liste Verständnis?

Answer 1

Ich würde dafür eine Coroutine verwenden:

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 2

Dies ist ineffizient, da es jedes Mal von Anfang an gemacht wird, aber es ist möglich:

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

Answer 3

Sie suchen nach zwei Dingen: fold (reduce) und eine lustige Funktion, die eine Liste der Ergebnisse einer anderen Funktion enthält, die ich running genannt habe. Ich habe sowohl Versionen mit als auch ohne Anfangsparameter erstellt; in beiden Fällen müssen diese zu reduce mit einem Anfangsparameter [] gehen.

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)

Bei sehr großen Listen dauert dies aufgrund des +-Operators sehr lange. In einer funktionalen Sprache würde diese Listenkonstruktion, wenn sie korrekt ausgeführt wird, O(n) sein.

Hier sind die ersten Zeilen der Ausgabe:

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]