Python-找到列表中出现次数最多的项目

Question

在Python中,我有一个列表:

L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]  

我想确定发生次数最多的项目.我能够解决它,但我需要最快的方法来解决它.我知道有一个很好的Pythonic答案.

Answer 1

from collections import Counter
most_common,num_most_common = Counter(L).most_common(1)[0] # 4, 6 times

对于较旧的Python版本(<2.7),您可以使用此receipe来获取Counter该类.

Answer 2

我很惊讶没有人提到最简单的解决方案,max()关键是list.count:

max(lst,key=lst.count)

例:

>>> lst = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
>>> max(lst,key=lst.count)
4

这适用于Python 3或2,但请注意,它只返回最频繁的项目,而不是频率.此外,在抽奖(即联合最频繁项目)的情况下,仅返回单个项目.

虽然使用的时间复杂度max()比使用更糟糕的Counter.most_common(1)是PM 2Ring意见,从一个快速的方法好处C执行,我觉得这种做法是为最快的短名单,但对于较大的(Python的3.6定时在IPython的5.3所示)慢:

In [1]: from collections import Counter
   ...: 
   ...: def f1(lst):
   ...:     return max(lst, key = lst.count)
   ...: 
   ...: def f2(lst):
   ...:     return Counter(lst).most_common(1)
   ...: 
   ...: lst0 = [1,2,3,4,3]
   ...: lst1 = lst0[:] * 100
   ...: 

In [2]: %timeit -n 10 f1(lst0)
10 loops, best of 3: 3.32 us per loop

In [3]: %timeit -n 10 f2(lst0)
10 loops, best of 3: 26 us per loop

In [4]: %timeit -n 10 f1(lst1)
10 loops, best of 3: 4.04 ms per loop

In [5]: %timeit -n 10 f2(lst1)
10 loops, best of 3: 75.6 us per loop

Answer 3

在您的问题中,您要求以最快的方式执行此操作.正如反复证明的那样,特别是Python,直觉不是一个可靠的指南:你需要衡量.

这是对几种不同实现的简单测试:

import sys
from collections import Counter, defaultdict
from itertools import groupby
from operator import itemgetter
from timeit import timeit

L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]

def max_occurrences_1a(seq=L):
    "dict iteritems"
    c = dict()
    for item in seq:
        c[item] = c.get(item, 0) + 1
    return max(c.iteritems(), key=itemgetter(1))

def max_occurrences_1b(seq=L):
    "dict items"
    c = dict()
    for item in seq:
        c[item] = c.get(item, 0) + 1
    return max(c.items(), key=itemgetter(1))

def max_occurrences_2(seq=L):
    "defaultdict iteritems"
    c = defaultdict(int)
    for item in seq:
        c[item] += 1
    return max(c.iteritems(), key=itemgetter(1))

def max_occurrences_3a(seq=L):
    "sort groupby generator expression"
    return max(((k, sum(1 for i in g)) for k, g in groupby(sorted(seq))), key=itemgetter(1))

def max_occurrences_3b(seq=L):
    "sort groupby list comprehension"
    return max([(k, sum(1 for i in g)) for k, g in groupby(sorted(seq))], key=itemgetter(1))

def max_occurrences_4(seq=L):
    "counter"
    return Counter(L).most_common(1)[0]

versions = [max_occurrences_1a, max_occurrences_1b, max_occurrences_2, max_occurrences_3a, max_occurrences_3b, max_occurrences_4]

print sys.version, "\n"

for vers in versions:
    print vers.__doc__, vers(), timeit(vers, number=20000)

我的机器上的结果:

2.7.2 (v2.7.2:8527427914a2, Jun 11 2011, 15:22:34) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] 

dict iteritems (4, 6) 0.202214956284
dict items (4, 6) 0.208412885666
defaultdict iteritems (4, 6) 0.221301078796
sort groupby generator expression (4, 6) 0.383440971375
sort groupby list comprehension (4, 6) 0.402786016464
counter (4, 6) 0.564319133759

所以似乎Counter解决方案并不是最快的.并且,至少在这种情况下,groupby更快.defaultdict很好,但你为它的方便付出了一点点; 这是略快于使用常规dict用get.

如果列表更大,会发生什么？添加L *= 10000到上面的测试并将重复次数减少到200:

dict iteritems (4, 60000) 10.3451900482
dict items (4, 60000) 10.2988479137
defaultdict iteritems (4, 60000) 5.52838587761
sort groupby generator expression (4, 60000) 11.9538850784
sort groupby list comprehension (4, 60000) 12.1327362061
counter (4, 60000) 14.7495789528

现在defaultdict是明显的赢家.因此,'get'方法的成本和inplace add的损失可能会增加(对生成的代码的检查留作练习).

但是使用修改后的测试数据,唯一项目值的数量并没有发生变化,因此dict与defaultdict其他实现相比具有优势.那么如果我们使用更大的列表却会大幅增加独特项目的数量会怎样？用以下内容替换L的初始化:

LL = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
L = []
for i in xrange(1,10001):
    L.extend(l * i for l in LL)

dict iteritems (2520, 13) 17.9935798645
dict items (2520, 13) 21.8974409103
defaultdict iteritems (2520, 13) 16.8289561272
sort groupby generator expression (2520, 13) 33.853593111
sort groupby list comprehension (2520, 13) 36.1303369999
counter (2520, 13) 22.626899004

所以现在Counter比显然更快groupby的解决方案比,但仍然较慢iteritems的版本dict和defaultdict.

这些例子的要点不是产生最佳解决方案.关键是通常没有一个最佳的通用解决方案.另外还有其他性能标准.存储器要求在解决方案之间会有很大差异,并且随着输入的大小增加,存储器要求可能成为算法选择的首要因素.

底线:这完全取决于你需要衡量.

Answer 4

这是一个defaultdict适用于Python 2.5及更高版本的解决方案:

from collections import defaultdict

L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
d = defaultdict(int)
for i in L:
    d[i] += 1
result = max(d.iteritems(), key=lambda x: x[1])
print result
# (4, 6)
# The number 4 occurs 6 times

请注意,如果L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 7, 7, 7, 7, 7, 56, 6, 7, 67] 那么有6个4和6个7.但是,结果将是(4, 6) 6个4s.

Answer 5

如果您使用的是 Python 3.8 或更高版本，则可以使用statistics.mode()返回遇到的第一个模式或statistics.multimode()返回所有模式。

>>> import statistics
>>> data = [1, 2, 2, 3, 3, 4] 
>>> statistics.mode(data)
2
>>> statistics.multimode(data)
[2, 3]

如果列表为空，则statistics.mode()抛出 astatistics.StatisticsError并statistics.multimode()返回一个空列表。

注意在 Python 3.8 之前，statistics.mode()（在 3.4 中引入）statistics.StatisticsError如果不存在最常见的值，则会额外抛出 a 。