4

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

3 回答 3

9

试试区间树。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 :)

于 2011-04-14T19:04:45.260 回答
0

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

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

于 2011-04-14T19:06:14.233 回答
0

如果 groundtruth 存储在散列集中，检查其中是否存在测试结果成员将是 O(n)。

编辑：我没有意识到您只使用由它们的端点表示的范围。哦！

某种基于树的结构必须是你最好的选择。

于 2011-04-14T22:50:30.797 回答