我将使用 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
换句话说,不能保证列表中范围之间的关系,Range
s 的平均大小为 100 或更大。
(1 to 1000).map{x =>
val midPt = r.nextInt(100000);
((midPt - r.nextInt(100)) to (midPt + r.nextInt(100)));
}.toList