Вычислить суммарную сумму списка, пока не появится нуль

Ответ 1

Вы слишком задумываетесь об этом.

Опция 1
Вы можете просто перебирать индексы и соответственно обновлять (вычислять совокупную сумму), исходя из того, является ли текущее значение 0 или нет.

data = [1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]

for i in range(1, len(data)):
    if data[i]:  
        data[i] += data[i - 1] 

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

print(data)
[1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]

Обратите внимание, что это обновляет ваш список на месте. Вы можете создать копию заранее, если вы не хотите, чтобы это - new_data = data.copy() и перебирали new_data таким же образом.

Вариант 2
Вы можете использовать API pandas, если вам нужна производительность. Найдите группы, основанные на размещении 0 с, и используйте groupby + cumsum для вычисления совокупных сумм по группам, как описано выше:

import pandas as pd

s = pd.Series(data)    
data = s.groupby(s.eq(0).cumsum()).cumsum().tolist()

print(data)
[1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]

Спектакль

Во-первых, настройка -

data = data * 100000
s = pd.Series(data)

Следующий,

%%timeit
new_data = data.copy()
for i in range(1, len(data)):
    if new_data[i]:  
        new_data[i] += new_data[i - 1]

328 ms ± 4.09 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

И, синхронизируя копию отдельно,

%timeit data.copy()
8.49 ms ± 17.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Итак, копия на самом деле не занимает много времени. В заключение,

%timeit s.groupby(s.eq(0).cumsum()).cumsum().tolist()
122 ms ± 1.69 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Подход панд концептуально линейный (как и другие подходы), но быстрее с постоянной степенью из-за реализации библиотеки.

Ответ 2

Если вы хотите, чтобы компактное родное решение Python, пожалуй, было наиболее эффективным с точки зрения памяти, хотя и не самым быстрым (см. Комментарии), вы можете широко использовать его из itertools:

>>> from itertools import groupby, accumulate, chain
>>> list(chain.from_iterable(accumulate(g) for _, g in groupby(list_a, bool)))
[1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]

Шаги здесь: группировать список в подсписках на основе наличия 0 (что является ложным), принимать кумулятивную сумму значений в каждом подсписке, сглаживать подсписки.

Как пишет Stefan Pochmann, если ваш список является двоичным по содержанию (например, состоящий только из 1 и 0), вам не нужно передавать ключ в groupby() вообще, и он будет возвращаться к функции идентификации. Это на 30% быстрее, чем использование bool для этого случая:

>>> list(chain.from_iterable(accumulate(g) for _, g in groupby(list_a)))
[1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]

Ответ 3

Лично я предпочел бы простой генератор вроде этого:

def gen(lst):
    cumulative = 0
    for item in lst:
        if item:
            cumulative += item
        else:
            cumulative = 0
        yield cumulative

Ничего магия (если вы знаете, как yield работает), легко читать и должно быть довольно быстро.

Если вам нужно больше производительности, вы можете даже обернуть это как тип расширения Cython (я использую здесь IPython). Таким образом, вы теряете "легко понятную" часть и требуете "тяжелых зависимостей":

%load_ext cython

%%cython

cdef class Cumulative(object):
    cdef object it
    cdef object cumulative
    def __init__(self, it):
        self.it = iter(it)
        self.cumulative = 0

    def __iter__(self):
        return self

    def __next__(self):
        cdef object nxt = next(self.it)
        if nxt:
            self.cumulative += nxt
        else:
            self.cumulative = 0
        return self.cumulative

И то, и другое нужно потреблять, например, используя list чтобы дать желаемый результат:

>>> list_a = [1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]
>>> list(gen(list_a))
[1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]
>>> list(Cumulative(list_a))
[1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]

Однако, так как вы спросили о скорости, я хотел бы поделиться результатами моих таймингов:

import pandas as pd
import numpy as np
import random

import pandas as pd
from itertools import takewhile
from itertools import groupby, accumulate, chain

def MSeifert(lst):
    return list(MSeifert_inner(lst))

def MSeifert_inner(lst):
    cumulative = 0
    for item in lst:
        if item:
            cumulative += item
        else:
            cumulative = 0
        yield cumulative

def MSeifert2(lst):
    return list(Cumulative(lst))

def original1(list_a):
    list_b = []
    for i, x in enumerate(list_a):
        if x == 0:
            list_b.append(x)
        else:
            sum_value = 0
            for j in list_a[i::-1]:
                if j != 0:
                    sum_value += j
                else:
                    break
            list_b.append(sum_value)

def original2(list_a):
    return [sum(takewhile(lambda x: x != 0, list_a[i::-1])) for i, d in enumerate(list_a)]

def Coldspeed1(data):
    data = data.copy()
    for i in range(1, len(data)):
        if data[i]:  
            data[i] += data[i - 1] 
    return data

