4

質問は実際には言語に依存しませんが、Scala 構文を使用してこの質問をします。

2つのリストがあるとします

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の平均サイズは 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 章でこれらについて説明しています。

あるいは、間隔のリストが両方ともソートされていて、リスト内の間隔が重複していない場合、次のアルゴリズムは問題を線形時間で解決し、両方のリストを 1 回パスします。

(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

グラウンドトゥルースがハッシュされたセットに格納されている場合、テスト結果のメンバーの存在をチェックするのは O(n) になります。

編集:エンドポイントで表される範囲のみを使用していることに気づきませんでした。ああ！

ある種のツリーベースの構造が最善の策です。

于 2011-04-14T22:50:30.797 に答える
0

範囲の開始値でリストを並べ替えることができればgroundtruth、範囲ごとにtestresultバイナリ検索を実行して、下限が問題の範囲以下である範囲のサブセットを取得できます。次に、上限がテストしている範囲の上限以上であるサブセットを順次検索する必要があります。

groundtruthすべての範囲が基準を満たす下限を持つ可能性があるため、最悪の場合でも O(n^2) ですが、実際のデータでの実行時間ははるかに短くなる可能性があります。

于 2011-04-14T19:06:14.233 に答える