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

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) 用于排序，这在这里对你没有任何帮助 - 你仍然需要为 max(...) 语句和每个元素检查完整的 a 遍历整个列表再次 count() 它的出现 - 即使 所有元素都相同.

所以

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

这使用 5 次遍历并计算整个列表，每个遍历导致 O(n²) 在 O(n*log(n)) 之上进行排序 - 无症状地这是受 O(n²).[=22= 约束]

这种的基本方法是使用collections.Counter:

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]

在一定程度上 list-size 列表计数可能仍然优于列表计数 - 因为您不需要从数据开始创建字典 - 这也需要时间。

对于稍大的列表，反击获胜：

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()]

编辑

抱歉，我没有注意到 'largest' 要求。

如果您选择计数器：

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 中存储了最大值 [key, value]。在第一个 if 语句中，我对元素的出现次数求和，在第二个 if 语句中，我更新了最大元素，而在最后一个 if 语句中，我还比较了键。

使用包含 20000 个元素的列表 我得到：

对于你的解决方案 3.08 秒，
对于此解决方案 16 毫秒！

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

How can I find the most frequent largest element in list faster?

python

python-3.x

optimization