¿Cómo encontrar la suma acumulativa de números en una lista?

92
time_interval = [4, 6, 12]

Quiero resumir los números como [4, 4+6, 4+6+12]para obtener la lista t = [4, 10, 22].

Intenté lo siguiente:

t1 = time_interval[0]
t2 = time_interval[1] + t1
t3 = time_interval[2] + t2
print(t1, t2, t3)  # -> 4 10 22
usuario2259323
fuente
Consulte también stackoverflow.com/q/9258602
hpaulj

Respuestas:

128

Si está haciendo mucho trabajo numérico con matrices como esta, sugeriría numpy, que viene con una función de suma acumulativa cumsum:

import numpy as np

a = [4,6,12]

np.cumsum(a)
#array([4, 10, 22])

Numpy es a menudo más rápido que Python puro para este tipo de cosas, vea en comparación con @ Ashwiniaccumu :

In [136]: timeit list(accumu(range(1000)))
10000 loops, best of 3: 161 us per loop

In [137]: timeit list(accumu(xrange(1000)))
10000 loops, best of 3: 147 us per loop

In [138]: timeit np.cumsum(np.arange(1000))
100000 loops, best of 3: 10.1 us per loop

Pero, por supuesto, si es el único lugar en el que usará numpy, es posible que no valga la pena depender de él.

askewchan
fuente
3
Este debería tener un np.cumsuncaso que comience con una lista, para tener en cuenta el tiempo de conversión.
hpaulj
3
Buen punto @hpaulj, para aquellos que comienzan desde (o apuntan a) un list, no lo recomendaría numpy.
askewchan
No creo que numpy sea el más rápido stackoverflow.com/questions/15889131/…
Chris_Rands
3
De acuerdo, como mencioné anteriormente. Evitar reacciones como la suya y la de @ hpaulj es la razón por la que traté de limitar su alcance en la primera y última línea de mi respuesta: - /
askewchan
1
@alex: Usando timeit, "si -nno se da, se calcula un número adecuado de bucles probando potencias sucesivas de 10 hasta que el tiempo total sea de al menos 0,2 segundos". Si espera que marque la diferencia, puede suministrar -n 1000para que todos sean equivalentes.
askewchan
94

En Python 2 puede definir su propia función de generador de esta manera:

def accumu(lis):
    total = 0
    for x in lis:
        total += x
        yield total

In [4]: list(accumu([4,6,12]))
Out[4]: [4, 10, 22]

Y en Python 3.2+ puedes usar itertools.accumulate():

In [1]: lis = [4,6,12]

In [2]: from itertools import accumulate

In [3]: list(accumulate(lis))
Out[3]: [4, 10, 22]
Ashwini Chaudhary
fuente
5
PEP 572 - Expresiones de asignación (esperado para Python 3.8) muestra una alternativa interesante total = 0; partial_sums = [total := total + v for v in values]. Todavía esperaría accumulateser más rápido.
Steven Rumbalski
3
@StevenRumbalski Hombre, personalmente creo que es la peor PEP de la historia. Ya es bastante malo ...
Ashwini Chaudhary
19

Mirad:

a = [4, 6, 12]
reduce(lambda c, x: c + [c[-1] + x], a, [0])[1:]

Saldrá (como se esperaba):

[4, 10, 22]
maravilla.mice
fuente
17
No es eficiente. El gasto total de realizar c + [c[-1] + x]una y otra vez se suma a un tiempo de ejecución cuadrático total en la longitud de entrada.
user2357112 apoya a Monica
reduce es bueno para una suma acumulativa única, pero si está haciendo muchas llamadas a su función cumsum, un generador será útil para "preprocesar" sus valores acumulativos_sum y acceder a ellos en O (1) para cada llamada posterior.
Scott Skiles
17

Hice una evaluación comparativa de las dos respuestas principales con Python 3.4 y descubrí que itertools.accumulatees más rápido que numpy.cumsumen muchas circunstancias, a menudo mucho más rápido. Sin embargo, como puede ver en los comentarios, es posible que este no sea siempre el caso, y es difícil explorar exhaustivamente todas las opciones. (No dude en agregar un comentario o editar esta publicación si tiene más resultados de referencia de interés).

