Python- encuentra el elemento con el máximo de ocurrencias en una lista

En Python, tengo una lista:

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

Quiero identificar el artículo que ocurrió la mayor cantidad de veces. Soy capaz de resolverlo pero necesito la forma más rápida de hacerlo. Sé que hay una buena respuesta pythonica a esto.

Aquí hay una solución defaultdict que funcionará con las versiones 2.5 y superiores de Python:

 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 

Note si L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 7, 7, 7, 7, 7, 56, 6, 7, 67] entonces hay seis 4s y seis 7s. Sin embargo, el resultado será (4, 6) es decir, seis 4s.

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

Para versiones anteriores de Python (<2.7), puede utilizar esta receta para obtener la clase Counter .

Me sorprende que nadie haya mencionado la solución más simple, max() con la lista de teclas.

 max(lst,key=lst.count) 

Ejemplo:

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

Esto funciona en Python 3 o 2, pero tenga en cuenta que solo devuelve el elemento más frecuente y no también la frecuencia. Además, en el caso de un sorteo (es decir, un artículo conjunto más frecuente) solo se devuelve un solo artículo.

Aunque la complejidad de tiempo de usar max() es peor que usar Counter.most_common(1) como comentarios de PM 2Ring , el enfoque se beneficia de una implementación rápida de C y creo que este enfoque es más rápido para listas cortas pero más lento para las más grandes tiempos mostrados en 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 

En tu pregunta, pediste la forma más rápida de hacerlo. Como se ha demostrado repetidamente, particularmente con Python, la intuición no es una guía confiable: usted necesita medir.

Aquí hay una prueba simple de varias implementaciones diferentes:

 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) 

Los resultados en mi máquina:

 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 

Así que parece que la solución de Counter no es la más rápida. Y, en este caso al menos, groupby es más rápido. defaultdict es bueno pero pagas un poco por su conveniencia; Es un poco más rápido usar un dict regular con un get .

¿Qué pasa si la lista es mucho más grande? Agregando L *= 10000 a la prueba anterior y reduciendo la cuenta de repetición a 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 

Ahora defaultdict es el claro ganador. Entonces, tal vez el costo del método ‘obtener’ y la pérdida de la sum en el lugar se sumn (se deja un examen del código generado como ejercicio).

Pero con los datos de prueba modificados, la cantidad de valores de elementos únicos no cambió, por lo que presumiblemente dict y defaultdict tienen una ventaja sobre las otras implementaciones. Entonces, ¿qué sucede si utilizamos la lista más grande pero aumentamos sustancialmente el número de elementos únicos? Reemplazando la inicialización de L con:

 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 

Así que ahora Counter es claramente más rápido que las soluciones groupby , pero aún más lento que las versiones de iteritems de dict y defaultdict .

El punto de estos ejemplos no es producir una solución óptima. El punto es que a menudo no hay una solución general óptima. Además, hay otros criterios de rendimiento. Los requisitos de memoria diferirán sustancialmente entre las soluciones y, a medida que aumenta el tamaño de la entrada, los requisitos de memoria pueden convertirse en el factor principal en la selección de algoritmos.

En pocas palabras: todo depende y usted necesita medir.

Quizás el método most_common ()

groupby los mejores resultados con groupby del módulo itertools con esta función usando 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)) 

Salida:

 4 occurred 6 times which is the highest number of times 

Prueba con timeit desde el módulo timeit .

Usé este script para mi prueba con el 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)) 

Salida (La mejor):

 0.1893607140000313 

Una forma sencilla sin bibliotecas ni conjuntos.

 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 

Quiero incluir otra solución que se vea bien y que sea rápida para listas cortas .

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

Puede comparar esto con el código proporcionado por Ned Deily, que le dará estos resultados para el caso de prueba más pequeño:

 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 

¡Pero cuidado, es ineficiente y, por lo tanto, se vuelve muy lento para listas grandes!

A continuación se presenta la solución que se me ocurrió si hay varios caracteres en la cadena que tienen la frecuencia más alta.

 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) 

Entrada: “hola gente”

Salida:

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

la mayor frecuencia de ocurrencia: 3

Los personajes son:

 e l 

Puede algo como esto:

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

Código simple y mejor:

 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") 

Salida: 4 ocurre 6 veces