Python le plus commun élément dans une liste

Question

Ce qui est un moyen efficace pour trouver le plus commun élément dans une liste Python?

Mes éléments de la liste peuvent ne pas être hashable ne peut donc pas utiliser un dictionnaire. Aussi en cas de attire l'élément avec le plus petit indice doit être retourné. Exemple:

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

Answer 1

Un simple one-liner:

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

Answer 2

D'emprunt à partir d' ici, il peut être utilisé avec Python 2.7:

from collections import Counter

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

Travaux autour de 4 à 6 fois plus rapide que Alex solutions, et est 50 fois plus rapide que le one-liner proposé par newacct.

Answer 3

Avec autant de solutions proposées, je suis étonné de voir que personne n'est proposé, ce que je voudrais examiner une évidence (pour les non-hashable mais comparable éléments) -- [itertools.groupby][1]. itertools offre rapide, des fonctionnalités réutilisables, et vous permet de déléguer des problèmes de logique pour le bien-testé standard des composants de la bibliothèque. Considérons par exemple:

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]

Cela pourrait être écrit de façon plus concise, bien sûr, mais je vise pour un maximum de clarté. Les deux print des déclarations peut être retirée afin de mieux voir les machines en action; par exemple, avec gravures sans commentaire:

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

émet:

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

Comme vous le voyez, SL est une liste de paires, chaque paire un élément suivie par l'élément d'index dans la liste d'origine (à mettre en œuvre les principaux condition que, si les plus "communes" les éléments avec le même plus compter sont > 1, le résultat doit être le plus précoce survenant).

groupby groupes par l'article (via operator.itemgetter). La fonction auxiliaire, appelé une fois par regroupement au cours de l' max calcul, reçoit et, en interne, décompresse un groupe - un n-uplet avec deux éléments (item, iterable) où l'objet iterable les articles sont également deux élément de n-uplets, (item, original index) [[les éléments de l' SL]].

Ensuite, la fonction auxiliaire utilise une boucle pour déterminer à la fois le nombre d'entrées dans le groupe de l'itératif, et le minimum de l'index; il renvoie les combinés de "qualité", avec le min de l'indice de signe-modifié le max fonctionnement considère comme "mieux" ceux de ces éléments qui a eu lieu plus tôt dans la liste d'origine.

Ce code pourrait être beaucoup plus simple si il s'inquiétait un peu moins sur le big-O questions dans le temps et dans l'espace, de l'e.g....:

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]

même idée de base, juste exprimé plus simplement et de façon compacte... mais, hélas, un supplément de O(N) espace auxiliaire (pour incarner les groupes iterables à des listes) et O(N au carré), le temps (pour obtenir le L.index de chaque élément). Alors que l'optimisation prématurée est la racine de tous les maux dans la programmation, délibérément sélection d'une O(N au carré) approche quand un O(N log N) est disponible à tout va trop à l'encontre de l'évolutivité!-)

Enfin, pour ceux qui préfèrent le "oneliners" à la clarté et à la performance, un bonus de 1-liner version avec convenablement les noms déformés:-).

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]

Answer 4

Si elles ne sont pas hashable, vous pouvez les trier et de faire une seule boucle sur le résultat compter les objets (les éléments identiques seront unes à côté des autres). Mais il pourrait être plus rapide à faire hashable et l'utilisation d'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

Answer 5

Trier une copie de la liste et de trouver le plus long terme. Vous pouvez décorer la liste avant d'en faire le tri avec l'index de chaque élément, puis choisissez la course qui commence avec l'indice le plus bas dans le cas d'une cravate.