我會用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
區間樹看起來很完美。當我回家時我會執行它。 – 2011-04-14 19:26:34
@Ken:請注意,線性時間算法對間隔樹進行一些小的調整,因爲這些算法會爲您進行排序,但以智能方式對間隔進行排序可能比產生平衡間隔搜索樹更容易。 – 2011-04-14 22:02:32