在Python中快速检查范围

Question

我有很多范围的形式[(1, 1000), (5000, 5678), ... ]。我试图找出最快的方法来检查数字是否在任何范围内。范围由longs组成，并且太大而不能保留所有数字的set。

最简单的办法是这样的：

ranges = [(1,5), (10,20), (40,50)] # The real code has a few dozen ranges 
nums = range(1000000) 
%timeit [n for n in nums if any([r[0] <= n <= r[1] for r in ranges])] 
# 1 loops, best of 3: 5.31 s per loop 

榕树是快了一点：

import banyan 
banyan_ranges = banyan.SortedSet(updator=banyan.OverlappingIntervalsUpdator) 
for r in ranges: 
    banyan_ranges.add(r) 
%timeit [n for n in nums if len(banyan_ranges.overlap_point(n))>0] 
# 1 loops, best of 3: 452 ms per loop 

虽然只有几十个范围，有几百万对那些范围检查。什么是做这些检查的最快方法？

（注：这个问题类似于Python: efficiently check if integer is within *many* ranges，但不具有相同的Django的相关限制，并与速度专门涉及）

Answer 1

事情尝试：

1. 处理前的范围，使他们不重叠，并将它们表达为半开区间。
2. 使用bisect模块进行搜索。 （请勿手动执行自己的二分搜索！）请注意，对于1中的预处理，您只需要知道bisect调用的结果是偶数还是奇数。
3. 如果批处理查询是一个选项，请考虑将输入分组到数组中并使用numpy.searchsorted。

一些代码和计时。首先设置（这里使用IPython的2.1和Python 3.4）：

In [1]: ranges = [(1, 5), (10, 20), (40, 50)] 

In [2]: nums = list(range(1000000)) # force a list to remove generator overhead 

时机与原来的方法我的机器上（但与发电机的表达，而不是一个列表理解）：

In [3]: %timeit [n for n in nums if any(r[0] <= n <= r[1] for r in ranges)] 
1 loops, best of 3: 922 ms per loop 

现在我们将范围重新作为边界点列表; 索引处的每个边界点是其中一个范围的入口点，而在处的奇数索引处的每个边界点是退出点。请注意转换为半开间隔，并且我已将所有数字放入单个列表中。

In [4]: boundaries = [1, 6, 10, 21, 40, 51] 

有了这个可以很容易地使用bisect.bisect来得到相同的结果和以前一样，而是速度更快。

In [5]: from bisect import bisect 

In [6]: %timeit [n for n in nums if bisect(boundaries, n) % 2] 
1 loops, best of 3: 298 ms per loop 

最后，根据上下文，你可以利用从与NumPy的searchsorted功能。这就像bisect.bisect，但是一次对整个值的集合进行操作。例如：

In [7]: import numpy 

In [8]: numpy.where(numpy.searchsorted(boundaries, nums, side="right") % 2)[0] 
Out[8]: 
array([ 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 40, 
     41, 42, 43, 44, 45, 46, 47, 48, 49, 50]) 

乍一看，从这个%timeit结果相当令人失望。

In [9]: %timeit numpy.where(numpy.searchsorted(boundaries, nums, side="right") % 2)[0] 
10 loops, best of 3: 159 ms per loop 

然而，事实证明，许多的性能成本的是在从Python列表转换的输入searchsorted到NumPy的阵列。让我们preconvert两个列表阵列，然后再试一次：比什么都重要，到目前为止

In [10]: boundaries = numpy.array(boundaries) 

In [11]: nums = numpy.array(nums) 

In [12]: %timeit numpy.where(numpy.searchsorted(boundaries, nums, side="right") % 2)[0] 
10 loops, best of 3: 24.6 ms per loop 

许多更快。然而，这有点作弊：我们当然可以预处理boundaries将它变成一个数组，但是如果你想测试的值不是以数组形式自然生成的，那么转换成本将需要考虑在内。另一方面，它表明搜索本身的成本可以降低到一个足够小的值，以至于不再可能成为运行时间的主导因素。

下面是这些行的另一个选项。它再次使用NumPy，但是对每个值进行直接非延迟线性搜索。 （请原谅乱序IPython提示：我加入这一个后来:-)

In [29]: numpy.where(numpy.logical_xor.reduce(numpy.greater_equal.outer(boundaries, nums), axis=0)) 
Out[29]: 
(array([ 2, 3, 4, 5, 6, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 41, 
     42, 43, 44, 45, 46, 47, 48, 49, 50, 51]),) 

In [30]: %timeit numpy.where(numpy.logical_xor.reduce(numpy.greater_equal.outer(boundaries, nums), axis=0)) 
10 loops, best of 3: 16.7 ms per loop 

对于这些特定的测试数据，这比searchsorted快，但时间会在数量呈线性增长。范围，而对于searchsorted，它应该根据范围数量的对数增长。请注意，它也使用与len(boundaries) * len(nums)成比例的内存量。这不一定是一个问题：如果你发现自己遇到了内存限制，你可能会将这些阵列分成更小的尺寸（比如说每次10000个元素），而不会失去太多的性能。

向上移动缩放比例，如果这些都不符合要求，我会接下来尝试使用Cython和NumPy编写搜索功能（将输入声明为整数的数组），对boundaries数组执行简单的线性搜索。我尝试过，但没有得到比基于bisect.bisect更好的结果。作为参考，这里是我尝试的Cython代码;你可以做的更好：

cimport cython 

cimport numpy as np 

@cython.boundscheck(False) 
@cython.wraparound(False) 
def search(np.ndarray[long, ndim=1] boundaries, long val): 
    cdef long j, k, n=len(boundaries) 
    for j in range(n): 
     if boundaries[j] > val: 
      return j & 1 
    return 0 

而且时机：

In [13]: from my_cython_extension import search 

In [14]: %timeit [n for n in nums if search(boundaries, n)] 
1 loops, best of 3: 793 ms per loop 

Answer 2

尝试使用二进制搜索，而不是线性的。它应该花费时间“记录（n）”。见下：

list = [] 
for num in nums: 
    start = 0 
    end = len(ranges)-1 
    if ranges[start][0] <= num <= ranges[start][1]: 
     list.append(num) 
    elif ranges[end][0] <= num <= ranges[end][1]: 
     list.append(num): 
    else: 
     while end-start>1: 
      mid = int(end+start/2) 
      if ranges[mid][0] <= num <= ranges[mid][1]: 
       list.append(num) 
       break 
      elif num < ranges[mid][0]: 
       end = mid 
      else: 
       start = mid 

Answer 3

@ ArminRigo的评论，这是非常快的实施。时机是从CPython的，没有PyPy：

exec_code = "def in_range(x):\n" 
first_if = True 
for r in ranges: 
    if first_if: 
     exec_code += " if " 
     first_if = False 
    else: 
     exec_code += " elif " 
    exec_code += "%d <= x <= %d: return True\n" % (r[0], r[1]) 
exec_code += " return False" 
exec(exec_code) 

%timeit [n for n in nums if in_range(n)] 
# 10 loops, best of 3: 173 ms per loop