有效检查元素是否在列表中至少出现了n次

本文介绍了有效检查元素是否在列表中至少出现了n次的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如何最好地编写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