在列表中找到最常见的元素

Question

在Python列表中，有什么高效的方法可以找到出现频率最高的元素呢？

我的列表中的元素可能无法被哈希，所以不能使用字典。如果出现频率相同的情况，应该返回索引最小的那个元素。举个例子：

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

Answer 1

借鉴自这里，这个方法可以在Python 2.7中使用：

from collections import Counter

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

这个方法的速度比Alex的解决方案快4到6倍，比newacct提出的单行代码快50倍。

在CPython 3.6及以上版本（任何Python 3.7及以上版本）中，如果出现多个相同的元素，这个方法会选择第一个出现的元素。如果你在使用旧版本的Python，并且想在出现相同元素的情况下保留列表中第一个出现的元素，你需要进行两次遍历来保持顺序：

# Only needed pre-3.6!
def most_common(lst):
    data = Counter(lst)
    return max(lst, key=data.get)

Answer 2

这是一个更简单的一行代码：

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

Answer 3

有这么多解决方案被提出，我很惊讶居然没有人提到我认为很明显的一个方法（对于那些不能哈希但可以比较的元素）—— [itertools.groupby][1]。itertools 提供了快速且可重用的功能，让你可以把一些复杂的逻辑交给经过充分测试的标准库组件来处理。举个例子：

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]

当然，这段代码可以写得更简洁，但我想让它尽量清晰。可以取消注释的两个 print 语句可以帮助你更好地理解代码的运作；例如，取消注释后：

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

输出：

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

如你所见，SL 是一个包含对的列表，每对由一个项目和该项目在原始列表中的索引组成（这实现了一个关键条件：如果“最常见”的项目中有多个计数相同且大于1，结果必须是最早出现的那个）。

groupby 只根据项目进行分组（通过 operator.itemgetter）。辅助函数在 max 计算时每分组调用一次，它接收并内部解包一个组——这是一个包含两个项目的元组 (item, iterable)，其中 iterable 的项目也是两个项目的元组 (item, original index) [[就是 SL 的项目]]。

然后，辅助函数使用循环来确定组的 iterable 中条目的数量，以及最小的原始索引；它将这些作为组合的“质量键”返回，并将最小索引的符号反转，这样 max 操作就会认为在原始列表中出现得更早的项目是“更好”的。

如果不那么担心时间和空间的复杂度，这段代码可以简单得多，比如……：

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]

基本思路相同，只是表达得更简单紧凑……但是，唉，这样会多出 O(N) 的辅助空间（为了把组的 iterable 转换为列表）和 O(N²) 的时间（为了获取每个项目的 L.index）。虽然过早优化是编程中的万恶之源，但在有 O(N log N) 的方法可用时，故意选择 O(N²) 的方法实在是太不符合可扩展性原则了！-)

最后，对于那些喜欢“单行代码”而不是清晰和性能的人，这里有一个额外的单行版本，名字也稍微搞得复杂一点:-）。

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]