在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