java - O（n）よりも優れた範囲交差アルゴリズム？

Question

範囲の交差は単純ですが、重要な問題です。

それはすでに2回答えられています：

• 番号範囲の共通部分を検索
• 日付範囲の比較

最初の解決策はO（n）であり、2番目の解決策はデータベース用です（もちろんO（n）未満です）。

私は同じ問題を抱えていますが、nが大きい場合、データベース内にいません。

この問題は、長方形内のポイントをすばやく取得するための2Dポイントの保存と非常に似ているようですが、どのようにマッピングされるかわかりません。

では、範囲の検索のコストがO（n）未満になるように、範囲のセットをどのデータ構造に格納しますか？（Javaで利用可能なライブラリを使用するための追加のクレジット）

編集：

交差するすべての範囲のサブセットを取得したいのですが、検索範囲が複数の範囲と交差する可能性があることを意味します。

JavaでO（n）未満である必要があるメソッドは次のとおりです。

public class RangeSet {
    ....
    public Set<Range> intersects(Range range);
    ....
}

Rangeは、intの開始と終了のペアを含む単なるクラスです。

これは不可能な質問ではありません、私はすでに解決策を持っています、私はそれを行うためのより標準的/より簡単な方法があるかどうかを見たかっただけです

Answer 1

標準的なアプローチは、インターバル ツリーを使用することです。

コンピューター サイエンスでは、インターバル ツリーは、インターバルを保持するためのツリー データ構造です。具体的には、任意の間隔またはポイントと重なるすべての間隔を効率的に見つけることができます。たとえば、長方形のビューポート内のコンピューター化された地図上のすべての道路を検索したり、3 次元シーン内のすべての可視要素を検索したりするために、ウィンドウ クエリによく使用されます。同様のデータ構造は、セグメント ツリーです。