def Coldspeed2(data):
    s = pd.Series(data)    
    return s.groupby(s.eq(0).cumsum()).cumsum().tolist()

def Chris_Rands(list_a):
    return list(chain.from_iterable(accumulate(g) for _, g in groupby(list_a, bool)))

def EvKounis(list_a):
    cum_sum = 0
    list_b = []
    for item in list_a:
        if not item:            # if our item is 0
            cum_sum = 0         # the cumulative sum is reset (set back to 0)
        else:
            cum_sum += item     # otherwise it sums further
        list_b.append(cum_sum)  # and no matter what it gets appended to the result

def schumich(list_a):
    list_b = []
    s = 0
    for a in list_a:
        s = a+s if a !=0 else 0
        list_b.append(s)
    return list_b

def jbch(seq):
    return list(jbch_inner(seq))

def jbch_inner(seq):
    s = 0
    for n in seq:
        s = 0 if n == 0 else s + n
        yield s


# Timing setup
timings = {MSeifert: [], 
           MSeifert2: [],
           original1: [], 
           original2: [],
           Coldspeed1: [],
           Coldspeed2: [],
           Chris_Rands: [],
           EvKounis: [],
           schumich: [],
           jbch: []}
sizes = [2**i for i in range(1, 20, 2)]

# Timing
for size in sizes:
    print(size)
    func_input = [int(random.random() < 0.75) for _ in range(size)]
    for func in timings:
        if size > 10000 and (func is original1 or func is original2):
            continue
        res = %timeit -o func(func_input)   # if you use IPython, otherwise use the "timeit" module
        timings[func].append(res)


%matplotlib notebook

import matplotlib.pyplot as plt
import numpy as np

fig = plt.figure(1)
ax = plt.subplot(111)

baseline = MSeifert2 # choose one function as baseline
for func in timings:
    ax.plot(sizes[:len(timings[func])], 
            [time.best / ref.best for time, ref in zip(timings[func], timings[baseline])], 
            label=func.__name__)  # you could also use "func.__name__" here instead
ax.set_ylim(0.8, 1e4)
ax.set_yscale('log')
ax.set_xscale('log')
ax.set_xlabel('size')
ax.set_ylabel('time relative to {}'.format(baseline)) # you could also use "func.__name__" here instead
ax.grid(which='both')
ax.legend()
plt.tight_layout()

Если вас интересуют точные результаты, я помещаю их в эту суть.

Это лог-лог-график и относительно ответа Cython. Короче: чем ниже скорость, тем выше диапазон между двумя основными тиками.

Таким образом, все решения имеют тенденцию быть в пределах одного порядка (по крайней мере, когда список большой), за исключением решений, которые у вас были. Странно, что решение pandas довольно медленное по сравнению с чистыми подходами Python. Однако решение Cython превосходит все остальные подходы в 2 раза.

Ответ 4

Вы играете слишком сильно с индексом в коде, который вы опубликовали, когда вам действительно не нужно. Вы можете просто следить за суммарной суммой и сбрасывать ее до 0 каждый раз, когда вы встречаете 0.

list_a = [1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]

cum_sum = 0
list_b = []
for item in list_a:
    if not item:            # if our item is 0
        cum_sum = 0         # the cumulative sum is reset (set back to 0)
    else:
        cum_sum += item     # otherwise it sums further
    list_b.append(cum_sum)  # and no matter what it gets appended to the result
print(list_b)  # -> [1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]

Ответ 5

Это не должно быть так сложно, как сделано в заданном вопросе, может быть очень простой подход.

list_a = [1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]
list_b = []
s = 0
for a in list_a:
    s = a+s if a !=0 else 0
    list_b.append(s)

print list_b

Ответ 6

Я бы использовал генератор, если вам нужна производительность (и это тоже просто).

def weird_cumulative_sum(seq):
    s = 0
    for n in seq:
        s = 0 if n == 0 else s + n
        yield s

list_b = list(weird_cumulative_sum(list_a_))

Я не думаю, что вы поправляетесь, но в любом случае вам придется перебирать список по крайней мере один раз.

Обратите внимание, что я вызвал list() в результате, чтобы получить список, как в вашем коде, но если код с использованием list_b выполняет итерацию по нему только один раз с циклом for или что-то, что нет смысла преобразовывать результат в список, просто передайте его генератор.

Ответ 7

Начиная с Python 3.8 и введением выражений присваивания (PEP 572) (:= оператор), мы можем использовать и увеличивать переменную в пределах понимания списка:

# items = [1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]
total = 0
[total := (total + x if x else x) for x in items]
# [1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]

Это:

• Инициализирует переменную total значение 0 что символизирует промежуточную сумму
• Для каждого элемента это оба:
  • либо увеличивает total с текущим зацикленным элементом (total := total + x) с помощью выражения присваивания, либо устанавливает его обратно в 0 если элемент равен 0
  • и в то же время сопоставляет x с новым значением total