寻找另一个数字之间的哪一对数字的优化方法？

Question

鉴于行区域的列表：

regions = [(10,25), (18, 30), (45, 60), ...] # so on so forth, regions can be overlapping, of variable size, etc. 

我想知道X点属于哪个国家和地区：

x = 23 
find_regions(regions, x) # ==> [(10, 25), (18, 30)] 

我天真地知道（和我目前的执行情况），我们可以只搜索在O（N），而是一个更生动的案例与成千上万的区域（的查找点千万，真的，是激励）都不能证明调查比这更快的方法：

regions = [(start, end) for (start, end) in regions if start < x and x < end] 

我会冒险猜测有人已经在......之前解决了这个问题，但我不确定它是如何最好地完成的。思考？

Answer 1

这是确切的工作interval trees被设计来做。谷歌搜索Python interval tree成立了一个名为Banyan的实现它们的现有库，尽管我不能说它的可靠性，并且似乎没有积极开发。你也可以实现你自己的区间树。

从N个区间列表构造一个区间树的预处理时间在O（Nlog（N））中，与其他答案不同，它只需要O（N）空间，不管多少间隔重叠。计算给定点有多少间隔重叠的时间是O（M + log（N）），其中M是包含该点的间隔数。

榕树间隔树演示，从PyPI page被拉：

>>> t = SortedSet([(1, 3), (2, 4), (-2, 9)], updator = OverlappingIntervalsUpdator) 
>>> 
>>> print(t.overlap_point(-5)) 
[] 
>>> print(t.overlap_point(5)) 
[(-2, 9)] 
>>> print(t.overlap_point(3.5)) 
[(-2, 9), (2, 4)] 
>>> 
>>> print(t.overlap((-10, 10))) 
[(-2, 9), (1, 3), (2, 4)] 

Answer 2

我会做你的列表理解，唯一的变化是，使之成为generator，缩短比较start < x < end，并有选择地打电话next()如果你只需要一个：

>>> regions = [(10,25), (18, 30), (45, 60)] 
>>> x = 23 
>>> next((start, end) for (start, end) in regions if start < x < end) 
(18, 30) 

还要注意你的比较start > x and x < end有倒退>。应该是start < x and x < end。这个修复程序包含在我的答案

---

编辑：看到评论和解答关于二进制搜索让我意识到，我当然绝对错误的，缺乏改进的余地的。也就是说，为了通过next()稍作改善的比较和短路，我仍然会保留这个答案。但与二进制搜索相比，我的改进是微不足道的。

我让你的搜索线性更快。二进制是对数的。

Answer 3

如果区域重叠，只需对区域进行排序并执行二进制搜索。

如果区域重叠，对于每个重叠区域计算重叠区域的列表并将它们存储为列表。然后做一个二进制搜索。

例如：（1,10），（5,15） 转换为

(1,4), (5,10), (11, 15) 
    |  |  | 
(1,10) (1,10) (5,15) 
      | 
     (5,15) 

即，连杆（5,10）到它所属的区域。

注意：这些只是线索，你需要做更多的工作。

Answer 4

我建议你将一切分成不重叠的基本区间，这样每个基本区间要么完全被覆盖，要么完全在任何给定区间之外。然后你创建一个从基本区间到给定区间的映射。由于基本区间不重叠，因此您可以使用二进制搜索轻松找到匹配的区域。从中你可以查找哪些实际时间间隔映射到它。 初始排序是O（N log N），由于二进制搜索，构建映射为O（N），最终查找为O（log N）。基本区间的数量小于2 * N。

下面是这个粗略的实现。不确定搜索点到底是否结束间隔结束的情况。

class IntervalFinder(): 
    elem_list = [] # the borders of the elementary interval 
    elem_sets = [] # the actual intervals mapped to each elementary 
    def __init__(self, intervals): 
     # sort the left ends 
     a = sorted(intervals) 
     # sort the right ends 
     b = sorted(intervals, key=lambda x : x[1]) 
     ia = 0 # index into a 
     start = a[0][0] # the start of the elementary interval 

     # the set of actual intervals covering the 
     # current elementary 
     current = set() 
     for xb in b: 
      while ia < len(a) and a[ia][0] < xb[1]: 
       stop = a[ia][0] 
       # an elementary interval ends here 
       # because a new interval starts 
       if stop > start: 
        self.elem_sets.append(set(current)) 
        self.elem_list.append(start) 
        start = stop 
       current.add(a[ia]) 
       ia += 1 

      if start < xb[1]:      
       self.elem_sets.append(set(current)) 
       self.elem_list.append(start) 
       start = xb[1] 

      current.remove(xb) 

     self.elem_sets.append(set()) 
     self.elem_list.append(start) 


    def find(self, a): 
     k = bisect.bisect(self.elem_list, a) - 1 
     if k<0: 
      return set() 
     # if its exactly on the border 
     # it belongs to both the right and the left 
     if a == self.elem_list[k]: 
      h = set(self.elem_sets[k]) 
      return h.union(self.elem_sets[k-1]) 
     else: 
      return self.elem_sets[k] 

intervals = [ (1, 10), (5, 15), (10, 20), (5, 30) ] 

ifind = IntervalFinder(intervals) 
for x in [0, 4,5,9,10,11, 20, 25, 30, 35]: 
    print(x, ifind.find(x))