Encuentra el elemento más común en una lista

¿Cuál es una forma eficiente de encontrar el elemento más común en una lista de Python?

Es posible que los elementos de mi lista no se puedan compartir, así que no puedo usar un diccionario. También en caso de sorteos, se debe devolver el artículo con el índice más bajo. Ejemplo:

>>> most_common(['duck', 'duck', 'goose'])
'duck'
>>> most_common(['goose', 'duck', 'duck', 'goose'])
'goose'

Con tantas soluciones propuestas, me sorprende que nadie haya propuesto lo que yo consideraría obvio (para elementos no intercambiables pero comparables) - [ itertools.groupby] [1]. itertoolsofrece una funcionalidad rápida y reutilizable, y le permite delegar algunas lógicas difíciles a componentes de biblioteca estándar bien probados Considere por ejemplo:

import itertools
import operator

def most_common(L):
  # get an iterable of (item, iterable) pairs
  SL = sorted((x, i) for i, x in enumerate(L))
  # print 'SL:', SL
  groups = itertools.groupby(SL, key=operator.itemgetter(0))
  # auxiliary function to get "quality" for an item
  def _auxfun(g):
    item, iterable = g
    count = 0
    min_index = len(L)
    for _, where in iterable:
      count += 1
      min_index = min(min_index, where)
    # print 'item %r, count %r, minind %r' % (item, count, min_index)
    return count, -min_index
  # pick the highest-count/earliest item
  return max(groups, key=_auxfun)[0]

Esto podría escribirse de manera más concisa, por supuesto, pero estoy buscando la máxima claridad. Las dos printdeclaraciones pueden ser descomentadas para ver mejor la maquinaria en acción; por ejemplo, con impresiones sin comentar:

print most_common(['goose', 'duck', 'duck', 'goose'])

emite:

SL: [('duck', 1), ('duck', 2), ('goose', 0), ('goose', 3)]
item 'duck', count 2, minind 1
item 'goose', count 2, minind 0
goose

Como puede ver, SLes una lista de pares, cada par un elemento seguido del índice del elemento en la lista original (para implementar la condición clave de que, si los elementos "más comunes" con el mismo recuento más alto son> 1, el resultado debe ser el más temprano).

groupbyagrupa por el artículo solamente (vía operator.itemgetter). La función auxiliar, llamada una vez por agrupación durante el maxcálculo, recibe y desempaqueta internamente un grupo: una tupla con dos elementos (item, iterable)donde los elementos del iterable también son tuplas de dos elementos, (item, original index)[[los elementos de SL]].

Luego, la función auxiliar utiliza un bucle para determinar tanto el recuento de entradas en el iterable del grupo como el índice original mínimo; los devuelve como "clave de calidad" combinada, con el signo de índice mínimo cambiado para que la maxoperación considere "mejor" aquellos elementos que ocurrieron anteriormente en la lista original.

Este código podría ser mucho más simple si se preocupara un poco menos por los problemas de grandes O en el tiempo y el espacio, por ejemplo ...:

def most_common(L):
  groups = itertools.groupby(sorted(L))
  def _auxfun((item, iterable)):
    return len(list(iterable)), -L.index(item)
  return max(groups, key=_auxfun)[0]

misma idea básica, expresada de manera más simple y compacta ... pero, por desgracia, un espacio auxiliar O (N) adicional (para incorporar los iterables de los grupos a las listas) y el tiempo O (N al cuadrado) (para obtener el L.indexde cada elemento) . Si bien la optimización prematura es la raíz de todo mal en la programación, elegir deliberadamente un enfoque O (N cuadrado) cuando hay un O (N log N) disponible, ¡va demasiado en contra de la escalabilidad! -)

Finalmente, para aquellos que prefieren "oneliners" a la claridad y el rendimiento, una versión adicional de 1 línea con nombres adecuadamente destrozados :-).

from itertools import groupby as g
def most_common_oneliner(L):
  return max(g(sorted(L)), key=lambda(x, v):(len(list(v)),-L.index(x)))[0]

Una línea más simple:

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

Tomando prestado de aquí , esto se puede usar con Python 2.7:

from collections import Counter

def Most_Common(lst):
    data = Counter(lst)
    return data.most_common(1)[0][0]

Funciona entre 4 y 6 veces más rápido que las soluciones de Alex, y es 50 veces más rápido que el one-liner propuesto por newacct.

Para recuperar el elemento que aparece primero en la lista en caso de empate:

def most_common(lst):
    data = Counter(lst)
    return max(lst, key=data.get)

