如何更快地找到列表中出现频率最高的元素?

Question

任务是找出给定列表中出现次数最多的最大元素

# for example we have list a
a = ['1', '3', '3', '2', '1', '1', '4', '3', '3', '1', '6', '6', '3','6', '6', '6']
a.sort(reverse=True)
print(max(a, key=a.count))

我怎样才能使这个简单的脚本工作更快?

Answer 1

为什么要排序?

你有n*log(n)排序，这对你没有任何帮助-你仍然需要检查完整的a对于max(...)语句，并且对于每个元素再次遍历整个列表直到count()它的出现-即使所有元素都是相同的。

["a","a","a","a","a"] 

这使用了5次传递，并计算了每一次的整个列表，这导致O(n²)在O(n*log(n))之上进行排序-这被O(n²)绑定。

这种类型的基本方法是使用集合。柜台:

from collections import Counter
a = ['1', '3', '3', '2', '1', '1', '4', '3', '3', '1',
'6', '6', '3','6', '6', '6']

c = Counter(a) 
# "3" and "6" occure 5 times, "3" is first in source so it is 
# reported first - to get the max value of all those that occure
# max_times, see below
print(c.most_common(1))[0][0] 

在一定的列表大小范围内，列表计数可能仍然优于

，因为您不需要从数据开始创建字典，这也需要花费时间。

---

对于稍大的列表Counter轻松获胜:

from collections import Counter
# larger sample - for short samples list iteration may outperform Counter
data = list('1332114331663666')
# 6 times your data + 1 times "6" so "6" occures the most
a1 = [*data, *data, *data, *data, *data, *data, "6"]
a2 = sorted(a1, reverse=True)
c = Counter(a1)
def yours():
return max(a1, key=a1.count)
def yours_sorted():
return max(a2, key=a2.count)
def counter():
c = Counter(a1)
mx = c.most_common(1)[0][1]  # get maximal count amount
# get max value for same highest count
return max(v for v,cnt in c.most_common() if cnt==mx) 
def counter_nc():        
mx = c.most_common(1)[0][1] # get maximal count amount
# get max value for same highest count
return max(v for v,cnt in c.most_common() if cnt==mx) 
import timeit
print("Yours:   ", timeit.timeit(stmt=yours, setup=globals, number=10000))
print("Sorted:  ", timeit.timeit(stmt=yours, setup=globals, number=10000))
print("Counter: ", timeit.timeit(stmt=counter, setup=globals, number=10000))
print("NoCreat: ", timeit.timeit(stmt=counter_nc, setup=globals, number=10000))

给出(大致):

Yours:    0.558837399999902
Sorted:   0.557338600001458 # for 10k executions saves 2/1000s == noise
Counter:  0.170493399999031 # 3.1 times faster including counter creation
NoCreat:  0.117090099998677 # 5 times faster no counter creation

即使包括在函数内部创建计数器，其时间也优于O(n²)方法。

Answer 2

如果您使用纯python,collections.Counter可能是最佳选择。

from collections import Counter
counter = Counter(a)
mode = counter.most_common(1)[0][0]

当然，自己实现它并不难。

counter = {}
counter_get = counter.get
for elem in a:
counter[elem] = counter_get(elem, 0) + 1
mode = max(counter, key=counter_get)   # or key=counter.__getitem__

对于大列表，使用numpy的数组可能会更快。

import numpy as np
ar = np.array(a, dtype=str)
vals, counts = np.unique(ar, return_counts=True)
mode = vals[counts.argmax()]

编辑

对不起，我没有注意到"最大"的要求。

如果您选择计数器:

max_count = max(counter.values())
largest_mode = max(val for val, count in counter.items() if count == max_count)
# One step in place, a little faster.
largest_mode = max(zip(counter.values(), counter))[1]

或numpy:

largest_mode = vals[counts == counts.max()].max()
# even vals[counts == counts.max()][-1]
# because vals is sorted.

Answer 3

从头开始的解决方案是这样的:

elem_dict = dict()
max_key_el = [0,0]
for el in a:
if el not in elem_dict:
elem_dict[el] = 1
else:
elem_dict[el] += 1
if elem_dict[el] >= max_key_el[1]:
if int(el) > int(max_key_el[0]):
max_key_el[0] = el
max_key_el[1] = elem_dict[el] 
print(max_key_el[0])

我使用字典elem_dict存储计数器。我存储在max_key_el最大[键，值]。在第一个if语句中，我对元素的出现次数求和，在第二个if语句中，我更新了最大元素，而在最后一个if语句中，我还比较了键。

使用包含20000个元素的列表我获得:

• 您的解决方案3.08 s
• 对于这个解决方案16毫秒!