python - 在 Python 中检查集合是否包含给定范围内的数字的最快方法

Question

检查一组是否至少包含给定范围内的一个数字的最快方法是什么？

例如setA = set(1,4,7,9,10), lowerRange=6, upperRange=8, 将因为 7 返回 True。

目前我正在使用:

filtered = filter(lambda x: lowerRange<=x<=upperRange,setA)

然后如果 filtered 不为空，则返回 True。

假设 setA 可以是一个非常大的集合，这是最优解吗？还是遍历整个 setA？

Answer 1

由于集合的成员资格大约为 O(1)，您可以在 any() 内置函数中使用生成器表达式:

rng = range(6, 9)
any(i in setA for i in rng)

请注意，对于短距离，使用 set.intersection() 可以获得更好的性能:

In [2]: a = {1,4,7,9,10}

In [3]: rng = range(6, 9)

In [8]: %timeit bool(a.intersection(rng))
1000000 loops, best of 3: 344 ns per loop

In [9]: %timeit any(i in a for i in rng)
1000000 loops, best of 3: 620 ns per loop

但在这种情况下，对于更长的范围，您肯定会使用 any():

In [10]: rng = range(6, 9000)

In [11]: %timeit any(i in a for i in rng)
1000000 loops, best of 3: 620 ns per loop

In [12]: %timeit bool(a.intersection(rng))
1000 loops, best of 3: 233 µs per loop

请注意 any() 表现更好的原因是因为它在遇到您的集合中存在的项目(基于我们的成员条件)后立即返回 True，因为数字 8 是在范围的开头，它使每个表单的 any() 变得如此之快。同样如评论中所述，作为一种更 pythonic 的方法来检查集合中可迭代对象的交集的有效性，您可以使用 isdisjoint() 方法。这是针对小愤怒使用此方法的基准:

In [26]: %timeit not a.isdisjoint(rng)
1000000 loops, best of 3: 153 ns per loop

In [27]: %timeit any(i in a for i in rng)
1000000 loops, best of 3: 609 ns per loop

这是一个基准测试，它使 any() 检查所有数字的成员资格，这表明 isdisjoint() 表现得更好:

In [29]: rng = range(8, 1000)

In [30]: %timeit any(i in a for i in rng)
1000000 loops, best of 3: 595 ns per loop

In [31]: %timeit not a.isdisjoint(rng)
10000000 loops, best of 3: 142 ns per loop