Lo que desea se conoce en estadísticas como modo, y Python, por supuesto, tiene una función incorporada para hacer exactamente eso por usted:

>>> from statistics import mode
>>> mode([1, 2, 2, 3, 3, 3, 3, 3, 4, 5, 6, 6, 6])
3

Tenga en cuenta que si no hay un "elemento más común", como los casos en que los dos primeros están empatados , esto aumentará StatisticsError, porque estadísticamente hablando, no hay modo en este caso.

Si no son intercambiables, puede ordenarlos y hacer un solo ciclo sobre el resultado contando los elementos (los elementos idénticos estarán uno al lado del otro). Pero podría ser más rápido hacerlos hashables y usar un dict.

def most_common(lst):
    cur_length = 0
    max_length = 0
    cur_i = 0
    max_i = 0
    cur_item = None
    max_item = None
    for i, item in sorted(enumerate(lst), key=lambda x: x[1]):
        if cur_item is None or cur_item != item:
            if cur_length > max_length or (cur_length == max_length and cur_i < max_i):
                max_length = cur_length
                max_i = cur_i
                max_item = cur_item
            cur_length = 1
            cur_i = i
            cur_item = item
        else:
            cur_length += 1
    if cur_length > max_length or (cur_length == max_length and cur_i < max_i):
        return cur_item
    return max_item

Esta es una solución O (n).

mydict   = {}
cnt, itm = 0, ''
for item in reversed(lst):
     mydict[item] = mydict.get(item, 0) + 1
     if mydict[item] >= cnt :
         cnt, itm = mydict[item], item

print itm

(se invierte para asegurarse de que devuelve el elemento de índice más bajo)

Sin el requisito sobre el índice más bajo, puede usar collections.Counterpara esto:

from collections import Counter

a = [1936, 2401, 2916, 4761, 9216, 9216, 9604, 9801] 

c = Counter(a)

print(c.most_common(1)) # the one most common element... 2 would mean the 2 most common
[(9216, 2)] # a set containing the element, and it's count in 'a'

Ordene una copia de la lista y encuentre la ejecución más larga. Puede decorar la lista antes de ordenarla con el índice de cada elemento, y luego elegir la ejecución que comienza con el índice más bajo en el caso de un empate.

Una frase:

def most_common (lst):
    return max(((item, lst.count(item)) for item in set(lst)), key=lambda a: a[1])[0]

# use Decorate, Sort, Undecorate to solve the problem

def most_common(iterable):
    # Make a list with tuples: (item, index)
    # The index will be used later to break ties for most common item.
    lst = [(x, i) for i, x in enumerate(iterable)]
    lst.sort()

    # lst_final will also be a list of tuples: (count, index, item)
    # Sorting on this list will find us the most common item, and the index
    # will break ties so the one listed first wins.  Count is negative so
    # largest count will have lowest value and sort first.
    lst_final = []

    # Get an iterator for our new list...
    itr = iter(lst)

    # ...and pop the first tuple off.  Setup current state vars for loop.
    count = 1
    tup = next(itr)
    x_cur, i_cur = tup

    # Loop over sorted list of tuples, counting occurrences of item.
    for tup in itr:
        # Same item again?
        if x_cur == tup[0]:
            # Yes, same item; increment count
            count += 1
        else:
            # No, new item, so write previous current item to lst_final...
            t = (-count, i_cur, x_cur)
            lst_final.append(t)
            # ...and reset current state vars for loop.
            x_cur, i_cur = tup
            count = 1

    # Write final item after loop ends
    t = (-count, i_cur, x_cur)
    lst_final.append(t)

    lst_final.sort()
    answer = lst_final[0][2]

    return answer

print most_common(['x', 'e', 'a', 'e', 'a', 'e', 'e']) # prints 'e'
print most_common(['goose', 'duck', 'duck', 'goose']) # prints 'goose'

Solución simple de una línea

moc= max([(lst.count(chr),chr) for chr in set(lst)])

Devolverá el elemento más frecuente con su frecuencia.

Probablemente ya no necesites esto, pero esto es lo que hice para un problema similar. (Parece más largo de lo que es debido a los comentarios).

itemList = ['hi', 'hi', 'hello', 'bye']

counter = {}
maxItemCount = 0
for item in itemList:
    try:
        # Referencing this will cause a KeyError exception
        # if it doesn't already exist
        counter[item]
        # ... meaning if we get this far it didn't happen so
        # we'll increment
        counter[item] += 1
    except KeyError:
        # If we got a KeyError we need to create the
        # dictionary key
        counter[item] = 1

    # Keep overwriting maxItemCount with the latest number,
    # if it's higher than the existing itemCount
    if counter[item] > maxItemCount:
        maxItemCount = counter[item]
        mostPopularItem = item

