查找列表中最常见的元素

Question

在 Python 列表中查找最常见元素的有效方法是什么？

我的列表项可能无法散列，因此无法使用字典。此外，在绘制的情况下，应返回索引最低的项目。例子：

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

原文由 hoju 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

提出了这么多解决方案，我很惊讶没有人提出我认为显而易见的解决方案（对于不可散列但可比较的元素）-- [ 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) 其中可迭代的项目也是两项元组， (item, original index) [[项目 SL ]]。

然后辅助函数使用循环来确定组的可迭代项中的条目数 和 最小原始索引；它将这些作为组合的“质量键”返回，最小索引符号已更改，因此 max 操作将考虑“更好”那些在原始列表中较早出现的项目。

如果这段代码 不太 担心时间和空间上的大 O 问题，它可能会简单得多，例如…：

 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) 辅助空间（以体现组的可迭代列表）和 O(N 平方) 时间（以获得 L.index 每个项目）。虽然过早的优化是编程中万恶之源，但当 O(N log N) 可用时故意选择 O(N 平方) 方法，这对可扩展性来说太过分了！-)

最后，对于那些更喜欢“oneliners”而不是清晰度和性能的人，还有一个额外的 1-liner 版本，带有适当的名称：-)。

 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]

原文由 Alex Martelli 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

一个更简单的单线：

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

原文由 newacct 发布，翻译遵循 CC BY-SA 2.5 许可协议