Как найти кумулятивную сумму чисел в списке?

92
time_interval = [4, 6, 12]

Я хочу суммировать цифры [4, 4+6, 4+6+12], чтобы получить список t = [4, 10, 22].

Я пробовал следующее:

t1 = time_interval[0]
t2 = time_interval[1] + t1
t3 = time_interval[2] + t2
print(t1, t2, t3)  # -> 4 10 22
user2259323
источник
См. Также stackoverflow.com/q/9258602
hpaulj

Ответы:

128

Если вы много работаете с числами с подобными массивами, я бы посоветовал numpyвоспользоваться функцией накопительной суммы cumsum:

import numpy as np

a = [4,6,12]

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

Numpy часто быстрее, чем чистый питон для такого рода вещей, см. По сравнению с @ 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

Но, конечно, если это единственное место, где вы будете использовать numpy, возможно, не стоит зависеть от него.

косо
источник
3
Это должно быть np.cumsunдело, которое начинается со списка, чтобы учесть время преобразования.
hpaulj
3
Хороший замечание @hpaulj, для тех, кто начинает (или стремится к), listя бы не рекомендовал numpy.
askewchan
Я не думаю, что numpy - самый быстрый stackoverflow.com/questions/15889131/…
Chris_Rands
3
Согласен, как я уже говорил выше. Избегая реакций, подобных вашей и @ hpaulj, я попытался ограничить его объем в самой первой и последней строках своего ответа: - /
askewchan
1
@alex: Используя timeit, «если -nне задано, подходящее количество циклов рассчитывается путем попытки последовательных степеней 10 до тех пор, пока общее время не составит не менее 0,2 секунды». Если вы ожидаете, что это изменит ситуацию, вы можете -n 1000сделать их все равноценными.
askewchan
94

В Python 2 вы можете определить свою собственную функцию генератора следующим образом:

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]

А в Python 3.2+ вы можете использовать itertools.accumulate():

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

In [2]: from itertools import accumulate

In [3]: list(accumulate(lis))
Out[3]: [4, 10, 22]
Ашвини Чаудхари
источник
5
PEP 572 - Выражения присваивания (ожидается для Python 3.8) показывает интересную альтернативу total = 0; partial_sums = [total := total + v for v in values]. Я все равно ожидал accumulateбы быть быстрее.
Стивен Румбальский
3
@StevenRumbalski Человек, я лично считаю, что это худший PEP на свете. Достаточно плохо ...
Ашвини Чаудхари
19

Вот:

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

Выведет (как и ожидалось):

[4, 10, 22]
чудо. мышка
источник
17
Не эффективно. Общие затраты на выполнение c + [c[-1] + x]снова и снова составляют общее время выполнения, квадратичное по длине ввода.
user2357112 поддерживает Монику
reduce хорош для одноразовой кумулятивной суммы, но если вы делаете много вызовов своей функции cumsum, генератор будет полезен для «предварительной обработки» ваших значений cumulative_sum и доступа к ним в O (1) для каждого последующего вызова.
Скотт Скилс
17

Я провел тест двух лучших ответов с Python 3.4 и обнаружил, что itertools.accumulateон быстрее, чем numpy.cumsumпри многих обстоятельствах, часто намного быстрее. Однако, как видно из комментариев, это может быть не всегда, и исчерпывающе изучить все варианты сложно. (Не стесняйтесь добавить комментарий или отредактировать этот пост, если у вас есть интересующие результаты тестов.)

Некоторое время ...

Для коротких списков accumulateпримерно в 4 раза быстрее:

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

Для более длинных списков accumulateпримерно в 3 раза быстрее:

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

Если numpy arrayне приведено к list, accumulateвсе равно примерно в 2 раза быстрее:

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