print mostPopularItem

Basándose en la respuesta de Luiz , pero satisfaciendo la condición " en caso de sorteos, se debe devolver el elemento con el índice más bajo ":

from statistics import mode, StatisticsError

def most_common(l):
    try:
        return mode(l)
    except StatisticsError as e:
        # will only return the first element if no unique mode found
        if 'no unique mode' in e.args[0]:
            return l[0]
        # this is for "StatisticsError: no mode for empty data"
        # after calling mode([])
        raise

Ejemplo:

>>> most_common(['a', 'b', 'b'])
'b'
>>> most_common([1, 2])
1
>>> most_common([])
StatisticsError: no mode for empty data

Aquí:

def most_common(l):
    max = 0
    maxitem = None
    for x in set(l):
        count =  l.count(x)
        if count > max:
            max = count
            maxitem = x
    return maxitem

Tengo la vaga sensación de que hay un método en algún lugar de la biblioteca estándar que le dará el recuento de cada elemento, pero no puedo encontrarlo.

Esta es la solución lenta obvia (O (n ^ 2)) si ni la clasificación ni el hashing son factibles, pero la comparación de igualdad ( ==) está disponible:

def most_common(items):
  if not items:
    raise ValueError
  fitems = [] 
  best_idx = 0
  for item in items:   
    item_missing = True
    i = 0
    for fitem in fitems:  
      if fitem[0] == item:
        fitem[1] += 1
        d = fitem[1] - fitems[best_idx][1]
        if d > 0 or (d == 0 and fitems[best_idx][2] > fitem[2]):
          best_idx = i
        item_missing = False
        break
      i += 1
    if item_missing:
      fitems.append([item, 1, i])
  return items[best_idx]

Pero hacer que sus elementos se puedan compartir o ordenar (como lo recomiendan otras respuestas) casi siempre haría que encontrar el elemento más común sea más rápido si la longitud de su lista (n) es grande. O (n) en promedio con hashing, y O (n * log (n)) en el peor de los casos para la clasificación.

>>> li  = ['goose', 'duck', 'duck']

>>> def foo(li):
         st = set(li)
         mx = -1
         for each in st:
             temp = li.count(each):
             if mx < temp:
                 mx = temp 
                 h = each 
         return h

>>> foo(li)
'duck'

Necesitaba hacer esto en un programa reciente. Lo admito, no podía entender la respuesta de Alex, así que esto es con lo que terminé.

def mostPopular(l):
    mpEl=None
    mpIndex=0
    mpCount=0
    curEl=None
    curCount=0
    for i, el in sorted(enumerate(l), key=lambda x: (x[1], x[0]), reverse=True):
        curCount=curCount+1 if el==curEl else 1
        curEl=el
        if curCount>mpCount \
        or (curCount==mpCount and i<mpIndex):
            mpEl=curEl
            mpIndex=i
            mpCount=curCount
    return mpEl, mpCount, mpIndex

Lo comparé con la solución de Alex y es aproximadamente un 10-15% más rápido para listas cortas, pero una vez que superas los 100 elementos o más (probado hasta 200000) es aproximadamente un 20% más lento.

Hola, esta es una solución muy simple con O grande (n)

L = [1, 4, 7, 5, 5, 4, 5]

def mode_f(L):
# your code here
    counter = 0
    number = L[0]
    for i in L:
        amount_times = L.count(i)
        if amount_times > counter:
            counter = amount_times
            number = i

    return number

Donde numerar el elemento en la lista que se repite la mayor parte del tiempo

def mostCommonElement(list):
  count = {} // dict holder
  max = 0 // keep track of the count by key
  result = None // holder when count is greater than max
  for i in list:
    if i not in count:
      count[i] = 1
    else:
      count[i] += 1
    if count[i] > max:
      max = count[i]
      result = i
  return result

mostCommonElement (["a", "b", "a", "c"]) -> "a"

 def most_common(lst):
    if max([lst.count(i)for i in lst]) == 1:
        return False
    else:
        return max(set(lst), key=lst.count)

def popular(L):
C={}
for a in L:
    C[a]=L.count(a)
for b in C.keys():
    if C[b]==max(C.values()):
        return b
L=[2,3,5,3,6,3,6,3,6,3,7,467,4,7,4]
print popular(L)