簡単な解決策は、各間隔にアクセスし、指定されたポイントまたは間隔と交差するかどうかをテストすることです。これには O(n) 時間が必要です。ここで、n はコレクション内の間隔の数です。クエリはすべての間隔を返す可能性があるため、たとえば、クエリがコレクション内のすべての間隔と交差する大きな間隔である場合、これは漸近的に最適です。ただし、クエリによって生成される間隔の数である m でランタイムが表現される、出力に依存するアルゴリズムを検討することで、より良い結果を得ることができます。間隔ツリーのクエリ時間は O(log n + m)、初期作成時間は O(n log n) ですが、メモリ消費は O(n) に制限されています。作成後、間隔ツリーは動的になり、O(log n) で間隔を効率的に挿入および削除できます。区間の端点が小さな整数範囲内にある場合 (たとえば、範囲 [1,...,

Answer 2

編集： このソリューションは多かれ少なかれInterval Tree のようです。インターバル ツリーのより完全な実装については、こちらを参照してください。

class TreeNode
{
public:
    long pivot;
    List<Range> leaves;  //Any ranges that intersect the pivot
    TreeNode left;        //Tree nodes that fall to the left of the pivot
    TreeNode right;       //Tree nodes that fall to the right of the pivot
};

準備 O(n log n):

1. 範囲のリストを作成する
2. ピボット ポイントを選択します (おそらく、終了日の並べ替えられたリストを使用します)。
3. ツリーを構築します。

探す：

1. 二分探索を使用して、>= TestRange.End である最初のピボットを見つけます。

2. ピボットまでツリーをトラバース > TestRange.Start

   2a. 結果に葉を追加します。

---

例：

範囲:

• 0 - 2
• 1 - 2
• 2 - 3
• 1 - 4
• 2 - 4
• 0 - 5
• 4 - 5
• 2 - 6
• 3 - 7

木：

                             4
               --------------+------------------
               3             |                 7
               |            1-4                |
               |            2-4                |
               |            0-5                |
               |            4-5                |
      ---------+------                 --------+--------
      2        |    null              6        |       null
 -----+----   2-3                 ----+----   3-7
null  |  null                   null  |  null    
     0-2                             2-6
     1-2

Answer 3

重複しない範囲:

準備 O(n log n):

1. 範囲の配列/ベクトルを作成します。
2. 範囲の終わりでベクトルを並べ替えます (範囲の始まりで並べ替えることでタイを破ります)

探す：

1. 二分探索を使用して、>= TestRange.Start の End 値を持つ最初の範囲を見つけます。

2. Start > TestRange.End が見つかるまで二分探索から開始する反復子:

   2a. 現在の範囲が TestRange 内にある場合は、それを結果に追加します。

Answer 4

重複する範囲:

準備 O(n log n):

1. 範囲の配列/ベクトルを作成します。
2. 範囲の終わりでベクトルを並べ替えます (範囲の始まりで並べ替えることでタイを破ります)

3. int の 2 番目のベクトルを作成します。これは、検索を停止できるポイントを表します。

   int stop[size];
   stop[size-1] = Ranges[size - 1].start;
   for (int i = size - 2; i >= 0; i--)
   {
       stop[i] = min(Ranges[i].start, stop[i+1]);
   }
   

探す：

1. 二分探索を使用して、>= TestRange.Start の End 値を持つ最初の範囲を見つけます。

2. stop[i] > TestRange.End までの二分探索から始まる反復子:

   2a. 現在の範囲が TestRange 内にある場合は、それを結果に追加します。

Answer 5

範囲が重複していて、特定のターゲット範囲と重複する (または含む)すべての範囲を取得したい場合、上記のソリューションのほとんどは機能しないようです。

一部の人が指摘しているように、(最悪の場合)すべての範囲がたまたまターゲット範囲と交差する場合 (たとえば、ターゲット範囲が {0..MAXINT} などの場合)、もちろん、返すのに O(n) が必要です。 n 範囲。

しかし、興味深い典型的/平均的なケースではありませんか? n の合計範囲のごくわずかな % のみがターゲット範囲と交差します。「m」と交差する数を呼び出します。その場合、おそらく O(m) と同じように実行できる可能性があります。そして、n=10^9 で m=10 の場合、それは決定的な違いです。

「タイプ」のためにマークアップされたさまざまな領域を持つテキスト ドキュメントの単純なケースを考えてみましょう。おそらく、指定された連続したテキスト範囲 (たとえば、段落) を含むか交差するすべてのマークアップされた単位を見つけたいと思うでしょう。HTML、XML、または同様のものでは、ターゲット範囲の少なくともいくつかの文字を含む text-node(s) の先祖にのみなることができます。各ノードに親ポインターを持つ典型的な表現では、これは O(m) です。特に、m は (短いターゲット範囲または同期ターゲット範囲の場合) 単にツリーのネストの深さであり、O(n) よりもさらに低くなる傾向があるためです。 ln(n) というのは、実際の大きな XML ドキュメントは、深くなるのではなく、より多くなるからです。

興味深いケースはもっと難しいです。「要素」が XML のようにツリーを形成せず、MECS、CLIX、LMNL、およびその他のシステムのようにオーバーラップできる場合はどうなるでしょうか? ターゲットと重複するすべての領域/「要素」を見つけたいと思っていますが、それらはそれほど簡単に整理されていません。

一方、多くのアプリケーションのマークアップ範囲はたいてい小さいため、非常にうまく処理できるはずです。本には、章よりもはるかに多くの単語、文、およびパラグラフがあります。そのため、ターゲットの前に始まる膨大な数の範囲と、その後に終わる膨大な数の範囲が存在する場合でも、交差は平均して非常に小さくなります。

それが元の質問者が得ていたものだと思います。残念ながら、その問題に対処する答えは見当たりませんでした。元の質問の内容と異なる場合は、新しい質問として提起したいと思います。

Answer 6

これは、リンクされた質問の正確な問題、明確で共通部分がない範囲、および検索された範囲が複数の範囲にまたがる可能性がある範囲によって異なります。問題が同じ場合、それは非常に簡単です。範囲の配列を取得し、それらを最小値で並べ替えます (それらは重複しないため、これは上位値で並べ替えた場合と同じ順序になります)。

次に、ターゲットの下限値（正確でない場合は小さい）とターゲットの上限値（正確でない場合は大きい）のビンサーチを作成します。結果のインデックスは、カバーされる範囲です。インデックス自体の範囲が含まれているか除外されているかを確認する必要がありますが、それは2つの確認だけです。全体的な複雑さ O(log n)。

Answer 7

四分木が2Dポイントのセットに対して機能するのと同じように、この場合は単純な二分木が機能するはずです。範囲を使用してツリーを構築します。

さらに説明すると、ツリーの各ノードには、範囲の開始と終了の2つの整数と、リーフノードでない場合は2つの子が含まれます。入力範囲がまたがる範囲を見つけるには、ツリーの一番上から始めます

  - if the node range intersects the input range:
     - if it's a leaf node, then add the range to your result list
     - if it's not a leaf node, then traverse down to the child nodes and repeat this process.

O（logN）である必要があります

詳細：二分木は、四分木の1次元バージョンのように構造化されます。各ノードには3つの整数があります（申し訳ありませんが、上記の2つが必要ですが、3つ必要です）。最小値は、このノードの下にある最小範囲の最小値を表し、最大値は、これより下にある最大範囲の最大値を表します。ノード、およびピボット。左の子は、このノードの最下位からピボットにまたがります。右の子は、このノードのピボットからこのノードの最高値までに及びます。「最低」から「最高」までの範囲が1つしかない場合は、ピボットがなく、これがリーフになります。理想的には、ツリーのバランスを保つために、各ノードのピボットを選択します。

Answer 8

SortedSet インターフェイスを実装するクラスが必要なようです。TreeSet は、コア API に同梱されている実装です。

最小値でソートされた範囲を保持するセットと、最大値でソートされたセットを用意します。

次に、メモリ内セットを使用して、データベース アルゴリズムと同等のものを実装できます。

これが実際に O(n) よりも速いかどうかはわかりません。

Answer 9

この問題が発生したとき、ソートされた範囲の配列と二分探索を使用して交差を探しました。これは (私が信じている) O(log n) のパフォーマンスであり、重複する範囲を処理するためのオーバーヘッドが少しあります。

あなたの質問への答えは、以下のコードから導き出せると思いますが、挿入には至りません。異なるコンテキストによる混乱を避けるために、コード全体を提示します。Unicode コードポイントの範囲をコードポイント範囲のリストに挿入する必要がありました。

- 編集 -

複数の範囲の交差を決定するために以下のコードを適応させるには、交差しなくなる範囲が見つかるまで、挿入ポイントから簡単な前方検索を行います。

-- 編集終了 --

Range クラスには以下が含まれます。

final int                               lower;                                  // lower end of range
final int                               upper;                                  // upper end of range

public int compareTo(Object obj) {
    if(obj==null) { return -1; }

    Range                           oth=(Range)obj;

    if(lower<oth.lower) { return -1; }
    if(lower>oth.lower) { return  1; }
    if(upper<oth.upper) { return -1; }
    if(upper>oth.upper) { return  1; }
    return 0;
    }

範囲挿入:

public Builder addRange(int fir, int las) {
    if(fir!=-1) { fir&=0x001FFFFF; }
    if(las!=-1) { las&=0x001FFFFF; }

    if(codepoints==null || codepoints.length==0) {
        codepoints=new Range[]{new Range(fir,las)};
        }
    else {
        int                         idx=Range.findChar(codepoints,fir);
        int                         ins=(idx<0 ? -(idx+1) : idx);

        if(idx<0) {
            if     (ins>0                 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); }  // new range adjoins the following range (can't overlap or idx would be >=0)
            else if(ins<codepoints.length && las>=(codepoints[ins  ].lower-1)) { idx=ins;     }  // new range overlaps or adjoins the following range
            }

        if(idx<0) {
            codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
            }
        else {
            boolean                 rmv=false;

            for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
                if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
                codepoints[xa]=null;
                rmv=true;
                }
            if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
                codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
                }
            if(rmv) { codepoints=Range.removeNulls(codepoints); }
            }
        }
    return this;
    }

二分探索:

static int findChar(Range[] arr, int val) {
    if(arr.length==1) {
        if     (val< arr[0].lower) { return -1; }                             // value too low
        else if(val<=arr[0].upper) { return  0; }                             // value found
        else                       { return -2; }                             // value too high
        }
    else {
        int                             lowidx=0;                               // low index
        int                             hghidx=(arr.length-1);                  // high index
        int                             mididx;                                 // middle index
        Range                           midval;                                 // middle value

        while(lowidx<=hghidx) {
            mididx=((lowidx+hghidx)>>>1);
            midval=arr[mididx];
            if     (val< midval.lower) { hghidx=(mididx-1); }                   // value too low
            else if(val<=midval.upper) { return mididx;     }                   // value found
            else                       { lowidx=(mididx+1); }                   // value too high
            }
        return -(lowidx+1);                                                     // value not found.
        }
    }