barplot - Python: encuentre el elemento con las ocurrencias máximas en una lista
pandas plot (10)
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. Puedo resolverlo, pero necesito la forma más rápida de hacerlo. Sé que hay una buena respuesta Pythonic a esto.
A continuación se encuentra la solución que surgió 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)
Entrada: "hola gente"
Salida:
{''o'': 2, ''p'': 2, ''h'': 1, '' '': 0, ''e'': 3, ''l'': 3}
la frecuencia más alta de ocurrencia: 3
Los personajes son:
e
l
Aquí hay una solución defaultdict
que funcionará con Python versiones 2.5 y superiores:
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
Observe si L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 7, 7, 7, 7, 7, 56, 6, 7, 67]
luego hay seis 4s y seis 7s. Sin embargo, el resultado será (4, 6)
es decir, seis 4s.
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í 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
Entonces parece que la solución 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? Agregar L *= 10000
a la prueba anterior y reducir el recuento 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 allí sobre las otras implementaciones. Entonces, ¿qué sucede si utilizamos la lista más grande pero aumentamos sustancialmente la cantidad de artículos ú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 groupby
soluciones, pero aún más lento que las versiones iteritems
de dict
y defaultdict
.
El objetivo 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 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 necesitas medir.
Me sorprende que nadie haya mencionado la solución más simple, max()
con la clave 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 solo devuelve el elemento más frecuente y no la frecuencia. Además, en el caso de un sorteo (es decir, el elemento más frecuente de la junta), solo se devuelve un solo artículo.
Aunque la complejidad temporal 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 encuentro que este enfoque es más rápido para listas cortas pero más lento para las más grandes (Python 3.6 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
Quiero agregar 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 compararlo con el código proporcionado por Ned Deily que le dará los 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 realmente lento para listas grandes!
Tal vez el método most_common()
Una forma simple sin bibliotecas o 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
puede algo como esto:
testList = [1, 2, 3, 4, 2, 2, 1, 4, 4] print(max(set(testList), key = testList.count))
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
.
Utilicé 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))
Salida (la mejor):
0.1893607140000313
from collections import Counter
most_common,num_most_common = Counter(L).most_common(1)[0] # 4, 6 times
Para las versiones anteriores de Python (<2.7), puede usar esta receta para obtener la clase de Counter
.