找到列表中最常见的元素

Question

找到列表中最常见的元素查找Python列表中最常见元素的有效方法是什么？我的列表项可能不具有哈希值，因此无法使用字典。同样在绘制的情况下，应返回具有最低索引的项目。例：>>> most_common(['duck', 'duck', 'goose'])'duck'>>> most_common(['goose', 'duck', 'duck', 'goose'])'goose'

Answer 1

有了这么多解决方案，我很惊讶没有人提出我认为是明显的解决方案（对于不可拆解但可比较的元素） - [ itertools.groupby] [1]。 itertools提供快速，可重用的功能，并允许您将一些棘手的逻辑委托给经过充分测试的标准库组件。考虑例如：

import itertoolsimport operatordef 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 1item 'goose', count 2, minind 0goose

如您所见，SL是一对对的列表，每一对都是一个项目，后跟原始列表中的项目索引（为了实现关键条件，如果具有相同最高计数的“最常见”项目> 1，则结果必须是最早发生的一个）。

groupby仅按项目分组（通过operator.itemgetter）。在max计算过程中每个分组调用一次的辅助函数接收并在内部解包一个组 - 一个包含两个项的元组，(item, iterable)其中iterable的项也是两项元组，(item, original index)[[items of 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 gdef most_common_oneliner(L):
  return max(g(sorted(L)), key=lambda(x, v):(len(list(v)),-L.index(x)))[0]

Answer 2

一个更简单的单线程：

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

Answer 3

借用这里，这可以用于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倍。

在绑定的情况下检索列表中首先出现的元素：

def most_common(lst):

    data = Counter(lst)

    return max(lst, key=data.get)