22 votes

Calculer la somme cumulée de la liste jusqu'à ce qu'un zéro apparaît

J'ai une (longue) liste dans laquelle les zéros et les uns apparaissent au hasard:

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

Je veux obtenir le list_b

  • somme de la liste jusqu'à l'endroit où 0 s'affiche
  • où 0 s'affiche, conserver 0 dans la liste

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

Je peux mettre en œuvre la présente comme suit:

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)

mais la liste réelle de la longueur est très longue.

Donc, je veux améliorer le code pour la grande vitesse. (si elle n'est pas lisible)

- Je changer le code comme ceci:

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)

Mais il n'est pas assez rapide. Comment puis-je le faire de manière plus efficace?

36voto

coldspeed Points 111053

Vous êtes d'avoir à y penser cela.

Option 1
Vous pouvez simplement effectuer une itération sur les indices et la mise à jour en conséquence (calcul de la somme cumulée), en se basant sur la valeur actuelle 0 ou pas.

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] 

C'est, si l'élément courant est non nulle, alors la mise à jour de l'élément à l'indice actuel comme la somme de la valeur actuelle, en plus de la valeur à l'indice précédent.

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

Notez que cette mise à jour de votre liste à la place. Vous pouvez créer une copie à l'avance si vous ne voulez pas que - new_data = data.copy() et parcourir new_data de la même manière.


Option 2
Vous pouvez utiliser les pandas de l'API si vous avez besoin de la performance. Trouver des groupes basés sur l'emplacement de 0s, et d'utiliser groupby + cumsum pour calculer un groupe de lampes sommes cumulées, similaire à ci-dessus:

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]

Performance

Tout d'abord, le programme d'installation -

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

Ensuite,

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

Et, le calendrier de la copie séparément,

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

Ainsi, la copie n'a pas vraiment prendre beaucoup de temps. Enfin,

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

Les pandas approche est conceptuellement linéaire (tout comme les autres approches), mais plus rapide par une constante de degré en raison de la mise en œuvre de la bibliothèque.

16voto

Chris_Rands Points 15161

Si vous voulez un compact natif Python solution qui est probablement le plus efficace en terme de mémoire, bien que pas le plus rapide (voir les commentaires), vous pouvez attirer beaucoup d' 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]

Les étapes sont les suivantes: groupe de la liste de sous-listes basées sur la présence d' 0 (ce qui est falsy), prendre la somme cumulée des valeurs au sein de chaque sous-liste, aplatir les sous-listes.

Comme Stefan Pochmann commentaires, si votre liste est binaire dans le contenu (comme composé de seulement 1s et 0s seulement), alors vous n'avez pas besoin de passer une clé d' groupby() , et il en sera de retour sur la fonction identité. C'est ~30% plus rapide que d'utiliser bool pour ce cas:

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

9voto

MSeifert Points 6307

Personnellement, je préférerais un générateur simple comme ceci:

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

Rien de magique (quand vous savez comment yield des travaux), facile à lire et plutôt rapide.

Si vous avez besoin de plus de performances, on pourrait même conclure que Cython type d'extension (je suis en utilisant IPython ici). Ainsi, vous perdez le "facile à comprendre" partie et nécessitant de lourds dépendances":

%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

Les deux doivent être consommés, par exemple à l'aide de list pour donner le résultat souhaité:

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

Cependant, puisque vous m'avez demandé de vitesse, je voulais partager les résultats de mes horaires:

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

Dans le cas où vous êtes intéressé par le résultat exact je les ai mis dans ce résumé.

enter image description here

C'est un graphe log-log et par rapport à la Cython réponse. En bref: La baisse la plus rapide et la distance entre deux graduations principales représente un ordre de grandeur.

Donc, toutes les solutions ont tendance à être à l'intérieur d'un ordre de grandeur (au moins lorsque la liste est grand), sauf pour les solutions que vous avez eu. Étrangement les pandas solution est assez lent par rapport à la pure Python approches. Cependant, le Cython solution bat tous les autres approches par un facteur de 2.

7voto

Ev. Kounis Points 9620

Vous jouez avec les indices de trop dans le code que vous avez posté, lorsque vous n'avez pas vraiment. Vous pouvez juste garder une trace d'une somme cumulative et de le remettre à 0 chaque fois que vous rencontrerez 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]

4voto

Shubham Mishra Points 166

Il ne doit pas être aussi compliqué que de fait dans la question posée, une approche très simple qui pourrait être présent.

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

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X