比较重叠范围

Question

我将使用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)时间来运行.

是否有更快的算法来计算这个结果,或者是一个可以提高exists测试效率的数据结构？

---

PS该算法应该使用如下表达式进行处理groundtruth和testresult生成.换句话说,不保证列表中的范围之间的关系,Ranges的平均大小为100或更大.

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

Answer 1

尝试间隔树.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)))))

(我希望你能看到方案:)