logo标签列表

在列表中找到出现次数最多的项

pythonlistmaxcounting
79

在Python中，我有一个列表：

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

我想找出发生最多次的项目。我知道如何解决它，但我需要最快的方法。我知道有一种很好的Pythonic答案。

14个回答
183

我很惊讶没有人提到最简单的解决方案，即使用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 2或3，但请注意它只返回最常见的项目而不是频率。另外，如果存在并列（即最常见的项目相同），则只返回一个项目。

虽然使用max()的时间复杂度比使用Counter.most_common(1)更差，正如PM 2Ring所评论的那样，但该方法有着快速的C实现，并且我发现该方法对于短列表来说速度最快，但对于较长列表则速度较慢（在IPython 5.3中显示Python 3.6的计时情况）：

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
5
我想要一个关于max如何与key=一起使用的解释。 - Asara
2
这有点低效，因为.count需要扫描整个列表以查找每个项，使其成为O(n²)。 - PM 2Ring
1
“Counter”很方便，但它并不以速度著称。当“n”相对较小且使用运行速度为C的函数/方法时，O(n²)可能已经足够好了。但是当“n”足够大时，情况可能会变得很糟糕，正如我在这里所讨论的那样。 - PM 2Ring
这是一个很好的答案，正是我所需要的，并且时间点得到了额外的奖励！我试图快速找到tensorflow.contrib.factorization.KMeansClustering()的输出中异常类。list(kmeans.predict_cluster_index(input_fn))的输出是一个数组，没有帮助函数来访问具有最高出现次数的聚类。 - Pat Grady
1
@Chris_Rands：非常好的答案！我在这个网站上找到了几种解决这个问题的方法。第二种方法与您的几乎完全相同，但他们首先对列表应用set()运算符。我想知道为什么这会起作用：我的意思是，我从列表中删除了所有重复项，然后再使用key=list.count..这对我来说没有意义。你明白这个吗？ - Luk
显示剩余9条评论
132
from collections import Counter
most_common,num_most_common = Counter(L).most_common(1)[0] # 4, 6 times

对于较旧的Python版本（< 2.7），您可以使用此配方来创建Counter类。

2
请参见Counter文档了解详情。 - SiggyF
3
如果你的列表为空，这将引发一个 IndexError 错误。 - user3064538
33
在你的问题中，你问了如何最快地完成它。正如多次展示的那样，特别是在使用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 是不错的选择，但你需要为其方便付出一点代价；用带有 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'方法的成本和原地添加的损失会相加（生成的代码的检查留作练习）。

但是使用修改后的测试数据时，唯一项值的数量没有改变，因此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的解决方案更快，但仍比dict和defaultdict的iteritems版本慢。

这些示例的重点不是产生最佳解决方案，而是通常不存在一个最佳的通用解决方案。此外，还有其他性能指标。这些解决方案之间的内存需求会有很大差异，并且随着输入大小的增加，内存需求可能成为算法选择中的主要因素。

总之：一切取决于具体情况，需要进行测量。

有趣的是，今天在Python 3.6上重新运行此代码时，结果发现计数器方法在处理长列表时似乎比其他方法更有效。 - moooeeeep
@moooeeeep：这是因为在3.2中添加了一个C加速器来计算可迭代对象（并在3.5中进一步优化以避免双哈希，这对于许多内置类型如小型int和str无害，但对其他类型来说代价高昂）；在此之前是纯Python。 Counter始终是最简单的，而且有了加速器后也是最快的。 - ShadowRanger
@NedDeily：如果您有机会，请在现代Python上重新运行这些计时；对于除了最小的输入（速度很少有影响），Counter将优于所有这些（它可以在不急切地在内存中实现整个输入的迭代器上工作，而sorted需要；峰值内存最终与唯一项目数成比例，而不是总数）。对于小输入，#4输给#1/2（击败其他人），但是将most_common内联为return max(Counter(L).items(), key=itemgetter(1))[0]即可解决；对于较大的输入，它的竞争对手的表现提高了2倍以上。 - ShadowRanger
18

这里是一个使用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]， 那么列表中有六个4和六个7。然而，结果将是(4, 6)，即六个4。

4
在简单性和速度方面，使用itemgetter(1)可能比使用lambda x: x[1]更好。这只是一个很小的建议。具体可以参考http://docs.python.org/howto/sorting.html#operator-module-functions。 - Darren Yin
10

如果您使用的是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()会抛出一个statistics.StatisticsError异常，而statistics.multimode()则返回一个空列表。
需要注意的是，在Python 3.8之前，statistics.mode()（在3.4中引入）还会在没有恰好一个最常见值的情况下抛出一个statistics.StatisticsError异常。
4

一种简单的方法，不需要任何库或集合

def mcount(l):
  n = []                  #To store count of each elements
  for x in l:
      count = 0
      for i in range(len(l)):
          if x == l[i]:
              count+=1
      n.append(count)
  a = max(n)              #largest in counts list
  for i in range(len(n)):
      if n[i] == a:
          return(l[i],a)  #element,frequency
  return                  #if something goes wrong
2
1
简单而最佳的代码：
def max_occ(lst,x):
    count=0
    for i in lst:
        if (i==x):
            count=count+1
    return count

lst=[1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
x=max(lst,key=lst.count)
print(x,"occurs ",max_occ(lst,x),"times")

输出：4 出现了 6 次

1

我使用Python 3.5.2版本，结合itertools模块中的groupby函数，取得了最佳的结果:

from itertools import groupby

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

def occurrence():
    occurrence, num_times = 0, 0
    for key, values in groupby(a, lambda x : x):
        val = len(list(values))
        if val >= occurrence:
            occurrence, num_times =  key, val
    return occurrence, num_times

occurrence, num_times = occurrence()
print("%d occurred %d times which is the highest number of times" % (occurrence, num_times))

输出：

4 occurred 6 times which is the highest number of times

使用timeit模块进行测试。

我在测试中使用了以下脚本，number= 20000：

from itertools import groupby

def occurrence():
    a = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
    occurrence, num_times = 0, 0
    for key, values in groupby(a, lambda x : x):
        val = len(list(values))
        if val >= occurrence:
            occurrence, num_times =  key, val
    return occurrence, num_times

if __name__ == '__main__':
    from timeit import timeit
    print(timeit("occurrence()", setup = "from __main__ import occurrence",  number = 20000))

输出（最佳）：

0.1893607140000313
1

我的（简单的）代码（学习Python三个月）：

def more_frequent_item(lst):
    new_lst = []
    times = 0
    for item in lst:
        count_num = lst.count(item)
        new_lst.append(count_num)
        times = max(new_lst)
    key = max(lst, key=lst.count)
    print("In the list: ")
    print(lst)
    print("The most frequent item is " + str(key) + ". Appears " + str(times) + " times in this list.")


more_frequent_item([1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67])

输出将为：

In the list: 
[1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
The most frequent item is 4. Appears 6 times in this list.
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接