检查值是否比列表中的X更常存在的最快方法

Question

我有一个很长的列表(300 000个元素),我想检查该列表中的每个元素是否存在超过5次.所以最简单的代码是

[x for x in x_list if x_list.count(x) > 5]

但是,我不需要计算x在列表中出现的频率,我可以在达到至少5个元素后停止计数？我也不需要遍历x_list中的所有元素,因为在查看列表时我有可能已经检查了值x.知道如何获得此代码的最佳版本吗？我的输出应该是一个列表,尽可能使用相同的顺序...

Answer 1

这是Counter基于解决方案:

from collections import Counter

items = [2,3,4,1,2,3,4,1,2,1,3,4,4,1,2,4,3,1,4,3,4,1,2,1]
counts = Counter(items)
print(all(c >= 5 for c in counts.values())) #prints True

如果我使用

items = [random.randint(1,1000) for i in range(300000)]

基于反制的解决方案仍然是一小部分.

Answer 2

信不信由你,只是做一个常规循环效率更高:

数据来自:

import random
N = 300000
arr = [random.random() for i in range(N)]
#and random ints are generated: arr = [random.randint(1,1000) for i in range(N)]

常规循环计算在0.22秒内,如果我使用整数,那么它是.12(非常类似于集合)(在2.4 Ghz处理器上).

di = {}
for item in arr:
    if item in di:
        di[item] += 1
    else:
        di[item] = 1
print (min(di.values()) > 5)

您的版本大于30秒,有或没有整数.

[x for x in arr if arr.count(x) > 5]

如果我使用整数,使用集合大约需要0.33秒和.11.

from collections import Counter

counts = Counter(arr)
print(all(c >= 5 for c in counts.values()))

最后,无论是否有整数,这都需要30秒以上:

count = [0]*(max(x_list)+1)
for x in x_list:
    count[x]+=1;
return [index for index, value in enumerate(count) if value >= 5]