Algunos horarios ...

Para listas cortas accumulatees aproximadamente 4 veces más rápido:

from timeit import timeit

def sum1(l):
    from itertools import accumulate
    return list(accumulate(l))

def sum2(l):
    from numpy import cumsum
    return list(cumsum(l))

l = [1, 2, 3, 4, 5]

timeit(lambda: sum1(l), number=100000)
# 0.4243644131347537
timeit(lambda: sum2(l), number=100000)
# 1.7077815784141421

Para listas más largas accumulatees aproximadamente 3 veces más rápido:

l = [1, 2, 3, 4, 5]*1000
timeit(lambda: sum1(l), number=100000)
# 19.174508565105498
timeit(lambda: sum2(l), number=100000)
# 61.871223849244416

Si numpy arrayno se lanza a list, accumulatesigue siendo aproximadamente 2 veces más rápido:

from timeit import timeit

def sum1(l):
    from itertools import accumulate
    return list(accumulate(l))

def sum2(l):
    from numpy import cumsum
    return cumsum(l)

l = [1, 2, 3, 4, 5]*1000

print(timeit(lambda: sum1(l), number=100000))
# 19.18597290944308
print(timeit(lambda: sum2(l), number=100000))
# 37.759664884768426

Si coloca las importaciones fuera de las dos funciones y aún devuelve a numpy array, accumulatesigue siendo casi 2 veces más rápido:

from timeit import timeit
from itertools import accumulate
from numpy import cumsum

def sum1(l):
    return list(accumulate(l))

def sum2(l):
    return cumsum(l)

l = [1, 2, 3, 4, 5]*1000

timeit(lambda: sum1(l), number=100000)
# 19.042188624851406
timeit(lambda: sum2(l), number=100000)
# 35.17324400227517
Chris_Rands
fuente
10
No esperaría que un avión sea más rápido que el tren para viajar por la ciudad, especialmente si incluye la compra de boletos y el control de seguridad. Del mismo modo, no usaría numpy para procesar uno listde cinco elementos, especialmente si no está dispuesto a aceptar un arraya cambio. Si la lista en cuestión es realmente tan corta, entonces su tiempo de ejecución sería intrascendente: las dependencias y la legibilidad seguramente dominarían. Pero el uso generalizado de un listtipo de datos numéricos uniformes de longitud significativa sería una tontería; para eso, un numpy array sería apropiado, y generalmente más rápido.
askewchan
@askewchan bueno, no solo encuentro esto para listas cortas y la pregunta del OP solicita una lista como salida en lugar de una matriz numpy. Tal vez pueda editar su respuesta para que sea más claro cuándo es apropiado cada uso :)
Chris_Rands
@askewchan De hecho, he editado mi respuesta con una comparación mucho más detallada. Bajo ninguna circunstancia, encuentro numpyser más rápido, a menos que haya pasado por alto algo.
Chris_Rands
2
Oh, sí, de hecho :) No diría que ha pasado por alto algo, pero la comparación es difícil de hacer de forma aislada sin considerar sus entradas y salidas. La mayor parte del tiempo en su sum2función es probablemente convertir len una matriz. Intente cronometrar a = np.array(l)y por np.cumsum(a)separado. A continuación, intente a = np.tile(np.arange(1, 6), 1000)vs l = [1,2,3,4,5]*1000. En un programa que lleva a cabo otros procesos numéricos (como la creación o carga de len primer lugar), sus datos de trabajo probablemente ya estén en una matriz, y la creación tendría un costo constante.
askewchan
1
@askewchan Tengo la misma idea que tú y, por lo tanto, cronometré el a = np.array (l). Para la suma2 sin la transformación a la lista, y con una matriz numpy como entrada, suma2 es 5 veces más rápido gracias a suma1 en mi computadora en el caso de la lista / matriz larga.
Mantxu
9

