Como encontrar a soma cumulativa dos números em uma lista?

93
time_interval = [4, 6, 12]

Quero somar os números [4, 4+6, 4+6+12]para obter a lista t = [4, 10, 22].

Tentei o seguinte:

t1 = time_interval[0]
t2 = time_interval[1] + t1
t3 = time_interval[2] + t2
print(t1, t2, t3)  # -> 4 10 22
user2259323
fonte
Consulte também stackoverflow.com/q/9258602
hpaulj

Respostas:

131

Se você estiver fazendo muito trabalho numérico com matrizes como esta, sugiro numpy, que vem com uma função de soma cumulativa cumsum:

import numpy as np

a = [4,6,12]

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

O Numpy costuma ser mais rápido do que o Python puro para esse tipo de coisa, veja em comparação com @ 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

Mas é claro que se for o único lugar onde você usará o numpy, pode não valer a pena depender dele.

Askewchan
fonte
3
Este deve ter um np.cumsuncase que começa com uma lista, para levar em consideração o tempo de conversão.
hpaulj de
3
Bom ponto @hpaulj, para quem está começando (ou querendo) a, listeu não recomendo numpy.
askewchan
Não acho que numpy seja mais rápido stackoverflow.com/questions/15889131/…
Chris_Rands
3
Concordo, como mencionei acima. Evitando reações como a sua e a de @hpaulj é por isso que tentei limitar seu escopo na primeira e na última linha da minha resposta: - /
askewchan
1
@alex: Usando timeit, "se -nnão for fornecido, um número adequado de loops é calculado tentando potências sucessivas de 10 até que o tempo total seja de pelo menos 0,2 segundos." Se você espera que faça diferença, pode fornecer -n 1000para torná-los todos equivalentes.
askewchan
94

No Python 2, você pode definir sua própria função de gerador assim:

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]

E no Python 3.2+ você pode 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
fonte
5
PEP 572 - Assignment Expressions (esperado para Python 3.8) mostra uma alternativa interessante total = 0; partial_sums = [total := total + v for v in values]. Eu ainda esperaria accumulateser mais rápido.
Steven Rumbalski
4
@StevenRumbalski Cara, eu pessoalmente acho que é o pior PEP de todos os tempos. Ruim o suficiente ...
Ashwini Chaudhary
19

Ver:

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

Irá produzir (conforme esperado):

[4, 10, 22]
maravilha. ratos
fonte
17
Não é eficiente. A despesa total de executar c + [c[-1] + x]repetidas vezes soma um tempo de execução total quadrático no comprimento de entrada.
user2357112 suporta Monica
reduzir é bom para uma soma cumulativa única, mas se você estiver fazendo muitas chamadas para sua função cumsum, um gerador será útil para "pré-processar" seus valores cumulative_sum e acessá-los em O (1) para cada chamada subsequente.
Scott Skiles
19

Eu fiz uma avaliação comparativa das duas principais respostas com Python 3.4 e descobri que itertools.accumulateé mais rápido do que numpy.cumsumem muitas circunstâncias, geralmente muito mais rápido. No entanto, como você pode ver nos comentários, nem sempre é esse o caso e é difícil explorar exaustivamente todas as opções. (Sinta-se à vontade para adicionar um comentário ou editar esta postagem se tiver mais resultados de referência de interesse.)

Alguns horários ...

Para listas curtas accumulateé cerca de 4 vezes mais 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 mais longas, accumulateé cerca de 3 vezes mais 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

Se numpy arraynão for lançado list, accumulateainda é cerca de 2 vezes mais 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