Если вы поместите импорт за пределы двух функций и все равно вернете a numpy array, accumulateвсе равно будет почти в 2 раза быстрее:

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
источник
10
Вы не ожидаете, что самолет будет быстрее, чем поезд, путешествующий по городу, особенно с учетом покупки билетов и проверки безопасности. Точно так же вы не будете использовать numpy для обработки listпяти элементов, особенно если вы не хотите принимать arrayвзамен. Если рассматриваемый список действительно такой короткий, то время их выполнения будет несущественным - зависимости и удобочитаемость, безусловно, будут преобладать. Но широкое использование listединого числового типа данных значительной длины было бы глупо; для этого array будет подходящим numpy , и обычно быстрее.
askewchan
@askewchan ну, я не просто нахожу это для коротких списков, и вопрос OP запрашивает список в качестве вывода, а не массив numpy. Возможно, вы можете отредактировать свой ответ, чтобы было понятнее, когда каждое использование подходит :)
Chris_Rands
@askewchan На самом деле я отредактировал свой ответ с гораздо более подробным сравнением. Ни при каких обстоятельствах не могу ли я numpyбыть быстрее, если я что-то не упустил?
Chris_Rands
2
О, да, конечно :) Я бы не сказал, что вы что-то упустили, но сравнение сложно провести изолированно, не учитывая ваши входы и выходы. Большая часть времени в вашей sum2функции, вероятно, заключается в преобразовании lв массив. Попробуй тайминг a = np.array(l)и np.cumsum(a)отдельно. Тогда попробуйте a = np.tile(np.arange(1, 6), 1000)против l = [1,2,3,4,5]*1000. В программе, выполняющей другие числовые процессы (например, создание или загрузка lв первую очередь), ваши рабочие данные, вероятно, уже будут в массиве, и создание будет стоить постоянную стоимость.
askewchan
1
@askewchan У меня такая же идея, как и у вас, и поэтому я рассчитал время a = np.array (l). Для sum2 без преобразования в список и с массивом numpy в качестве входных данных sum2 в 5 раз быстрее, спасибо sum1 на моем компьютере в случае длинного списка / массива.
Mantxu
9

Попробуйте следующее: функция накопления вместе с оператором add выполняет текущее сложение.

import itertools  
import operator  
result = itertools.accumulate([1,2,3,4,5], operator.add)  
list(result)
Вани С
источник
5
Вам не нужно переходить, operator.addпоскольку операция по умолчанию в любом случае является добавлением.
Евгений Ярмаш
8

Выражения присваивания из PEP 572 (новое в Python 3.8) предлагают еще один способ решить эту проблему:

time_interval = [4, 6, 12]

total_time = 0
cum_time = [total_time := total_time + t for t in time_interval]
Стивен Румбальский
источник
5

Вы можете рассчитать совокупный список сумм за линейное время с помощью простого forцикла:

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]

Стандартная библиотека itertools.accumulateможет быть более быстрой альтернативой (поскольку она реализована на C):

from itertools import accumulate
time_interval = [4, 6, 12]
print(list(accumulate(time_interval)))  # [4, 10, 22]
Евгений Ярмаш
источник
2
values = [4, 6, 12]
total  = 0
sums   = []

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

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

Запуск этого кода дает

Values: [4, 6, 12]
Sums:   [4, 10, 22]
Крис Тейлор
источник
2

В Python3, чтобы найти кумулятивную сумму списка, где ith элемент является суммой первых элементов i + 1 из исходного списка, вы можете сделать:

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

ИЛИ вы можете использовать понимание списка:

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

Выход

[4,10,22]
Manish apte
источник
Это выглядит правильно, но я могу оставить ссылку на документацию, без этого я не могу проголосовать.
S Meaden,
2

Если вам нужен питонический способ без работы numpy в 2.7, это был бы мой способ сделать это

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

теперь давайте попробуем и проверим на всех других реализациях

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
Кобри
источник
2

На это может быть много ответов, в зависимости от длины списка и производительности. Один очень простой способ, который я могу думать, не думая о производительности, заключается в следующем:

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]

Это происходит с использованием понимания списка, и это может работать довольно хорошо, просто здесь я добавляю много раз над подмассивом, вы могли бы импровизировать с этим и упростить!

Приветствую вас!

Аашиш Чаубей
источник
1

Во-первых, вам нужен текущий список подпоследовательностей:

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

Затем вы просто вызываете sumкаждую подпоследовательность:

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

