Index maximal des éléments répétitifs divisibles par 'n' dans une liste en Python

Question

J'ai une liste triée de nombres comme :

a = [77,98,99,100,101,102,198,199,200,200,278,299,300,300,300]

Je dois trouver l'indice maximal de chaque valeur qui est divisible par 100.

La sortie devrait être comme : 4,10,15

Mon code :

a = [77,98,99,100,101,102,198,199,200,200,278,299,300,300,300]
idx = 1
for i in (a):
    if i%100 == 0:
        print idx
    idx = idx+1

Sortie du code ci-dessus :

4
9
10
13
14
15

Answer 1

Au cas où les gens seraient curieux, j'ai comparé la technique de compréhension du dict avec la technique d'itération en arrière. La compréhension du dict est environ deux fois plus rapide. En passant à OrderedDict a entraîné un ralentissement MASSIF. Environ 15x plus lent que la compréhension de la dictée.

def test1():
    a = [77,98,99,100,101,102,198,199,200,200,278,299,300,300,300]
    max_index = {}
    for i, item in enumerate(a[::-1]):
        if item not in max_index:
            max_index[item] = len(a) - (i + 1)
    return max_index

def test2():
    a = [77,98,99,100,101,102,198,199,200,200,278,299,300,300,300]
    return {item: index for index, item in enumerate(a, 1)}

def test3():
    a = [77,98,99,100,101,102,198,199,200,200,278,299,300,300,300]
    OrderedDict((item, index) for index, item in enumerate(a, 1))

if __name__ == "__main__":
    import timeit
    print(timeit.timeit("test1()", setup="from __main__ import test1"))
    print(timeit.timeit("test2()", setup="from __main__ import test2"))
    print(timeit.timeit("test3()", setup="from __main__ import test3; from collections import OrderedDict"))

3.40622282028
1.97545695305
26.347012043

Answer 2

Utilisez un simple dict-compréhension ou OrderedDict avec des éléments divisibles comme clés, les anciennes valeurs seront remplacées par les plus récentes automatiquement.

>>> {item: index for index, item in enumerate(lst, 1) if not item % 100}.values()
dict_values([4, 10, 15])

# if order matters
>>> from collections import OrderedDict    
>>> OrderedDict((item, index) for index, item in enumerate(lst, 1) if not item % 100).values()
odict_values([4, 10, 15])

Une autre façon sera de boucler sur la liste inversée et d'utiliser un set pour garder la trace des éléments vus jusqu'à présent( lst[::-1] peut être légèrement plus rapide que reversed(lst) pour les petites listes).

>>> seen = set()
>>> [len(lst) - index for index, item in enumerate(reversed(lst))
        if not item % 100 and item not in seen and not seen.add(item)][::-1]
[4, 10, 15]

Vous pouvez voir le code équivalent de ce qui précède aquí .

Answer 3

Vous podría utilice itertools.groupby puisque vos données sont triées :

>>> a = [77,98,99,100,101,102,198,199,200,200,278,299,300,300,300]
>>> from itertools import groupby
>>> [list(g)[-1][0] for k,g in groupby(enumerate(a), lambda t: (t[1] % 100, t[1])) if k[0] == 0]
[3, 9, 14]

Bien que ce soit un peu cryptique.

Voici une approche compliquée utilisant uniquement un itérateur de liste et l'accumulation dans une liste :

>>> run, prev, idx = False, None, []
>>> for i, e in enumerate(a):
...     if not (e % 100 == 0):
...         if not run:
...             prev = e
...             continue
...         idx.append(i - 1)
...         run = False
...     else:
...         if prev != e and run:
...             idx.append(i - 1)
...         run = True
...     prev = e
...
>>> if run:
...     idx.append(i)
...
>>> idx
[3, 9, 14]

Je pense qu'il est préférable d'utiliser une approche par dictionnaire comme celle de @AshwiniChaudhary. C'est plus simple et beaucoup plus rapide :

>>> timeit.timeit("{item: index for index, item in enumerate(a, 1)}", "from __main__ import a")
1.842843743012054
>>> timeit.timeit("[list(g)[-1][0] for k,g in groupby(enumerate(a), lambda t: (t[1] % 100, t[1])) if k[0] == 0]", "from __main__ import a, groupby")
8.479677081981208

Le site groupby est assez lente, notez que l'approche compliquée est plus rapide, et pas très éloignée de l'approche dict-compréhension :

>>> def complicated(a):
...     run, prev, idx = False, None, []
...     for i, e in enumerate(a):
...         if not (e % 100 == 0):
...             if not run:
...                 prev = e
...                 continue
...             idx.append(i - 1)
...             run = False
...         else:
...             if prev != e and run:
...                 idx.append(i - 1)
...             run = True
...         prev = e
...     if run:
...         idx.append(i)
...     return idx
...
>>> timeit.timeit("complicated(a)", "from __main__ import a, complicated")
2.6667005629860796

Editar

Notez que la différence de performance se réduit si nous appelons list sur le dict-compréhension .values() :

>>> timeit.timeit("list({item: index for index, item in enumerate(a, 1)}.values())", "from __main__ import a")
2.3839886570058297
>>> timeit.timeit("complicated(a)", "from __main__ import a, complicated")
2.708565960987471

Answer 4

Ça semblait être une bonne idée au départ, mais c'est devenu un peu tordu, j'ai dû corriger quelques cas...

a = [0,77,98,99,100,101,102,198,199,200,200,278,299,300,300,300, 459, 700,700]

bz = [*zip(*((i, d//100) for i, d in enumerate(a) if d%100 == 0 and d != 0))]
[a for a, b, c in zip(*bz, bz[1][1:]) if c-b != 0] + [bz[0][-1]]    

Out[78]: [4, 10, 15, 18]  

énumérer, zip à créer bz qui associe le(s) numérateur(s) de 100 aux indices

bz = [*zip(*((i, d//100) for i, d in enumerate(a) if d%100 == 0 and d != 0))]
print(*bz, sep='\n')
(4, 9, 10, 13, 14, 15, 17, 18)
(1, 2, 2, 3, 3, 3, 7, 7)

puis refermez, zip(*bz, bz[1][1:]) décalage du tuple du numérateur pour permettre à la différence décalée de donner une logique de sélection. if c-b != 0 pour le dernier indice de chaque cycle mais le dernier

ajouter le match des 100 dernières années parce que c'est toujours la fin de la dernière série. + [bz[0][-1]]