Se você colocar as importações fora das duas funções e ainda retornar a numpy array, accumulateainda será quase 2 vezes mais 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
fonte
10
Você não esperaria que um avião fosse mais rápido do que o trem para viajar pela cidade, especialmente incluindo a compra de passagens e a inspeção de segurança. Da mesma forma, você não usaria o numpy para processar um listdos cinco itens, especialmente se não estiver disposto a aceitar um arrayem troca. Se a lista em questão for realmente tão curta, então seu tempo de execução seria inconseqüente - dependências e legibilidade certamente dominariam. Mas o amplo uso de umlist tipo de dado numérico uniforme de comprimento significativo seria bobo; para isso, um numpy array seria apropriado e geralmente mais rápido.
askewchan
@askewchan bem, eu não acho isso apenas para listas curtas e a pergunta do OP pede uma lista como saída em vez de uma matriz numpy. Talvez você possa editar sua resposta para ficar mais claro quando cada uso é apropriado :)
Chris_Rands
@askewchan Na verdade, editei minha resposta com uma comparação muito mais detalhada. Sob nenhuma circunstância, acho que sou numpymais rápido, a menos que tenha esquecido algo?
Chris_Rands
2
Oh meu Deus, sim :) Eu não diria que você esqueceu algo, mas a comparação é difícil de fazer isoladamente sem considerar suas entradas e saídas. Na maioria das vezes, sua sum2função provavelmente está na conversão lem um array. Experimente o tempo a = np.array(l)e np.cumsum(a)separadamente. Então tentea = np.tile(np.arange(1, 6), 1000) vs l = [1,2,3,4,5]*1000. Em um programa conduzindo outros processos numéricos (como a criação ou o carregamento de lem primeiro lugar), seus dados de trabalho provavelmente já estariam em um array, e a criação seria um custo constante.
askewchan de
1
@askewchan Tive a mesma ideia que você e portanto calculei o tempo a = np.array (l). Para sum2 sem a transformação para listar e com uma matriz numpy como entrada, sum2 é 5 vezes mais rápido graças a sum1 no meu computador no caso da lista / matriz longa.
Mantxu
9

Tente isto: a função de acumulação, junto com a adição do operador, executa a adição em execução.

import itertools  
import operator  
result = itertools.accumulate([1,2,3,4,5], operator.add)  
list(result)
Vani S
fonte
6
Você não precisa passar operator.addporque a operação padrão é adição de qualquer maneira.
Eugene Yarmash
8

As expressões de atribuição do PEP 572 (novo no Python 3.8) oferecem outra maneira de resolver isso:

time_interval = [4, 6, 12]

total_time = 0
cum_time = [total_time := total_time + t for t in time_interval]
Steven Rumbalski
fonte
7

Você pode calcular a lista de soma cumulativa em tempo linear com um forloop simples :

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]

A biblioteca padrão itertools.accumulatepode ser uma alternativa mais rápida (já que é implementada em C):

from itertools import accumulate
time_interval = [4, 6, 12]
print(list(accumulate(time_interval)))  # [4, 10, 22]
Eugene Yarmash
fonte
3

Se você quiser uma forma pitônica sem o trabalho entorpecido no 2.7, esta seria a minha maneira de fazê-lo

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

agora vamos tentar e testar contra todas as outras implementações

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
fonte
3

Pode haver muitas respostas para isso, dependendo do tamanho da lista e do desempenho. Uma maneira muito simples que posso pensar sem pensar na performance é 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]

Isso é feito usando a compreensão de lista e isso pode funcionar muito bem, mas aqui estou adicionando o subarray muitas vezes, você poderia improvisar sobre isso e torná-lo simples!

Felicidades pelo seu esforço!

Aashish Chaubey
fonte
2
values = [4, 6, 12]
total  = 0
sums   = []

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

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

Executar este código dá

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

Em Python3, para encontrar a soma cumulativa de uma lista em que o iésimo elemento é a soma dos primeiros i + 1 elementos da lista original, você pode fazer:

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

OU você pode usar a compreensão de lista:

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

Resultado

[4,10,22]
Apte manish
fonte
Isso parece certo, mas pode cair um link para a documentação, sem isso eu não posso votar positivamente.
S Meaden
1

Primeiro, você quer uma lista contínua de subsequências:

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

Então você apenas chama sumcada subsequência:

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

