比较重叠范围
|
我将使用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
没有找到相关结果
已邀请:
3 个回复
死簇
(希望您可以阅读Scheme :)
豪抱怒掳
列表进行排序,那么对于
中的每个范围,您都可以进行二进制搜索以获取其下界小于或等于所讨论范围的范围的子集。然后,您需要在该子集中顺序搜索那些上限大于或等于所测试范围的上限的子集。 最糟糕的情况仍然是O(n ^ 2),因为所有
范围都可能具有满足条件的下限,但使用实际数据的运行时间可能会少得多。
抬澈帅沮