Trouver l'indice du nième élément d'une liste

Question

Je veux trouver l'indice de la n'ième occurrence d'un élément dans une liste, par exemple,

x=[False,True,True,False,True,False,True,False,False,False,True,False,True]

Quel est l'indice du nième vrai ? Si je veux la cinquième occurrence (la quatrième si l'indexation est nulle), la réponse est 10.

J'ai trouvé :

indargs = [ i for i,a in enumerate(x) if a ]
indargs[n]

Notez que x.index renvoie la première occurrence ou la première occurrence après un certain point, et donc, pour autant que je sache, ce n'est pas une solution.

Il existe également une solution dans numpy pour les cas similaires à ceux mentionnés ci-dessus, par exemple en utilisant cumsum et where mais j'aimerais savoir s'il existe un moyen sans numpy de résoudre le problème.

Je suis préoccupé par les performances car j'ai rencontré ce problème pour la première fois lors de l'implémentation d'un tamis d'Eratosthenes pour un problème du projet Euler, mais il s'agit d'une question plus générale que j'ai rencontrée dans d'autres situations.

EDIT : J'ai reçu beaucoup de bonnes réponses, alors j'ai décidé de faire quelques tests de performance. Voici les résultats timeit temps d'exécution en secondes pour les listes avec len nements à la recherche du 4000/1000ème Vrai. Les listes sont des Vrais/Faux aléatoires. Le code source est lié ci-dessous ; c'est un peu désordonné. J'ai utilisé des versions courtes / modifiées des noms des posters pour décrire les fonctions, à l'exception de listcomp qui est la compréhension de la liste simple ci-dessus.

