Python: Vérifiez les occurrences dans une liste par rapport à une valeur

Question

lst = [1,2,3,4,1] 

Je veux savoir 1 se produit deux fois dans cette liste, y at-il un moyen efficace de faire?

Answer 1

lst.count(1) retournerait le nombre de fois qu'il se produit. Si vous comptez compter des éléments dans une liste, O (n) est ce que vous obtiendrez.

La fonction générale de la liste est list.count(x) et renvoie le nombre de fois où x apparaît dans une liste. Voulez-vous savoir si chaque élément de la liste est unique?

Answer 2

len(set(lst)) == len(lst) 

Si 1 se produit plusieurs fois?

lst.count(1) > 1 

Notez que ce qui précède n'est pas une efficacité maximale, car il ne sera pas court-circuit - même si 1 se produit deux fois, il sera toujours compter le reste des événements. Si vous voulez qu'il court-circuite, vous devrez écrire quelque chose d'un peu plus compliqué.

Si l'élément premier se produit plusieurs fois?

lst[0] in lst[1:] 

Quelle est la fréquence de chaque élément?

import collections 
collections.Counter(lst) 

Quelque chose d'autre?

Answer 3

def valCount(lst): 
    res = {} 
    for v in lst: 
     try: 
      res[v] += 1 
     except KeyError: 
      res[v] = 1 
    return res 

u = [ x for x,y in valCount(lst).iteritems() if y > 1 ] 

Vous voyez maintenant toutes les valeurs qui apparaissent plusieurs fois.

Edit:

@katrielalex: Merci d'avoir signalé collections.Counter, dont je n'étais pas au courant auparavant. Il peut également être écrit de manière plus concise en utilisant un fichier collections.defaultdict, comme démontré dans les tests suivants. Les trois méthodes sont approximativement O (n) et raisonnablement proches dans les performances d'exécution (en utilisant collections.defaultdict est en fait légèrement plus rapide que collections.Counter).

Mon intention était de donner une réponse facile à comprendre pour ce qui semblait une requête relativement peu sophistiquée. Compte tenu de cela, y a-t-il d'autres sens dans lesquels vous considérez que c'est «mauvais code» ou «mal fait»?

import collections 
import random 
import time 

def test1(lst): 
    res = {} 
    for v in lst: 
     try: 
      res[v] += 1 
     except KeyError: 
      res[v] = 1 
    return res 

def test2(lst): 
    res = collections.defaultdict(lambda: 0) 
    for v in lst: 
     res[v] += 1 
    return res 

def test3(lst): 
    return collections.Counter(lst) 

def rndLst(lstLen): 
    r = random.randint 
    return [r(0,lstLen) for i in xrange(lstLen)] 

def timeFn(fn, *args): 
    st = time.clock() 
    res = fn(*args) 
    return time.clock() - st 

def main(): 
    reps = 5000 

    res = [] 
    tests = [test1, test2, test3] 

    for t in xrange(reps): 
     lstLen = random.randint(10,50000) 
     lst = rndLst(lstLen) 
     res.append([lstLen] + [timeFn(fn, lst) for fn in tests]) 

    res.sort() 
    return res 

Et les résultats, pour les listes aléatoires contenant jusqu'à 50.000 articles, sont les suivants: (axe vertical est le temps en secondes, l'axe horizontal est le nombre d'éléments de la liste)

Answer 4

Une autre façon pour obtenir tous les éléments qui se produisent plus d'une fois:

lst = [1,2,3,4,1] 
d = {} 
for x in lst: 
    d[x] = x in d 
print d[1] # True 
print d[2] # False 
print [x for x in d if d[x]] # [1] 

Answer 5

pour plusieurs occurrences, cela vous donne l'index de chaque occurence:

>>> lst=[1,2,3,4,5,1] 
>>> tgt=1 
>>> found=[] 
>>> for index, suspect in enumerate(lst): 
...  if(tgt==suspect): 
...  found.append(index) 
... 
>>> print len(found), "found at index:",", ".join(map(str,found)) 
2 found at index: 0, 5 

Si vous voulez que le nombre de chaque élément dans la liste:

>>> lst=[1,2,3,4,5,2,2,1,5,5,5,5,6] 
>>> count={} 
>>> for item in lst: 
...  count[item]=lst.count(item) 
... 
>>> count 
{1: 2, 2: 3, 3: 1, 4: 1, 5: 5, 6: 1} 

Answer 6

Vous pouvez également trier la liste qui est O (n * log (n)), puis vérifier les éléments adjacents pour l'égalité, qui est O (n). Le résultat est O (n * log (n)). Cela a l'inconvénient d'exiger que toute la liste soit triée avant d'être éventuellement recouverte lorsqu'un doublon est trouvé.

Pour une grande liste avec des doublons relativement rares, cela pourrait être le meilleur que vous pouvez faire. La meilleure façon d'aborder cela dépend vraiment de la taille des données impliquées et de leur nature.