比較重疊範圍

我會用Scala語法問這個問題，即使這個問題真的是語言獨立的。比較重疊範圍

假設我有兩個列表

val groundtruth:List[Range] 
val testresult:List[Range]

而且我想找到所有的重疊groundtruth一些元素的testresult元素。

我能做到這一點，如下所示：

def overlaps(x:Range,y:Range) = (x contains y.start) || (y contains x.start) 
val result = testresult.filter{ tr => groundtruth.exists{gt => overlaps(gt,tr)}}

但這需要O(testresult.size * groundtruth.size)時間來運行。

有沒有更快的算法來計算這個結果，或者一個數據結構，可以使exists測試更有效？

P.S.該算法應該在使用如下表達式生成的groundtruth和testresult上工作。換句話說，對於列表中的範圍之間的關係沒有任何保證，Range的平均大小爲100或更大。

(1 to 1000).map{x => 
    val midPt = r.nextInt(100000); 
    ((midPt - r.nextInt(100)) to (midPt + r.nextInt(100))); 
}.toList

來源

2011-04-14 Ken Bloom

試試interval tree。 Cormen, Leiserson, Rivest and Stein在（IIRC）第14章中討論了這些問題。

或者，如果您的間隔列表均已排序並且列表中的間隔不重疊，那麼以下算法將以線性時間和單遍方式解決您的問題在兩個名單：

(define interval cons) 
(define lower car) 
(define upper cdr) 

(define (overlap a b) 
    (cond ((or (null? a) (null? b)) '()) 
     ((< (upper a) (lower b)) 
     (overlap (cdr a) b)) 
     ((> (lower a) (upper b)) 
     (overlap a (cdr b))) 
     (#t ;; (car a) and (car b) overlap 
      ;; EDIT: there's a bug in the following part. 
      ;; The code shouldn't skip over both cars at once, 
      ;; since they may also overlap with further intervals. 
      ;; However, I'm too tired to fix this now. 
     (cons (interval (max (lower a) (lower b)) 
         (min (upper a) (upper b))) 
       (overlap a b)))))

（我希望你能閱讀計劃:)

來源

2011-04-14 19:04:45

區間樹看起來很完美。當我回家時我會執行它。 – 2011-04-14 19:26:34

@Ken：請注意，線性時間算法對間隔樹進行一些小的調整，因爲這些算法會爲您進行排序，但以智能方式對間隔進行排序可能比產生平衡間隔搜索樹更容易。 – 2011-04-14 22:02:32

如果你能排序開始價值groundtruth列表中的範圍，然後爲每個在testresult你可以做一個二進制搜索，獲得範圍下限小於或等於ra的範圍的子集有問題的。然後，您需要按順序搜索那些上限大於或等於您正在測試的範圍的上限的那些子集。

最壞的情況仍然是O（n^2），因爲所有的groundtruth範圍都有可能達到標準的低限，但實際數據的運行時間可能會少得多。

來源

2011-04-14 19:06:14

如果將groundtruth存儲在哈希集合中，檢查其中的測試結果成員的存在將是O（n）。

編輯：我沒有意識到你只是在用他們的端點表示的範圍工作。 D'哦！

某種基於樹的結構已成爲您的最佳選擇。

來源

2011-04-14 22:50:30 Marcin

「重疊」關係不是[等價關係]（http://en.wikipedia.org/wiki/Equivalence_relation），所以它不適合在散列表中進行恆定時間查找。 – 2011-04-15 02:38:07

正確，但整數相等，因此您可以在groundtruth哈希集中的testresult中查找單個整數。該操作的總成本將與testresult的大小成線性關係。 – Marcin 2011-04-15 12:00:59

所以你建議'val ranges = new scala.collection.mutable.HashSet [Int];對於（gt < - groundtruth; point < - ）範圍+ = point; val結果= testresult.filter {tr => tr.exists {point =>範圍（點）}}'當範圍很短時可以很好地工作，但當範圍很長時會浪費很多時間（即平均大小是100）。 – 2011-04-15 15:47:28

比較重疊範圍

回答

相關問題