有效检查元素是否在列表中至少出现了n次 [英] Efficiently check if an element occurs at least n times in a list
问题描述
如何最好地编写Python函数(check_list
)以有效测试元素(x
)在列表(l
)中是否出现至少n
次?
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
的步骤,然后返回该切片中的 next 项(如果该切片存在)或默认的False
(如果不存在)
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屋!