比较重叠范围

Question

我将使用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

- Ken Bloom

Answer 1

尝试使用区间树。Cormen、Leiserson、Rivest和Stein在（如果我没记错的话）第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 :）

- Fred Foo

---

区间树看起来很完美。我回家后会去实现它。 - Ken Bloom

@Ken：请注意，线性时间算法适用于区间树，并进行了一些微小的调整，因为它们会为您进行排序，但是以聪明的方式对区间进行排序可能比生成平衡的区间搜索树更容易。 - Fred Foo

Answer 2

如果您可以按范围开始值对groundtruth列表进行排序，那么对于testresult中的每个范围，您可以进行二进制搜索以获取其低边界小于或等于所测试范围的范围子集。然后，您需要顺序搜索该子集，以查找高边界大于或等于您正在测试的范围的高边界的范围。

最坏情况仍然是O(n^2)，因为所有groundtruth范围都可能具有满足条件的低边界，但实际数据的运行时间可能会少得多。

- Jim Mischel

Answer 3

如果将groundtruth存储在哈希集合中，则检查其中测试结果成员的存在将是O(n)。

编辑：我没有意识到您仅使用由其端点表示的范围。天啊！

某种基于树的结构肯定是您最好的选择。

- Marcin

---

“重叠”关系不是等价关系，因此它不能在哈希表中进行常数时间查找。 - Ken Bloom

正确，但整数的相等性是如此，因此您可以在groundtruth哈希集中查找testresult中的单个整数。操作的总成本将与testresult的大小成线性关系。 - Marcin

所以你建议使用val ranges = new scala.collection.mutable.HashSet[Int]; for (gt <- groundtruth; point <- gt) ranges += point; val result = testresult.filter{ tr => tr.exists{point => ranges(point)}}。当范围较短时，这种方法可以很好地工作，但是当范围较长时（即平均大小为100），会浪费很多时间。 - Ken Bloom

我对你的Scala代码的含义还不是很清楚。我没有意识到你的测试结果被存储为范围。 - Marcin