Python - trouver l'élément avec un maximum d'occurrences dans une liste

En Python, j'ai une liste:

L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]

Je tiens à identifier l'élément qui s'est produite le plus grand nombre de fois. Je suis en mesure de résoudre le problème, mais j'ai besoin de la manière la plus rapide de le faire. Je sais que c'est une belle Pythonic réponse à cette question.

  • Vous dites que vous êtes en mesure de le résoudre. Il serait d'enseignement pour d'autres si vous pouvez fournir votre propre solution en tant que point de départ.
InformationsquelleAutor zubinmehta | 2011-08-08
  1. 14

    Ici est un defaultdict solution qui fonctionne avec les versions de Python 2.5 et supérieur:

    from collections import defaultdict

L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
d = defaultdict(int)
for i in L:
    d[i] += 1
result = max(d.iteritems(), key=lambda x: x[1])
print result
# (4, 6)
# The number 4 occurs 6 times

    Remarque si L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 7, 7, 7, 7, 7, 56, 6, 7, 67]
    ensuite, il y a six 4s et six 7s. Toutefois, le résultat sera (4, 6) c'est à dire six 4s.

    InformationsquelleAutor Andrew Clark
  2. 96
    from collections import Counter
most_common,num_most_common = Counter(L).most_common(1)[0] # 4, 6 times

    Pour les anciennes versions de Python (< 2.7), vous pouvez utiliser cette recette pour obtenir le Compteur classe.

    • Voir le Compteur docs pour plus de détails.
    • Cette solution est vraiment élégant, mais à l'heure actuelle, l'autre a travaillé pour moi.
    InformationsquelleAutor phihag
  3. 68

    Je suis surpris que personne n'a mentionné la solution la plus simple,max() avec la clé list.count:

    max(lst,key=lst.count)

    Exemple:

    >>> lst = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
>>> max(lst,key=lst.count)
4

    Cela fonctionne en Python 3 ou 2, mais notez qu'il ne retourne la plus fréquente de l'élément et non pas la fréquence. Aussi, dans le cas d'un tirage (c'est à dire articulaires les plus fréquentes de l'élément) un seul élément est retourné.

    Bien que le temps de la complexité de l'utilisation de max() est pire que d'utiliser Counter.most_common(1) comme PM 2Ring commentaires, l'approche bénéficie d'un rapide C la mise en œuvre et je trouve cette approche est plus rapide pour de courtes listes, mais plus lente pour les plus grands (Python 3.6 timings indiqués dans IPython 5.3):

    In [1]: from collections import Counter
   ...: 
   ...: def f1(lst):
   ...:     return max(lst, key = lst.count)
   ...: 
   ...: def f2(lst):
   ...:     return Counter(lst).most_common(1)
   ...: 
   ...: lst0 = [1,2,3,4,3]
   ...: lst1 = lst0[:] * 100
   ...: 

In [2]: %timeit -n 10 f1(lst0)
10 loops, best of 3: 3.32 us per loop

In [3]: %timeit -n 10 f2(lst0)
10 loops, best of 3: 26 us per loop

In [4]: %timeit -n 10 f1(lst1)
10 loops, best of 3: 4.04 ms per loop

In [5]: %timeit -n 10 f2(lst1)
10 loops, best of 3: 75.6 us per loop
    • très bon et solution optimisée
    • Je voudrais une explication sur la façon max fonctionne avec key=
    • C'est un peu inefficace, puisque .count a pour numériser l'ensemble de la liste pour chaque élément, rendant O(n2).
    • Counter est commode, mais il n'est pas connu pour la vitesse. Et quand n est relativement petit O(n2) peut être assez bon quand vous êtes à l'aide d'une fonction / méthode qui fonctionne à C de vitesse. Mais quand n est assez grand, les choses peuvent devenir laid, comme je l'ai discuter ici.
    • Édité ma réponse et les horaires, merci encore
    • C'est une grande réponse, exactement ce dont j'avais besoin et des points bonus pour les horaires! J'essayais de trouver rapidement les valeurs aberrantes de la classe dans une sortie de tensorflow.contrib.la factorisation.KMeansClustering(). La sortie de la liste(kmeans.predict_cluster_index(input_fn)) est une matrice comportant pas de fonctions d'aide à l'accès au cluster avec le plus haut nombre d'occurrences.
    • lst = [[1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67],[1, 2, 45, 55, 5, 5, 5]] max(lst,key=lst.count) dans l'exemple ci-dessus son retour m'première liste, mais je tiens résultat comme [[4],[5]]

    InformationsquelleAutor Chris_Rands
  4. 27

    Dans votre question, vous avez demandé de la manière la plus rapide de le faire. Comme cela a été démontré à maintes reprises, en particulier avec Python, l'intuition n'est pas un guide fiable: vous avez besoin de mesurer.

    Voici un test simple de plusieurs implémentations différentes:

    import sys
