Python-在列表中查找最常见的元素

Question

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

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

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

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]

相同的基本思想，只是表达得更简单，紧凑…但是，las，额外的O（N）辅助空间（将组的可迭代对象体现到列表中）和O（N平方）时间（获取L.index每个项目的总和） 。尽管过早的优化是编程中所有弊端的根源，但在有O（N log N）个可用的情况下，故意选择O（N平方）的方法与可扩展性背道而驰！

最后，对于那些更喜欢“单线”而不是清晰度和性能的人，可以使用名称经过适当修饰的1线奖金版本：-)。

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]