(Это не самый эффективный способ сделать это, потому что вы постоянно добавляете все префиксы. Но это, вероятно, не имеет значения для большинства случаев использования, и его легче понять, если вам не нужно думать о промежуточные итоги.)

Если вы используете Python 3.2 или новее, вы можете использовать itertools.accumulateдля этого:

sums = itertools.accumulate(seq)

А если вы используете 3.1 или более раннюю версию, вы можете просто скопировать "эквивалентный" исходный код прямо из документации (за исключением перехода на 2.5 и более ранние next(it)версии it.next()).

Abarnert
источник
9
Это выполняется в квадратичном времени (возможно, это не имеет значения для OP, но стоит упомянуть).
Крис Тейлор
Во-первых, когда N = 3, кого волнует квадратичное время? И я не думаю, что это слишком сложно. Это два очень простых шага, каждый из которых преобразует один итератор в другой, напрямую переводя англоязычное описание. (Тот факт, что он использует необычный способ определения серии, где префикс нулевой длины не учитывается, делает его немного более сложным ... но это является неотъемлемой частью проблемы, и я подумал, что лучше поместить это в rangeчем обойти это, делая [1:]в конце, или игнорировать это.)
abarnert 08
1
По-видимому, настоящая проблема ОП не в том, чтобы получить частичные суммы, [4,6,12]поскольку, как он написал в вопросе, он уже знает, что это такое!
Крис Тейлор
@ChrisTaylor: Он прямо сказал, что уже знает, как это писать, но хочет "более простой способ написать это".
abarnert 08
1

Попробуй это:

result = []
acc = 0
for i in time_interval:
    acc += i
    result.append(acc)
МостафаР
источник
-1
In [42]: a = [4, 6, 12]

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

Это немного быстрее, чем метод генератора выше @Ashwini для небольших списков

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

Для больших списков обязательно используйте генератор. . .

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
рептиликус
источник
1
Вы рассчитываете только для списка из 3 пунктов, попробуйте 10 ^ 4 пунктов.
Ашвини Чаудхари
1
Правда, для больших списков генератор работает намного быстрее!
reptilicus 08
-1

Немного хакерский, но, похоже, работает:

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

Я действительно думал, что внутренняя функция сможет изменить yобъявленное во внешней лексической области видимости, но это не сработало, поэтому вместо этого мы используем несколько неприятных хаков с модификацией структуры. Возможно, более элегантно использовать генератор.

Ватин
источник
-1

Без использования Numpy вы можете перебирать массив напрямую и накапливать сумму по пути. Например:

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

Результаты в:

[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
user3062149
источник
-1

Чистый питон oneliner для накопительной суммы:

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

Это рекурсивная версия, вдохновленная рекурсивными совокупными суммами . Некоторые пояснения:

  1. Первый член X[:1]- это список, содержащий предыдущий элемент, и он почти такой же, как [X[0]](который будет жаловаться на пустые списки).
  2. Рекурсивный cumsumвызов во втором члене обрабатывает текущий элемент [1]и оставшийся список, длина которого будет уменьшена на единицу.
  3. if X[1:]короче для if len(X)>1.

Контрольная работа:

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

cumsum([])
#[]

И моделирование совокупного продукта:

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

Контрольная работа:

cumprod([4,6,12])
#[4, 24, 288]
Фридрих
источник
-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))
Суганда
источник
-1

Вот еще одно забавное решение. Это использует преимущество locals()понимания, то есть локальные переменные, сгенерированные внутри области понимания списка:

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

Вот как locals()выглядит каждая итерация:

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

Производительность не страшна для небольших списков:

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

И, очевидно, не подходит для больших списков.

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

Несмотря на то, что этот метод уродлив и непрактичен, он определенно забавен.

Саяндип Датта
источник
-2
lst = [4,6,12]

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

Если вы ищете более эффективное решение (большие списки?), Генератор может быть хорошим numpyвыбором (или просто используйте, если вы действительно заботитесь о производительности).

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

print list(gen([4, 6, 12]))
гонз
источник
-3

Это будет в стиле 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])
макропетр
источник