Получить соответствующие суммы частей списка - PullRequest
Новая
       12

Получить соответствующие суммы частей списка

1 голос
/ 18 июня 2019

У меня есть список [0, 1, 2, 3, 4, 5, 6], и я суммирую его части так: 

l = [0, 1, 2, 3, 4, 5, 6] -> 21

l = [1, 2, 3, 4, 5, 6] -> 21

l = [2, 3, 4, 5, 6] -> 20

l = [3, 4, 5, 6] -> 18

l = [4, 5, 6] -> 15

l = [5, 6] -> 11

l = [6] -> 6

l = [] -> 0

Итак, я получаю соответствующие суммы частей списка: [21, 21, 20, 18, 15, 11, 6, 0]

КодЯ использую:

[sum(l[i:]) for i in range(len(l) + 1)]

Но для списков с диапазоном больше 100000 код значительно замедляется.

Любая идея, почему и как его оптимизировать

Ответы [ 3 ]

6 голосов
/ 18 июня 2019

Я бы предложил itertools.accumulate для этого (который я вспоминаю быстрее, чем np.cumsum), с некоторым изменением списка, чтобы получить желаемый результат: 

>>> from itertools import accumulate
>>> lst = [0, 1, 2, 3, 4, 5, 6]
>>> list(accumulate(reversed(lst)))[::-1]
[21, 21, 20, 18, 15, 11, 6]

(при необходимости можно добавить 0 в конец)

6 голосов
/ 18 июня 2019

Это может помочь сократить время расчета для больших списков: 

l = [0, 1, 2, 3, 4, 5, 6]
output = list(np.cumsum(l[::-1]))[::-1]+[0]

Вывод : 

[21, 21, 20, 18, 15, 11, 6, 0]

Вот одно сравнение по производительности для четырех различных методоввсе из которых делает то же самое: 

from timeit import timeit

def sum10(l):
    from itertools import accumulate
    return list(accumulate(reversed(l)))[::-1]+[0]

def sum11(l):
    from itertools import accumulate
    return list(accumulate(l[::-1]))[::-1]+[0]


def sum20(l):
    from numpy import cumsum
    return list(cumsum(l[::-1]))[::-1]+[0]

def sum21(l):
    from numpy import cumsum
    return list(cumsum(list(reversed(l))))[::-1]+[0]

l = list(range(1000000))
iter_0 = timeit(lambda: sum10(l), number=10)  #0.14102990700121154
iter_1 = timeit(lambda: sum11(l), number=10)  #0.1336850459993002
nump_0 = timeit(lambda: sum20(l), number=10)  #0.6019859320003889
nump_1 = timeit(lambda: sum21(l), number=10)  #0.3818727100006072
1 голос
/ 18 июня 2019

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

Этот код будет работать без каких-либо других библиотек: 

def cumulative_sum(a):
  total= 0
  for item in a:
    total += item
    yield total

list(cumulative_sum(listname))

Начиная с Python 3.8, тамновый оператор , который может помочь: 

[(x, total := total + x) for x in items]
...