Python- encontrar el elemento con eventos máximo en una lista

Question

En Python, tengo una lista:

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

quiero para identificar el elemento que se ha producido el mayor número de veces. Puedo resolverlo, pero necesito la forma más rápida de hacerlo. Sé que hay una buena respuesta Pythonic a esto.

Answer 1

Aquí es una solución defaultdict que trabajará con versiones Python 2.5 y anteriores:

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 

Nota 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.

Answer 2

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

Para las versiones antiguas de Python (< 2.7), puede utilizar this receipe para obtener la clase Counter.

Answer 3

Quizás el most_common() método

Answer 4

En su pregunta, usted pidió 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: es necesario medir.

Aquí está 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 

lo que parece que la solución Counter no es el más rápido. 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 normal con un get.

¿Qué sucede si la lista es mucho más grande? La adición de L *= 10000 a la prueba anterior y reducir el número de repeticiones 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 del complemento en el lugar se suma (un examen del código generado se deja como un ejercicio).

Pero con los datos de prueba modificados, el número 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 la cantidad de artículos únicos? Sustitución de 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 iteritemsdict y defaultdict.

El objetivo de estos ejemplos no es producir una solución óptima. El punto es que a menudo no es uno solución general óptima. Además, hay otros criterios de rendimiento.Los requisitos de memoria variará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 primordial en la selección del algoritmo.

En pocas palabras: todo depende y usted necesita medir.

Answer 5

me sorprende que nadie ha mencionado la solución más simple, max() con la tecla list.count:

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 se solo devuelve el elemento más frecuente y no también la frecuencia. Además, en el caso de un dibuje (es decir, el elemento más común de unión), solo se devuelve un solo artículo.

encuentro el enfoque max() es aproximadamente dos veces más rápido que Counter.most_common(1):

from collections import Counter 
from timeit import timeit 

def f1(lst): 
    return max(lst, key = lst.count) 

def f2(lst): 
    return Counter(lst).most_common(1) 

lst = range(100000) 

timeit(lambda: f1(lst), number = 1000) 
# 28.13 
timeit(lambda: f2(lst), number = 1000) 
# 59.01 

Answer 6

obtuve los mejores resultados con groupby de itertools módulo con esta función utilizando 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 

Tes t con timeit del módulo timeit.

que utiliza este script para mi prueba con 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 salida (el mejor):

0.1893607140000313 

Answer 7

quiero lanzar en otra solución que se ve bien y es rápido para corto listas.

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

Se pueden 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 realmente lenta para listas grandes!

Answer 8

La siguiente es la solución que se me ocurrió si hay múltiples 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) 

de entrada: "Hola gente"

Salida:

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

la mayor frecuencia de aparición: 3

los personajes son:

e 

l