True Test (100'th True in a list containing True/False)
         nelements      eyquem_occur eyquem_occurrence            graddy            taymon          listcomp       hettinger26         hettinger
             3000:          0.007824          0.031117          0.002144          0.007694          0.026908          0.003563          0.003563
            10000:          0.018424          0.103049          0.002233          0.018063          0.088245          0.003610          0.003769
            50000:          0.078383          0.515265          0.002140          0.078074          0.442630          0.003719          0.003608
           100000:          0.152804          1.054196          0.002129          0.152691          0.903827          0.003741          0.003769
           200000:          0.303084          2.123534          0.002212          0.301918          1.837870          0.003522          0.003601
True Test (1000'th True in a list containing True/False)
         nelements      eyquem_occur eyquem_occurrence            graddy            taymon          listcomp       hettinger26         hettinger
             3000:          0.038461          0.031358          0.024167          0.039277          0.026640          0.035283          0.034482
            10000:          0.049063          0.103241          0.024120          0.049383          0.088688          0.035515          0.034700
            50000:          0.108860          0.516037          0.023956          0.109546          0.442078          0.035269          0.035373
           100000:          0.183568          1.049817          0.024228          0.184406          0.906709          0.035135          0.036027
           200000:          0.333501          2.141629          0.024239          0.333908          1.826397          0.034879          0.036551
True Test (20000'th True in a list containing True/False)
         nelements      eyquem_occur eyquem_occurrence            graddy            taymon          listcomp       hettinger26         hettinger
             3000:          0.004520          0.004439          0.036853          0.004458          0.026900          0.053460          0.053734
            10000:          0.014925          0.014715          0.126084          0.014864          0.088470          0.177792          0.177716
            50000:          0.766154          0.515107          0.499068          0.781289          0.443654          0.707134          0.711072
           100000:          0.837363          1.051426          0.501842          0.862350          0.903189          0.707552          0.706808
           200000:          0.991740          2.124445          0.498408          1.008187          1.839797          0.715844          0.709063
Number Test (750'th 0 in a list containing 0-9)
         nelements      eyquem_occur eyquem_occurrence            graddy            taymon          listcomp       hettinger26         hettinger
             3000:          0.026996          0.026887          0.015494          0.030343          0.022417          0.026557          0.026236
            10000:          0.037887          0.089267          0.015839          0.040519          0.074941          0.026525          0.027057
            50000:          0.097777          0.445236          0.015396          0.101242          0.371496          0.025945          0.026156
           100000:          0.173794          0.905993          0.015409          0.176317          0.762155          0.026215          0.026871
           200000:          0.324930          1.847375          0.015506          0.327957          1.536012          0.027390          0.026657

La solution itertools de Hettinger est presque toujours la meilleure. Les solutions de taymon et de graddy sont ensuite les meilleures dans la plupart des situations, bien que l'approche de compréhension de liste puisse être meilleure pour les tableaux courts lorsque vous voulez la nième instance telle que n est élevé ou des listes dans lesquelles il y a moins de n occurrences. S'il y a une chance qu'il y ait moins de n occurrences, la solution initiale de count Le contrôle permet de gagner du temps. De plus, la solution de Grady est plus efficace lorsqu'elle recherche des nombres au lieu de Vrai/Faux... on ne sait pas trop pourquoi. Les solutions d'eyquem sont essentiellement équivalentes à d'autres avec un peu plus ou moins de surcharge ; eyquem_occur est approximativement la même que la solution de Taymon, alors que eyquem_occurrence est similaire à listcomp.

Answer 1

La réponse de @Taymon utilisant liste.index était génial.

Pour info, voici une approche fonctionnelle qui utilise la fonction module itertools . Il fonctionne avec toute entrée itérable, pas seulement les listes :

>>> from itertools import compress, count, imap, islice
>>> from functools import partial
>>> from operator import eq

>>> def nth_item(n, item, iterable):
        indicies = compress(count(), imap(partial(eq, item), iterable))
        return next(islice(indicies, n, None), -1)

Cet exemple est intéressant car il montre comment combiner efficacement les outils fonctionnels de Python. Notez qu'une fois que le pipeline est mis en place, il n'y a pas de voyage autour de la boucle d'évaluation de Python - tout est fait à la vitesse du C, avec une empreinte mémoire minuscule, avec une évaluation paresseuse, sans assignation de variable, et avec des composants testables séparément. Autrement dit, c'est tout ce dont rêvent les programmeurs fonctionnels :-)

Exemple d'exécution :

>>> x = [False,True,True,False,True,False,True,False,False,False,True,False,True]
>>> nth_item(50, True, x)
-1
>>> nth_item(0, True, x)
1
>>> nth_item(1, True, x)
2
>>> nth_item(2, True, x)
4
>>> nth_item(3, True, x)
6

Answer 2

Je ne peux pas dire avec certitude que c'est le moyen le plus rapide, mais j'imagine que c'est assez bon :

i = -1
for j in xrange(n):
    i = x.index(True, i + 1)

La réponse est i .

Answer 3

Si l'efficacité est un souci, je pense qu'il est préférable d'itérer normalement (O(N)) plutôt que de comprendre une liste, ce qui prend O(L), où L est la longueur de la liste.

Exemple : Considérez une très grande liste et vous voulez trouver la première occurrence N=1, il est évidemment préférable d'arrêter dès que vous trouvez la première occurrence.

count = 0
for index,i in enumerate(L):
    if i:
        count = count + 1
        if count==N:
            return index

Answer 4

Si vous êtes préoccupé par les performances, il est préférable de voir s'il est possible d'effectuer des optimisations algorithmiques. Par exemple, si vous appelez cette fonction plusieurs fois sur les mêmes valeurs, vous pouvez mettre en cache les calculs précédents (par exemple, une fois que vous avez trouvé la 50e occurrence d'un élément, vous pouvez trouver toutes les occurrences précédentes dans le fichier O(1) temps).

Sinon, vous devez vous assurer que votre technique fonctionne sur les itérateurs (paresseux).

Les plus * sur *La manière la plus élégante et la plus performante à laquelle je pense pour l'implémenter est la suivante :

def indexOfNthOccurrence(N, element, stream):
    """for N>0, returns index or None"""
    seen = 0
    for i,x in enumerate(stream):
        if x==element:
            seen += 1
            if seen==N:
                return i

(si vous vous souciez vraiment de la différence de performance entre enumerate et les autres techniques, vous devrez recourir au profilage, en particulier avec les fonctions numpy, qui peuvent recourir au C)

Pour prétraiter l'ensemble du flux et soutenir O(1) des requêtes :

from collections import *
cache = defaultdict(list)
for i,elem in enumerate(YOUR_LIST):
    cache[elem] += [i]

# e.g. [3,2,3,2,5,5,1]
#       0 1 2 3 4 5 6
# cache: {3:[0,2], 1:[6], 2:[1,3], 5:[4,5]}

Answer 5

[y for y in enumerate(x) if y[1]==True][z][0]

Note : Ici, Z est la nième occurrence,