尋找另一個數字之間的哪一對數字的優化方法？

鑑於行區域的列表：尋找另一個數字之間的哪一對數字的優化方法？

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]

我會冒險猜測有人已經在......之前解決了這個問題，但我不確定它是如何最好地完成的。思考？

來源

2014-02-11 zaczap

爲什麼會'find_regions（區域中，x）'返回'[（10，20），（22，30）]'？ – Bach

忘了將該示例更新爲原始定義（18,30） – zaczap

我仍然不明白。「23」屬於「該地區（10,20）」的含義？ – Bach

這是確切的工作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)]

來源

2014-02-11 08:49:04 user2357112

我會做你的列表理解，唯一的變化是，使之成爲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()稍作改善的比較和短路，我仍然會保留這個答案。但與二進制搜索相比，我的改進是微不足道的。

我讓你的搜索線性更快。二進制是對數的。

來源

2014-02-11 07:05:38 mhlester

如果區域重疊，只需對區域進行排序並執行二進制搜索。

如果區域重疊，對於每個重疊區域計算重疊區域的列表並將它們存儲爲列表。然後做一個二進制搜索。

例如：（1,10），（5,15）轉換爲

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

即，連桿（5,10）到它所屬的區域。

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

來源

2014-02-11 07:15:36 ElKamina

排序本身是O（NlogN），而他最初的想法是O（N）。但從長遠來看，預先排序的方法會擊敗O（N^M）方法。 – thefourtheye

我建議你將一切分成不重疊的基本區間，這樣每個基本區間要麼完全被覆蓋，要麼完全在任何給定區間之外。然後你創建一個從基本區間到給定區間的映射。由於基本區間不重疊，因此您可以使用二進制搜索輕鬆找到匹配的區域。從中你可以查找哪些實際時間間隔映射到它。初始排序是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))

來源

2014-02-11 08:39:16 pentadecagon

尋找另一個數字之間的哪一對數字的優化方法？

回答

相關問題