1

2 つのリストで重複するすべての範囲を効率的に見つけるのに問題があります。この問題はこの質問に
似ていますが、入力が異なります。

2 つの入力ファイルがあります。1 つは範囲とデータのペアの多くの行を含み、もう 1 つは交点を見つけるための範囲のリストを含みます。

データ ファイルから読み取り、範囲とデータのペアのリストを保持するオブジェクトを一度に 1 つずつ返すファイル リーダー クラスを既に作成しましたが、2 つの範囲リストの重複を見つけようとすると問題が発生します。

現在私が行っているのは、データ リスト内のすべての範囲を共通部分リスト内の他のすべての範囲と比較するブルート フォースですが、データ ファイルが非常に大きいため、時間がかかります。

サンプル オブジェクト:
これは、データ リスト内のオブジェクトです。

public DataModel {
    private int start; {set; get;}
    private int end; {set; get;}
    //Other Data
}

モデルの範囲は、対になった整数 (開始、終了) の単なるリストです。

while (fileParser.hasNext()) {
    dataList = fileParser.next();
    for (DataModel data : dataList)
        for (RangeModel range : rangeList)
            if(overlaps(data, range))
                print(range.getString + " " + data.getString);
}

わかりやすくするために編集します。

DataModel は、さまざまな長さの同様の範囲の小さなパケットで提供されますが、ほとんどが 20 未満であるため、比較は同じ RangeModel とそれぞれの新しい DataModel で繰り返し実行されます。すべてのデータの合計範囲は約 20 億ですが、実際には問題ではありません。助けてくれてありがとう。

4

4 に答える 4

1

さまざまな最適化を考えることができますが、それらはチェック後にどのような種類のデータを利用できるかによって異なります。

データと範囲の両方を並べ替えて順番に処理すると、100で始まる範囲を、50で終わる別の範囲に対してテストする意味がないため、パフォーマンスが即座に向上します。

もう1つの改善点は、範囲を「圧縮」することです。（1-10）、（10-20）、（20-30）のような範囲がある場合は、それらを単一の（1-30）範囲に簡単に置き換えて、テストの数を減らすことができます。どの元の範囲がオーバーラップを引き起こしているのかを知りたい場合に備えて、構成範囲のIDを追跡する適切なAggregateRangeクラスを作成できます。

さらに別の改善点は、データリストを処理するときに以前の結果をスマートに使用することです。例：データ範囲（1〜10）をテストし、それがたまたま重複していないとします。次のテストデータ範囲が（2〜8）の場合、前の結果で重複しないことが保証されているため、範囲に対してテストする必要はありません。

この改善の背後にある基本的な考え方は、テストされていないデータ範囲の開始を、最後の重複しないデータ範囲の終了まで進めることです。新しい開始がそれ自体の終了を超える場合、重複しないため、テストは必要ありません。つまり、重複しない（1-20）は、テストされていない（10-100）をテストされていない（20-100）に変換する必要があります。これは実装が難しい場合があるため、やりすぎないように注意してください。

于 2013-01-16T21:03:43.300 に答える
1

私の理解が正しいかどうかを確認してください。

  • DataModel と RangeModel は範囲を表します。(DataModel にはさらに多くのデータが含まれる場合がありますが、それは無関係です)。
  • 約あります。200 万DataModels、および少数のRangeModels。（ただし、私のソリューションはこの非対称性を利用していません）
  • 重複している場合でも、DataModel 内の範囲を異なるエンティティとして保持する必要があります。(交差のみに関心がある場合は、最適化として、それらが互いに近くにあるときに範囲を折りたたむことができます)。

これから説明する方法では、範囲がどのように見えるか (重複、大きな範囲など) に関係なく、範囲の 2 つのリスト間で範囲交差を行うことができます。制限は、範囲の 2 つのリストのサイズの合計 (並べ替えがボトルネック) と、見つかった範囲の数 (反復がボトルネック) です。

範囲を 2 つのオブジェクトに分割しEndPointます。これは、値 ( int)、範囲の開始または終了 ( boolean)、開始EndPointオブジェクト (範囲の開始。範囲の終了の場合は範囲​​の開始を表すオブジェクトをnull指します)、タグ ( 、それがデータであるか、クエリする範囲であるかを示します)。EndPointint

範囲の両方のリストからすべてのEndPoints をまとめて、値で並べ替え、開始を終了エンドポイントの前に置くことでタイ ブレークします (タッチが交差であると考える場合)。ソートステップの複雑さは O((m + n)log(m + n)) です。

EndPoint次の疑似コードに従って、ソートされた s をループします。

open_data = HashSet()
open_range = HashSet()

for e in endpoints:
  if e is start of range:
    if e is data:
      print e intersect with all in open_range
      open_data.add(e)
    else: // e is range to test
      print e intersect with all in open_data
      open_range.add(e)
  else: // e is end of range
    if e is data:
      open_data.remove(e.startPoint)
    else: // e is range to test
      open_range.remove(e.startPoint)

HashSet への追加と削除は、O(1) で償却されます。問題は、交差の印刷にあり、これは O(k) です。ここで、k は交差の数であり、最悪の場合は最大で O(m * n) になる可能性があります。

組み合わせると、複雑さは最悪の場合 O((m + n)log(m + n) + m * n) になります。データのプロパティに基づいて、より適切に実行できる場合があります。これは非常に一般的な解決策です。

于 2013-01-16T22:03:48.257 に答える
0

理想的なソリューションは、データの特定の特性によって異なりますが、2 つの入力セットを並べ替えることが最初のステップとして適切であり、必要な比較の量を減らすことができます。

1 つのオプションは、min(startTime) から max(endTime) までの配列を作成し、各位置に、この範囲をカバーする入力値への参照を格納することです。

したがって、入力が
A: [1-5] および B:[3-7] の場合、次のようなデータ構造を持つことができます。

1: A
2: A
3: A,B
4: A,B
5: A,B
6: B
7: B

次に、[2-4] とデータ セットの交差をテストするには、配列リストで 2,3,4 を検索し、結果を連結します。

交差点が誰と正確に交わっているかではなく、交差点がある場合のみを気にする場合は、さらに速度を向上させることができます。または、すべての交差点ではなく、AN 交差点のみを気にする場合。

于 2013-01-16T21:06:31.513 に答える
0

範囲o（N ln N）の各リストをソートし、それらの範囲O（N）のマージソートを実行できます

これにより、最小限の CPU 時間で重複する範囲が表示されます。

于 2013-01-16T21:34:10.213 に答える