Intente esto: función de acumulación, junto con el operador agregar realiza la suma en ejecución.

import itertools  
import operator  
result = itertools.accumulate([1,2,3,4,5], operator.add)  
list(result)
Vani S
fuente
5
No es necesario que lo pase, operator.addya que la operación predeterminada es la adición de todos modos.
Eugene Yarmash
8

Las expresiones de asignación de PEP 572 (nuevo en Python 3.8) ofrecen otra forma de resolver esto:

time_interval = [4, 6, 12]

total_time = 0
cum_time = [total_time := total_time + t for t in time_interval]
Steven Rumbalski
fuente
5

Puede calcular la lista de suma acumulada en tiempo lineal con un forciclo simple :

def csum(lst):
    s = lst.copy()
    for i in range(1, len(s)):
        s[i] += s[i-1]
    return s

time_interval = [4, 6, 12]
print(csum(time_interval))  # [4, 10, 22]

La biblioteca estándar itertools.accumulatepuede ser una alternativa más rápida (ya que está implementada en C):

from itertools import accumulate
time_interval = [4, 6, 12]
print(list(accumulate(time_interval)))  # [4, 10, 22]
Eugene Yarmash
fuente
2
values = [4, 6, 12]
total  = 0
sums   = []

for v in values:
  total = total + v
  sums.append(total)

print 'Values: ', values
print 'Sums:   ', sums

Ejecutar este código da

Values: [4, 6, 12]
Sums:   [4, 10, 22]
Chris Taylor
fuente
2

En Python3, para encontrar la suma acumulativa de una lista donde el ielemento th es la suma de los primeros elementos i + 1 de la lista original, puede hacer:

a = [4 , 6 , 12]
b = []
for i in range(0,len(a)):
    b.append(sum(a[:i+1]))
print(b)

O puede utilizar la comprensión de listas:

b = [sum(a[:x+1]) for x in range(0,len(a))]

Salida

[4,10,22]
manish apte
fuente
Esto parece correcto, pero puede colocar un enlace a la documentación, sin eso no puedo votar a favor.
S Meaden
2

Si quieres una forma pitónica sin trabajar numpy en 2.7, esta sería mi forma de hacerlo

l = [1,2,3,4]
_d={-1:0}
cumsum=[_d.setdefault(idx, _d[idx-1]+item) for idx,item in enumerate(l)]

ahora probémoslo y probémoslo con todas las demás implementaciones

import timeit, sys
L=list(range(10000))
if sys.version_info >= (3, 0):
    reduce = functools.reduce
    xrange = range


def sum1(l):
    cumsum=[]
    total = 0
    for v in l:
        total += v
        cumsum.append(total)
    return cumsum


def sum2(l):
    import numpy as np
    return list(np.cumsum(l))

def sum3(l):
    return [sum(l[:i+1]) for i in xrange(len(l))]

def sum4(l):
    return reduce(lambda c, x: c + [c[-1] + x], l, [0])[1:]

def this_implementation(l):
    _d={-1:0}
    return [_d.setdefault(idx, _d[idx-1]+item) for idx,item in enumerate(l)]


# sanity check
sum1(L)==sum2(L)==sum3(L)==sum4(L)==this_implementation(L)
>>> True    

