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

Question

如何最好地编写Python函数(check_list)来有效地测试一个element(x)是否至少出现在nlist(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))

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

谢谢

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

请注意,同样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

Answer 2

您可以使用第二个参数index来查找后续的出现索引:

def check_list(l, x, n):
    i = 0
    try:
        for _ in range(n):
            i = l.index(x, i)+1
        return True
    except ValueError:
        return False

print( check_list([1,3,2,3,4,0,8,3,7,3,1,1,0], 3, 4) )

关于index论点

官方文档在其Python Tutuorial第5节中没有提到方法的第二个或第三个参数,但是你可以在更全面的Python标准库中找到它,第4.6节:

s.index(x[, i[, j]]) 的第一次出现的指数X在小号(在或索引后我和指数前  Ĵ)  ⁽⁸⁾

⁽⁸⁾ 在s中找不到x时index加注.支持时,索引方法的附加参数允许有效搜索序列的子部分.传递额外的参数大致相当于使用,只是没有复制任何数据,返回的索引相对于序列的开头而不是切片的开头.ValueErrors[i:j].index(x)

绩效比较

在将该list.index方法与该islice(gen)方法进行比较时,最重要的因素是要找到的事件之间的距离.一旦该距离平均为13或更多,则list.index具有更好的性能.对于较低距离,最快的方法还取决于要查找的出现次数.找到的次数越多,该islice(gen)方法list.index在平均距离方面表现越快:当出现次数变得非常大时,这种增益会逐渐消失.

下图绘制了(近似)边界线,两个方法的表现同样良好(X轴为对数):