python – 查找列表中最常见的元素

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

我的列表项可能不具有哈希值,因此无法使用字典.
同样在绘制的情况下,应返回具有最低索引的项目.例：

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

解决方法:

有了这么多解决方案,我很惊讶没有人提出我认为是明显的解决方案(对于不可拆解但可比较的元素) – [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 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).辅助函数,在最大计算期间每个分组调用一次,接收并在内部解包一个组 – 一个包含两个项目的元组(item,iterable),其中iterable的项目也是两项元组,(item,original index)[[the SL的项目]].

然后辅助函数使用循环来确定组的可迭代条目数和最小原始索引;它返回那些组合的“质量密钥”,最小索引符号已更改,因此最大操作将考虑“更好”那些在原始列表中较早发生的项目.

如果它对时间和空间上的大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]

来源：https://www./content-1-452551.html