查找號碼範圍交叉點

Question

找出兩個號碼範圍是否相交的最佳方法是什麼？

我的號碼範圍是3023-7430，現在我想測試其以下數量範圍與它相交：< 3000，3000-6000，6000-8000，8000-10000，> 10000。答案應該是3000-6000和6000-8000。

什麼是在任何編程語言中做到這一點的好的，有效的數學方法？

Answer 1

只是一個僞代碼的猜測：

Set<Range> determineIntersectedRanges(Range range, Set<Range> setofRangesToTest) 
{ 
    Set<Range> results; 
    foreach (rangeToTest in setofRangesToTest) 
    do 
    if (rangeToTest.end <range.start) continue; // skip this one, its below our range 
    if (rangeToTest.start >range.end) continue; // skip this one, its above our range 
    results.add(rangeToTest); 
    done 
    return results; 
} 

Answer 2

我會做一個範圍類，並給它一個方法布爾相交（範圍）。然後，你可以做一個

foreach(Range r : rangeset) { if (range.intersects(r)) res.add(r) } 

交叉口本身是一樣的東西

this.start <= other.end && this.end >= other.start 

Answer 3

這在很大程度上取決於你的範圍。範圍可以大或小，並且可以聚類或不聚類。如果你有很大的聚集範圍（想想「可以除以2的所有正32位整數），那麼範圍（低，高）的簡單方法將不會成功。

我想我可以說下列： 如果你有小的範圍（聚類或不聚類在這裏沒有關係），考慮位向量。這些小動物在聯合，相交和成員測試方面快速發展，即使對所有元素的迭代可能需要一段時間，取決於而且，因爲他們只是每個元素使用一個位，所以它們非常小，除非你在它們上面投射很大的範圍

如果你有更少，更大的範圍，那麼一個類別由別人描述就足夠了這個類有屬性上下交點（a，b）基本上是a.lower或a.upper> b.lower。聯合和交叉點可以在單個範圍和複雜範圍內以恆定的時間實現，時間隨着子範圍的數量而增長（因此您不希望太多的小範圍）

如果您有一個巨大的空間你的數字可能是，而且範圍分佈在一個討厭的時尚，你應該看看二元決策圖（BDD）。這些漂亮的圖有兩個終端節點，True和False以及輸入的每個位的決策節點。一個決策節點看起來有一點，後面有兩個圖形節點 - 一個是「位是一」，另一個是「位是零」。鑑於這些條件，您可以在很小的空間內對大範圍進行編碼。任意大數的所有正整數可以編碼在圖中的3個節點中 - 基本上是最低有效位的單個決策節點，其在1上變爲False並且在0上變爲True。

交集和聯合都很漂亮遞歸算法，例如，交集基本上在每個BDD中佔用兩個相應的節點，遍歷1-邊直到彈出一些結果並檢查：如果其中一個結果是False-Terminal，則創建一個1分支到False-終端在結果BDD中。如果兩者都是真實終端，則在結果BDD中爲真正終端創建1分支。如果是別的東西，在結果BDD中爲此創建一個1分支。在那之後，一些最小化踢入（如果一個節點的0和1分支到達相同的下一個BDD /終端，將其移除並且將傳入的轉換拉到目標），並且你是黃金。我們甚至比這更進一步，我們致力於模擬在BDD上添加整數集以增強價值預測，從而優化條件。

這些注意事項意味着您的操作受數字範圍內的位數限制，即log_2（MAX_NUMBER）。試想一下，你可以在幾乎不變的時間內交叉64位整數的任意集合。

更多信息可以在例如Wikipedia和參考文件中找到。

此外，如果錯誤肯定是可承受的並且您只需要存在檢查，則可以查看Bloom過濾器。布隆過濾器使用哈希向量來檢查一個元素是否包含在表示的集合中。交叉路口和聯盟是不變的時間。這裏的主要問題在於，如果您填充bloom-filter太多，您會得到越來越高的假陽性率。例如， 信息，同樣在Wikipedia中。

哈希，集合表示是一個有趣的領域。 :)

Answer 4

在蟒蛇

class nrange(object): 
    def __init__(self, lower = None, upper = None): 
     self.lower = lower 
     self.upper = upper 
    def intersection(self, aRange): 
     if self.upper < aRange.lower or aRange.upper < self.lower: 
      return None 
     else: 
      return nrange(max(self.lower,aRange.lower), \ 
          min(self.upper,aRange.upper)) 

Answer 5

如果您使用的是Java Commons Lang Range 有 overlapsRange（量程範圍）方法。