from collections import Counter, defaultdict
from itertools import groupby
from operator import itemgetter
from timeit import timeit
L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
def max_occurrences_1a(seq=L):
"dict iteritems"
c = dict()
for item in seq:
c[item] = c.get(item, 0) + 1
return max(c.iteritems(), key=itemgetter(1))
def max_occurrences_1b(seq=L):
"dict items"
c = dict()
for item in seq:
c[item] = c.get(item, 0) + 1
return max(c.items(), key=itemgetter(1))
def max_occurrences_2(seq=L):
"defaultdict iteritems"
c = defaultdict(int)
for item in seq:
c[item] += 1
return max(c.iteritems(), key=itemgetter(1))
def max_occurrences_3a(seq=L):
"sort groupby generator expression"
return max(((k, sum(1 for i in g)) for k, g in groupby(sorted(seq))), key=itemgetter(1))
def max_occurrences_3b(seq=L):
"sort groupby list comprehension"
return max([(k, sum(1 for i in g)) for k, g in groupby(sorted(seq))], key=itemgetter(1))
def max_occurrences_4(seq=L):
"counter"
return Counter(L).most_common(1)[0]
versions = [max_occurrences_1a, max_occurrences_1b, max_occurrences_2, max_occurrences_3a, max_occurrences_3b, max_occurrences_4]
print sys.version, "\n"
for vers in versions:
print vers.__doc__, vers(), timeit(vers, number=20000)

    Les résultats sur ma machine:

    2.7.2 (v2.7.2:8527427914a2, Jun 11 2011, 15:22:34) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] 
dict iteritems (4, 6) 0.202214956284
dict items (4, 6) 0.208412885666
defaultdict iteritems (4, 6) 0.221301078796
sort groupby generator expression (4, 6) 0.383440971375
sort groupby list comprehension (4, 6) 0.402786016464
counter (4, 6) 0.564319133759

    Il semble donc que la Counter solution n'est pas la plus rapide. Et, dans ce cas au moins, groupby est plus rapide. defaultdict est bon, mais vous payer un peu pour sa commodité; il est légèrement plus rapide à utiliser régulièrement dict avec un get.

    Ce qui se passe si la liste est beaucoup plus grand? L'ajout de L *= 10000 pour le test ci-dessus et en réduisant le nombre de répétitions à 200:

    dict iteritems (4, 60000) 10.3451900482
dict items (4, 60000) 10.2988479137
defaultdict iteritems (4, 60000) 5.52838587761
sort groupby generator expression (4, 60000) 11.9538850784
sort groupby list comprehension (4, 60000) 12.1327362061
counter (4, 60000) 14.7495789528

    Maintenant defaultdict est le gagnant clair. Alors peut-être que le coût de la 'get' de la méthode et de la perte de la place ajouter ajoute (examen du code généré est laissée en exercice).

    Mais avec la modification des données de test, le nombre de valeurs n'ont pas changé donc vraisemblablement dict et defaultdict ont un avantage sur les autres implémentations. Donc ce qui arrive si nous utilisons la plus grande liste, mais d'accroître considérablement le nombre d'éléments uniques? Le remplacement de l'initialisation de L avec:

    LL = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
L = []
for i in xrange(1,10001):
L.extend(l * i for l in LL)
dict iteritems (2520, 13) 17.9935798645
dict items (2520, 13) 21.8974409103
defaultdict iteritems (2520, 13) 16.8289561272
sort groupby generator expression (2520, 13) 33.853593111
sort groupby list comprehension (2520, 13) 36.1303369999
counter (2520, 13) 22.626899004

    Alors maintenant Counter est clairement plus rapide que la groupby des solutions, mais encore plus lent que le iteritems versions de dict et defaultdict.

    Le point de ces exemples n'est pas de produire une solution optimale. Le point est qu'il n'est pas souvent un optimale de la solution générale. Plus il y a d'autres critères de performance. Les besoins en mémoire diffèrent considérablement entre les solutions et, comme la taille de l'entrée de monte, les besoins en mémoire peut devenir le facteur prépondérant dans la sélection d'un algorithme.

    Bas de ligne: tout dépend de la situation et vous avez besoin de mesurer.

    • C'est une fantastique réponse, grand fan de temps-alternatives à l'expérimentation pour la solution. Merci Ned.
    InformationsquelleAutor Ned Deily
  5. 2

    Peut-être le most_common() méthode

    InformationsquelleAutor Danny
  6. 1

    J'ai obtenu les meilleurs résultats avec groupby de itertools module de cette fonction à l'aide de Python 3.5.2:

    from itertools import groupby
a = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
def occurrence():
occurrence, num_times = 0, 0
for key, values in groupby(a, lambda x : x):
val = len(list(values))
if val >= occurrence:
occurrence, num_times =  key, val
return occurrence, num_times
occurrence, num_times = occurrence()
print("%d occurred %d times which is the highest number of times" % (occurrence, num_times))

    De sortie:

    4 occurred 6 times which is the highest number of times

    Test avec timeit de timeit module.

    J'ai utilisé ce script pour mon test avec number= 20000:

    from itertools import groupby
def occurrence():
a = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
occurrence, num_times = 0, 0
for key, values in groupby(a, lambda x : x):
val = len(list(values))
if val >= occurrence:
occurrence, num_times =  key, val
return occurrence, num_times
if __name__ == '__main__':
from timeit import timeit
print(timeit("occurrence()", setup = "from __main__ import occurrence",  number = 20000))

    De sortie (Le meilleur):

    0.1893607140000313
    InformationsquelleAutor Chiheb Nexus
  7. 1

    Une façon simple, sans bibliothèques ou des ensembles

    def mcount(l):
n = []                  #To store count of each elements
for x in l:
count = 0
for i in range(len(l)):
if x == l[i]:
count+=1
n.append(count)
a = max(n)              #largest in counts list
for i in range(len(n)):
if n[i] == a:
return(l[i],a)  #element,frequency
return                  #if something goes wrong
    InformationsquelleAutor Prashanth ram
  8. 0

    Je veux jeter dans une autre solution qui a l'air sympa et rapide pour les court listes.

    def mc(seq=L):
"max/count"
max_element = max(seq, key=seq.count)
return (max_element, seq.count(max_element))

    Vous pouvez mesurer cela avec le code fourni par Ned Deily qui va vous donner ces résultats pour les plus petits des cas de test:

    3.5.2 (default, Nov  7 2016, 11:31:36) 
[GCC 6.2.1 20160830] 
dict iteritems (4, 6) 0.2069783889998289
dict items (4, 6) 0.20462976200065896
defaultdict iteritems (4, 6) 0.2095775119996688
sort groupby generator expression (4, 6) 0.4473949929997616
sort groupby list comprehension (4, 6) 0.4367636879997008
counter (4, 6) 0.3618192010007988
max/count (4, 6) 0.20328268999946886

    Mais attention, il est inefficace et obtient ainsi vraiment lent pour les grandes listes!

    InformationsquelleAutor dd23
  9. 0

    Suivante est la solution que j'ai trouvé avec s'il y a plusieurs caractères dans la chaîne tout en ayant la fréquence la plus élevée.

    mystr = input("enter string: ")
#define dictionary to store characters and their frequencies
mydict = {}
#get the unique characters
unique_chars = sorted(set(mystr),key = mystr.index)
#store the characters and their respective frequencies in the dictionary
for c in unique_chars:
ctr = 0
for d in mystr:
if d != " " and d == c:
ctr = ctr + 1
mydict[c] = ctr
print(mydict)
#store the maximum frequency
max_freq = max(mydict.values())
print("the highest frequency of occurence: ",max_freq)
#print all characters with highest frequency
print("the characters are:")
for k,v in mydict.items():
if v == max_freq:
print(k)

    D'entrée: "bonjour les gens"

    De sortie:

    {'o': 2, 'p': 2, 'h': 1, ' ': 0, 'e': 3, 'l': 3}

    la plus haute fréquence d'occurence: 3

    les personnages sont:

    e
l
    InformationsquelleAutor Arko
  10. 0

    Simple et le meilleur code: 

    def max_occ(lst,x):
count=0
for i in lst:
if (i==x):
count=count+1
return count
lst=[1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
x=max(lst,key=lst.count)
print(x,"occurs ",max_occ(lst,x),"times")

    De sortie: 4 apparaît 6 fois

    InformationsquelleAutor Ranjith M
  11. 0

    Mon (tout simplement) code (de trois mois à étudier Python):

    def more_frequent_item(lst):
new_lst = []
times = 0
for item in lst:
count_num = lst.count(item)
new_lst.append(count_num)
times = max(new_lst)
key = max(lst, key=lst.count)
print("In the list: ")
print(lst)
print("The most frequent item is " + str(key) + ". Appears " + str(times) + " times in this list.")
more_frequent_item([1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67])

    La sortie sera:

    In the list: 
[1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
The most frequent item is 4. Appears 6 times in this list.
    InformationsquelleAutor Rentis
  12. -1

    peut quelque chose comme ceci:

    testList = [1, 2, 3, 4, 2, 2, 1, 4, 4]
    print(max(set(testList), key = testList.count))

    InformationsquelleAutor BreakBadSP