有效地检查一个元素是否在列表中至少出现 n 次 [英] Efficiently check if an element occurs at least n times in a list
问题描述
如何最好地编写 Python 函数 (check_list
) 以有效测试元素 (x
) 是否在一个元素中至少出现 n
次列表 (l
)?
How to best write a Python function (check_list
) to efficiently test if an element (x
) occurs at least n
times in a list (l
)?
我的第一个想法是:
def check_list(l, x, n):
return l.count(x) >= n
但是一旦 x
被找到 n
次并且总是 O(n),这不会短路.
But this doesn't short-circuit once x
has been found n
times and is always O(n).
一种简单的短路方法是:
A simple approach that does short-circuit would be:
def check_list(l, x, n):
count = 0
for item in l:
if item == x:
count += 1
if count == n:
return True
return False
我还有一个更紧凑的带发电机的短路解决方案:
I also have a more compact short-circuiting solution with a generator:
def check_list(l, x, n):
gen = (1 for item in l if item == x)
return all(next(gen,0) for i in range(n))
还有其他好的解决方案吗?什么是最有效的方法?
Are there other good solutions? What is the best efficient approach?
谢谢
推荐答案
而不是通过设置 range
对象并使用必须测试的 all
来产生额外的开销每个项目的真实性,你可以使用itertools.islice
使生成器前进 n
步,如果切片存在或默认 False,则返回切片中的 next 项
如果不是:
Instead of incurring extra overhead with the setup of a range
object and using all
which has to test the truthiness of each item, you could use itertools.islice
to advance the generator n
steps ahead, and then return the next item in the slice if the slice exists or a default False
if not:
from itertools import islice
def check_list(lst, x, n):
gen = (True for i in lst if i==x)
return next(islice(gen, n-1, None), False)
请注意,与 list.count
一样,itertools.islice
也以 C 速度运行.这具有处理非列表的可迭代对象的额外优势.
Note that like list.count
, itertools.islice
also runs at C speed. And this has the extra advantage of handling iterables that are not lists.
一些时间:
In [1]: from itertools import islice
In [2]: from random import randrange
In [3]: lst = [randrange(1,10) for i in range(100000)]
In [5]: %%timeit # using list.index
....: check_list(lst, 5, 1000)
....:
1000 loops, best of 3: 736 µs per loop
In [7]: %%timeit # islice
....: check_list(lst, 5, 1000)
....:
1000 loops, best of 3: 662 µs per loop
In [9]: %%timeit # using list.index
....: check_list(lst, 5, 10000)
....:
100 loops, best of 3: 7.6 ms per loop
In [11]: %%timeit # islice
....: check_list(lst, 5, 10000)
....:
100 loops, best of 3: 6.7 ms per loop
这篇关于有效地检查一个元素是否在列表中至少出现 n 次的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!