# PERFORMANCE TEST
timeit.timeit('sum1(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.001018061637878418

timeit.timeit('sum2(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.000829620361328125

timeit.timeit('sum3(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.4606760001182556 

timeit.timeit('sum4(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.18932826995849608

timeit.timeit('this_implementation(L)','from __main__ import sum1,sum2,sum3,sum4,this_implementation,L', number=100)/100.
>>> 0.002348129749298096
Cobry
fuente
2

Puede haber muchas respuestas para esto dependiendo de la longitud de la lista y el rendimiento. Una forma muy simple en la que puedo pensar sin pensar en la actuación es esta:

a = [1, 2, 3, 4]
a = [sum(a[0:x:1]) for x in range(len(a)+1)][1:]
print(a)

[1, 3, 6, 10]

Esto es mediante el uso de la comprensión de listas y esto puede funcionar bastante bien, es solo que aquí estoy agregando sobre el subarreglo muchas veces, ¡posiblemente podría improvisar sobre esto y hacerlo simple!

¡Salud por tu esfuerzo!

Aashish Chaubey
fuente
1

Primero, desea una lista en ejecución de subsecuencias:

subseqs = (seq[:i] for i in range(1, len(seq)+1))

Luego, simplemente llame suma cada subsecuencia:

sums = [sum(subseq) for subseq in subseqs]

(Esta no es la forma más eficiente de hacerlo, porque está agregando todos los prefijos repetidamente. Pero eso probablemente no importará para la mayoría de los casos de uso, y es más fácil de entender si no tiene que pensar en los totales acumulados.)

Si está utilizando Python 3.2 o una versión más reciente, puede usar itertools.accumulatepara hacerlo por usted:

sums = itertools.accumulate(seq)

Y si está utilizando 3.1 o una versión anterior, puede copiar la fuente "equivalente a" directamente de los documentos (excepto para cambiar next(it)a it.next()2.5 y versiones anteriores).

abarnert
fuente
9
Esto se ejecuta en tiempo cuadrático (tal vez eso no importe para el OP, pero vale la pena mencionarlo).
Chris Taylor
Primero, cuando N = 3, ¿a quién le importa el tiempo cuadrático? Y no creo que sea demasiado complicado. Son dos pasos muy simples, cada uno transforma un iterador en otro, traduciendo directamente la descripción en inglés. (El hecho de que esté usando una forma poco común de definir series, donde no se cuenta el prefijo de longitud 0, lo hace un poco más complicado ... pero eso es inherente al problema, y ​​pensé que era mejor poner eso en el rangeque hackearlo haciendo [1:]al final, o ignorarlo.)
abarnert
1
Presumiblemente, el problema real del OP no es obtener las sumas parciales de [4,6,12]ya que, como escribió en la pregunta, ¡ya sabe qué es eso!
Chris Taylor
@ChrisTaylor: Dijo explícitamente que ya sabe cómo escribir esto, pero quiere "una forma más fácil de escribirlo".
abarnert
1

Prueba esto:

result = []
acc = 0
for i in time_interval:
    acc += i
    result.append(acc)
MostafaR
fuente
-1
In [42]: a = [4, 6, 12]

In [43]: [sum(a[:i+1]) for i in xrange(len(a))]
Out[43]: [4, 10, 22]

Esto es un poco más rápido que el método generador anterior de @Ashwini para listas pequeñas

In [48]: %timeit list(accumu([4,6,12]))
  100000 loops, best of 3: 2.63 us per loop

In [49]: %timeit [sum(a[:i+1]) for i in xrange(len(a))]
  100000 loops, best of 3: 2.46 us per loop

Para listas más grandes, el generador es el camino a seguir. . .

In [50]: a = range(1000)

In [51]: %timeit [sum(a[:i+1]) for i in xrange(len(a))]
  100 loops, best of 3: 6.04 ms per loop

In [52]: %timeit list(accumu(a))
  10000 loops, best of 3: 162 us per loop
reptilicus
fuente
1
Estás cronometrando solo la lista de 3 elementos, prueba con 10 ^ 4 elementos.
Ashwini Chaudhary
1
Es cierto que para listas más grandes el generador es mucho más rápido.
reptilicus
-1

Algo hacky, pero parece funcionar:

def cumulative_sum(l):
  y = [0]
  def inc(n):
    y[0] += n
    return y[0]
  return [inc(x) for x in l]

Pensé que la función interna podría modificar lo ydeclarado en el ámbito léxico externo, pero eso no funcionó, así que jugamos algunos trucos desagradables con la modificación de la estructura. Probablemente sea más elegante usar un generador.

Vatine
fuente
-1

Sin tener que usar Numpy, puede recorrer directamente la matriz y acumular la suma en el camino. Por ejemplo:

a=range(10)
i=1
while((i>0) & (i<10)):
    a[i]=a[i-1]+a[i]
    i=i+1
print a

Resultados en:

[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
usuario3062149
fuente
-1

Un delineador de pitón puro para suma acumulativa:

cumsum = lambda X: X[:1] + cumsum([X[0]+X[1]] + X[2:]) if X[1:] else X

Esta es una versión recursiva inspirada en sumas acumulativas recursivas . Algunas explicaciones:

  1. El primer término X[:1]es una lista que contiene el elemento anterior y es casi igual a [X[0]](que se quejaría de listas vacías).
  2. La cumsumllamada recursiva en el segundo término procesa el elemento actual [1]y la lista restante cuya longitud se reducirá en uno.
  3. if X[1:]es más corto para if len(X)>1.

Prueba:

cumsum([4,6,12])
#[4, 10, 22]

cumsum([])
#[]

Y similar para producto acumulativo:

cumprod = lambda X: X[:1] + cumprod([X[0]*X[1]] + X[2:]) if X[1:] else X

Prueba:

cumprod([4,6,12])
#[4, 24, 288]
Friedrich
fuente
-1
l = [1,-1,3]
cum_list = l

def sum_list(input_list):
    index = 1
    for i in input_list[1:]:
        cum_list[index] = i + input_list[index-1]
        index = index + 1 
    return cum_list

print(sum_list(l))
Sugandha
fuente
-1

Aquí tienes otra solución divertida. Esto aprovecha el locals()dictado de una comprensión, es decir, las variables locales generadas dentro del ámbito de comprensión de la lista:

>>> [locals().setdefault(i, (elem + locals().get(i-1, 0))) for i, elem 
     in enumerate(time_interval)]
[4, 10, 22]

Esto es lo que se locals()ve para cada iteración:

>>> [[locals().setdefault(i, (elem + locals().get(i-1, 0))), locals().copy()][1] 
     for i, elem in enumerate(time_interval)]
[{'.0': <enumerate at 0x21f21f7fc80>, 'i': 0, 'elem': 4, 0: 4},
 {'.0': <enumerate at 0x21f21f7fc80>, 'i': 1, 'elem': 6, 0: 4, 1: 10},
 {'.0': <enumerate at 0x21f21f7fc80>, 'i': 2, 'elem': 12, 0: 4, 1: 10, 2: 22}]

El rendimiento no es terrible para listas pequeñas:

>>> %timeit list(accumulate([4, 6, 12]))
387 ns ± 7.53 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

>>> %timeit np.cumsum([4, 6, 12])
5.31 µs ± 67.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

>>> %timeit [locals().setdefault(i, (e + locals().get(i-1,0))) for i,e in enumerate(time_interval)]
1.57 µs ± 12 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Y, obviamente, cae plano para listas más grandes.

>>> l = list(range(1_000_000))
>>> %timeit list(accumulate(l))
95.1 ms ± 5.22 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit np.cumsum(l)
79.3 ms ± 1.07 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit np.cumsum(l).tolist()
120 ms ± 1.23 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit [locals().setdefault(i, (e + locals().get(i-1, 0))) for i, e in enumerate(l)]
660 ms ± 5.14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Aunque el método es feo y no práctico, seguro que es divertido.

Sayandip Dutta
fuente
-2
lst = [4,6,12]

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

Si está buscando una solución más eficiente (¿listas más grandes?), Un generador podría ser una buena opción (o simplemente usarlo numpysi realmente le importa el rendimiento).

def gen(lst):
    acu = 0
    for num in lst:
        yield num + acu
        acu += num

print list(gen([4, 6, 12]))
Gonz
fuente
-3

Este sería al estilo Haskell:

def wrand(vtlg):

    def helpf(lalt,lneu): 

        if not lalt==[]:
            return helpf(lalt[1::],[lalt[0]+lneu[0]]+lneu)
        else:
            lneu.reverse()
            return lneu[1:]        

    return helpf(vtlg,[0])
macropeter
fuente