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

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 l' Counter classe.

je suis surpris que personne n'ait mentionné la solution la plus simple,max() avec la touche 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 renvoie que l'élément le plus fréquent et pas aussi la fréquence. Aussi, dans le cas d'un draw (c.-à-d. l'article le plus fréquent en commun) seul un article est retourné.

bien que la complexité temporelle de l'utilisation max() est pire que d'utiliser Counter.most_common(1) PM 2Ring les commentaires, l'approche bénéficie d'un rapide C mise en place 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

dans votre question, vous avez demandé le moyen le plus rapide de le faire. Comme cela a été démontré à plusieurs reprises, en particulier avec Python, l'intuition n'est pas un guide fiable: vous devez mesurer.

voici un simple test 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 mon ordinateur:

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 l' Counter la solution n'est pas la plus rapide. Et, dans ce cas au moins, groupby est plus rapide. defaultdict est bon mais vous payez un peu à sa convenance; il est légèrement plus rapide d'utiliser un dict avec un get.

Qu'advient-il si la liste est beaucoup plus grand? L'ajout d' 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

defaultdict est clairement le gagnant. Alors peut-être que le coût de la méthode " get " et la perte du inplace s'additionnent (un examen du code généré est laissé comme exercice).

mais avec les données d'essai modifiées, le nombre des valeurs uniques d'item n'ont pas changé donc probablement dict et defaultdict avoir un avantage sur les autres implémentations. Alors que se passe-t-il si nous utilisons la liste plus grande mais augmentons considérablement le nombre d'articles uniques? Remplacer l'initialisation de L Par:

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 nettement plus rapide que le groupby mais toujours plus lent que le iteritems versions de dict et defaultdict.

le but de ces exemples n'est pas de produire une solution optimale. Le fait est que souvent il n'y a pas solution générale optimale. Plus il y a d'autres critères de performance. Les besoins en mémoire diffèrent considérablement d'une solution à l'autre et, à mesure que la taille de l'entrée augmente, les besoins en mémoire peuvent devenir le facteur dominant dans le choix de l'algorithme.

conclusion: tout dépend et il faut mesurer.

peut-être le most_common () méthode

j'ai obtenu les meilleurs résultats avec groupbyitertools module avec cette fonction utilisant 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))

Sortie:

4 occurred 6 times which is the highest number of times

tester avec timeittimeit 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))

Sortie (Le meilleur):

0.1893607140000313

une manière simple sans bibliothèques ou sets

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

je veux ajouter une autre solution qui soit belle et rapide pour court listes.

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

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!

Voici la solution que j'ai trouvée s'il y a plusieurs caractères dans la chaîne tous 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)

Entrée: "bonjour les gens"

Sortie:

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

la fréquence la plus élevée d'occurence: 3

les personnages sont:

e

l

peut quelque chose comme ceci:

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