python - Calcule la suma acumulativa de una lista hasta que aparezca un cero

performance binary

Question

Tengo una lista (larga) en la que aparecen ceros y unos al azar:

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

Quiero obtener la lista_b

• Suma de la lista hasta donde aparece 0.

• donde aparece 0, retiene 0 en la lista

  list_b = [1, 2, 3, 0, 1, 2, 0, 1, 0, 1, 2, 3]

Puedo implementar esto de la siguiente manera:

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)
print(list_b)

pero la longitud real de la lista es muy larga.

Por lo tanto, quiero mejorar el código de alta velocidad. (si no es legible)

Cambio el código de esta manera:

from itertools import takewhile
list_c = [sum(takewhile(lambda x: x != 0, list_a[i::-1])) for i, d in enumerate(list_a)]
print(list_c)

Pero no es lo suficientemente rápido. ¿Cómo puedo hacerlo de manera más eficiente?

Answer 1

Está jugando demasiado con los índices en el código que publicó cuando realmente no tiene que hacerlo. Solo puede hacer un seguimiento de una suma acumulada y restablecerla a 0 cada vez que cumpla con un 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]

Answer 2

Estás pensando demasiado en esto.

Opción 1
Puede simplemente iterar sobre los índices y actualizarlos (calculando la suma acumulada), según si el valor actual es 0 o no.

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] 

Es decir, si el elemento actual no es cero, entonces actualice el elemento en el índice actual como la suma del valor actual, más el valor en el índice anterior.

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

Tenga en cuenta que esto actualiza su lista en su lugar. Puede crear una copia de antemano si no quiere eso - new_data = data.copy() e iterar sobre new_data de la misma manera.

opcion 2
Puedes usar la API de pandas si necesitas rendimiento. Encuentre grupos según la ubicación de 0 s, y use groupby + cumsum para calcular sumas acumulativas por grupo, similares a las anteriores:

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]

Actuación

Primero, la configuración -

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

Siguiente,

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

Y, cronometrando la copia por separado,

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

Por lo tanto, la copia realmente no toma mucho tiempo. Finalmente,

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

El enfoque de los pandas es conceptualmente lineal (al igual que los otros enfoques) pero más rápido en un grado constante debido a la implementación de la biblioteca.

Answer 3

No tiene que ser tan complicado como se hace en la pregunta, un enfoque muy simple podría ser este.

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

Answer 4

Personalmente preferiría un generador simple como este:

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

Nada mágico (cuando sabes cómo funciona el yield ), fácil de leer y debería ser bastante rápido.

Si necesita más rendimiento, podría incluso envolver esto como el tipo de extensión Cython (aquí estoy usando IPython). Por lo tanto, se pierde la parte "fácil de entender" y se requieren "dependencias pesadas":

%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

Ambos deben consumirse, por ejemplo, utilizando la list para obtener el resultado deseado:

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

Sin embargo, ya que me preguntaste sobre la velocidad, quería compartir los resultados de mis tiempos:

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

En caso de que esté interesado en los resultados exactos los puse en esta esencia .

Es un gráfico log-log y relativo a la respuesta de Cython. En resumen: cuanto más bajo, más rápido, el rango entre dos tics principales representa un orden de magnitud.

Por lo tanto, todas las soluciones tienden a estar dentro de un orden de magnitud (al menos cuando la lista es grande), excepto las soluciones que tenía. Extrañamente, la solución de los pandas es bastante lenta en comparación con los enfoques puros de Python. Sin embargo, la solución de Cython supera a todos los otros enfoques por un factor de 2.

Answer 5

Si desea una solución nativa compacta de Python que sea probablemente la más eficiente en memoria, aunque no sea la más rápida (vea los comentarios), puede extraer mucho de 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]

Los pasos aquí son: agrupar la lista en sublistas según la presencia de 0 (que es falsa), tomar la suma acumulativa de los valores dentro de cada sublista, aplanar las sublistas.

Como lo comenta Stefan Pochmann , si su lista tiene contenidos binarios (como solo consta de 1 sy 0 s), no necesita pasar una clave a groupby() en absoluto y se basará en la función de identidad. Esto es ~ 30% más rápido que usar bool para este caso:

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

Answer 6

Yo usaría un generador si quieres rendimiento (y también es simple).

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

No creo que consigas algo mejor que eso, en cualquier caso tendrás que iterar sobre list_a al menos una vez.

Tenga en cuenta que llamé a list () en el resultado para obtener una lista como en su código, pero si el código que usa list_b está iterando sobre él solo una vez con un bucle for o algo, no sirve de nada convertir el resultado en una lista, simplemente pase el generador.