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

小编典典

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

python

如何最好地编写Python函数（check_list）以有效测试元素（x）是否至少出现在n列表（l）中几次？

我的第一个想法是：

def check_list(l, x, n):
    return l.count(x) >= n

但是，一旦x发现n次数，它就不会短路，并且始终为O（n）。

造成短路的简单方法是：

def check_list(l, x, n):
    count = 0
    for item in l:
        if item == x:
            count += 1
            if count == n:
                return True
    return False

我也有一个带有发电机的更紧凑的短路解决方案：

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

还有其他好的解决方案吗？什么是最有效的方法？

谢谢

阅读 216

2020-12-20

共1个答案

小编典典

而不会造成额外的开销用的设置的range对象，并使用all具有测试 感实性
每一个项目，你可以使用itertools.islice推动发电机n提前步骤，然后返回
下一个 切片项目，如果切片存在或默认False，如果不：

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)

注意like list.count，itertools.islice也以C速度运行。这具有处理非列表的可迭代对象的额外优势。

一些时间：

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

2020-12-20