找到列表中最常见的元素

Question

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

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

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

Answer 1

一个更简单的单线程:

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

Answer 2

借用这里,这可以用于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)

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)[[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 g
def most_common_oneliner(L):
  return max(g(sorted(L)), key=lambda(x, v):(len(list(v)),-L.index(x)))[0]

Answer 4

你想要的东西在统计学中称为模式,Python当然有一个内置函数来完成你的工作:

>>> from statistics import mode
>>> mode([1, 2, 2, 3, 3, 3, 3, 3, 4, 5, 6, 6, 6])
3

请注意,如果没有"最常见的元素",例如前两个被绑定的情况,这将会提高StatisticsError,因为从统计上讲,在这种情况下没有模式.

Answer 5

没有关于最低索引的要求，您可以使用collections.Counter：

from collections import Counter

a = [1936, 2401, 2916, 4761, 9216, 9216, 9604, 9801] 

c = Counter(a)

print(c.most_common(1)) # the one most common element... 2 would mean the 2 most common
[(9216, 2)] # a set containing the element, and it's count in 'a'

Answer 6

如果它们不可清洗,您可以对它们进行排序,并对计算项目的结果进行一次循环(相同的项目将彼此相邻).但它可以更快地使它们可以使用并使用dict.

def most_common(lst):
    cur_length = 0
    max_length = 0
    cur_i = 0
    max_i = 0
    cur_item = None
    max_item = None
    for i, item in sorted(enumerate(lst), key=lambda x: x[1]):
        if cur_item is None or cur_item != item:
            if cur_length > max_length or (cur_length == max_length and cur_i < max_i):
                max_length = cur_length
                max_i = cur_i
                max_item = cur_item
            cur_length = 1
            cur_i = i
            cur_item = item
        else:
            cur_length += 1
    if cur_length > max_length or (cur_length == max_length and cur_i < max_i):
        return cur_item
    return max_item

Answer 7

这是一个O(n)解决方案.

mydict   = {}
cnt, itm = 0, ''
for item in reversed(lst):
     mydict[item] = mydict.get(item, 0) + 1
     if mydict[item] >= cnt :
         cnt, itm = mydict[item], item

print itm

(反向用于确保它返回最低的索引项)

Answer 8

对列表的副本进行排序,找到最长的运行时间.您可以在使用每个元素的索引对其进行排序之前对列表进行装饰,然后在绑定的情况下选择以最低索引开头的运行.

Answer 9

单行:

def most_common (lst):
    return max(((item, lst.count(item)) for item in set(lst)), key=lambda a: a[1])[0]