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

Question

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

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

目前我使用：

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

那么，如果过滤不为空，返回真。

假设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 

Answer 2

除非你打算使用这些值，使用filter函数是不必要的，因为它存储了你最终不会使用的数据。即使找到符合标准的标准，它也会继续运行，这会让您的相对速度变慢。

我的解决方案本来是写和使用以下功能。

def check(list, lower, upper): 
    for i in list: 
     if i >= lower and i <= upper: 
      return True 
    return False 

与@ Kasramvd的回答和你的想法一样，这是蛮力搜索（O（n）解决方案）。除非事先对数据有一些限制，否则这是不可能的，因为它必须进行排序。

Answer 3

最快的方法是使用排序列表或元组而不是集合。这样你就可以使用bisect module进行范围搜索。