(Esta não é a maneira mais eficiente de fazer isso, porque você está adicionando todos os prefixos repetidamente. Mas isso provavelmente não importa para a maioria dos casos de uso e é mais fácil de entender se você não tiver que pensar em os totais corridos.)

Se estiver usando Python 3.2 ou mais recente, você pode usar itertools.accumulatepara fazer isso por você:

sums = itertools.accumulate(seq)

E se você estiver usando 3.1 ou anterior, você pode simplesmente copiar o "equivalente a" fonte em linha reta fora dos docs (exceto para mudar next(it)a it.next()para 2,5 e anteriores).

abarnert
fonte
9
Isso é executado em tempo quadrático (talvez isso não importe para o OP, mas vale a pena mencionar).
Chris Taylor,
Primeiro, quando N = 3, quem se importa com o tempo quadrático? E não acho que seja complicado demais. São duas etapas muito simples, cada uma transformando um iterador em outro, traduzindo diretamente a descrição em inglês. (O fato de ele estar usando uma maneira incomum de definir séries, onde o prefixo de comprimento 0 não é contado, torna um pouco mais complicado ... mas isso é inerente ao problema, e achei melhor colocá-lo no rangedo que hackear [1:]no final, ou ignorá-lo.)
abarnert
1
Presumivelmente, o problema real do OP não é obter as somas parciais [4,6,12], pois, como ele escreveu na pergunta, ele já sabe o que é!
Chris Taylor,
@ChrisTaylor: Ele disse explicitamente que já sabe escrever isso, mas quer "uma maneira mais fácil de escrever".
abarnert em
1

Experimente isto:

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

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

Esta é slighlty mais rápido do que o método gerador acima por @Ashwini para pequenas listas

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 maiores, o gerador é o caminho certo. . .

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
fonte
1
Você está cronometrando para uma lista de apenas 3 itens, tente para 10 ^ 4 itens.
Ashwini Chaudhary
1
É verdade que para listas maiores o gerador é muito mais rápido!
reptilicus
-1

Um pouco hacky, mas parece funcionar:

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

Eu realmente pensei que a função interna seria capaz de modificar o ydeclarado no escopo léxico externo, mas isso não funcionou, então nós jogamos alguns hacks desagradáveis ​​com modificação de estrutura. Provavelmente é mais elegante usar um gerador.

Vatine
fonte
-1

Sem ter que usar o Numpy, você pode fazer um loop diretamente sobre a matriz e acumular a soma ao longo do caminho. Por exemplo:

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

Resulta em:

[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
user3062149
fonte
-1

Um oneliner python puro para soma cumulativa:

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

Esta é uma versão recursiva inspirada em somas cumulativas recursivas . Algumas explicações:

  1. O primeiro termo X[:1]é uma lista contendo o elemento anterior e é quase o mesmo que[X[0]] (o que reclamaria de listas vazias).
  2. A cumsumchamada recursiva no segundo termo processa o elemento atual [1]e a lista restante, cujo comprimento será reduzido em um.
  3. if X[1:]é mais curto para if len(X)>1.

Teste:

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

cumsum([])
#[]

E semelhante para produto cumulativo:

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

Teste:

cumprod([4,6,12])
#[4, 24, 288]
Friedrich
fonte
-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
fonte
-1

Aqui está outra solução divertida. Isso aproveita o locals()ditado de uma compreensão, ou seja, variáveis ​​locais geradas dentro do escopo de compreensão da lista:

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

Aqui está o que ele locals()procura para cada iteração:

>>> [[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}]

O desempenho não é terrível para listas pequenas:

>>> %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)

E, obviamente, não dá certo para listas maiores.

>>> 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)

Mesmo que o método seja feio e pouco prático, com certeza é divertido.

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

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

Se você estiver procurando por uma solução mais eficiente (listas maiores?), Um gerador pode ser uma boa opção (ou apenas use numpyse você realmente se preocupa com o desempenho).

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

print list(gen([4, 6, 12]))
gonz
fonte
-3

Isso seria no 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])
macropéter
fonte