比较重叠范围

| 我将使用Scala语法提出这个问题,即使该问题确实与语言无关。 假设我有两个清单
val groundtruth:List[Range]
val testresult:List[Range]
我想找到
testresult
中与
groundtruth
中某些元素重叠的所有元素。 我可以这样做,如下所示:
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)
的时间来运行。 是否有用于计算此结果的更快算法,或者可以使“ 5”测试更有效的数据结构? 附言该算法应适用于通过如下表达式生成的
groundtruth
testresult
。换句话说,不能保证列表中范围之间的关系,“ 8”的平均大小为100或更大。
(1 to 1000).map{x =>
   val midPt = r.nextInt(100000);
   ((midPt - r.nextInt(100)) to (midPt + r.nextInt(100)));
}.toList
    
已邀请:
尝试间隔树。 Cormen,Leiserson,Rivest和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)))))
(希望您可以阅读Scheme :)     
如果您可以按范围起始值对
groundtruth
列表进行排序,那么对于
testresult
中的每个范围,您都可以进行二进制搜索以获取其下界小于或等于所讨论范围的范围的子集。然后,您需要在该子集中顺序搜索那些上限大于或等于所测试范围的上限的子集。 最糟糕的情况仍然是O(n ^ 2),因为所有
groundtruth
范围都可能具有满足条件的下限,但使用实际数据的运行时间可能会少得多。     
如果将groundtruth存储在散列集中,则检查测试结果中成员的存在将为O(n)。 编辑:我没有意识到您只是在使用由其端点表示的范围。噢! 某种基于树的结构必须是最好的选择。     

要回复问题请先登录注册