O（n）よりも優れた範囲交差アルゴリズム？
https://stackoverflow.com/questions/303591
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
範囲の交差は単純ですが、重要な問題です。
すでに2回回答済みです：
最初の解決策はO（n）であり、2番目の解決策はデータベース用です（もちろんO（n）より小さい）。
同じ問題を抱えていますが、nが大きく、データベース内にいません。
この問題は 2Dポイントを保存して、四角形の中にあるものをすばやく取得するが、どのようにマップされるかわかりません。
では、範囲の検索がO（n）未満になるように、範囲のセットをどのデータ構造に保存しますか？ （Javaで利用可能なライブラリを使用するための追加クレジット）
編集：
すべての交差する範囲のサブセットを取得したい。つまり、検索範囲が複数の範囲と交差する可能性がある。
JavaでO（n）より小さくする必要があるメソッドは次のとおりです。
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
範囲は、intの開始と終了のペアを含む単なるクラスです。
これは不可能な質問ではなく、すでに解決策があります。もっと標準的で簡単な方法があるかどうかを見たかっただけです
解決
標準的なアプローチは、間隔ツリーを使用することです。
コンピューターサイエンスでは、間隔ツリーは間隔を保持するツリーデータ構造です。具体的には、任意の間隔またはポイントと重複するすべての間隔を効率的に見つけることができます。多くの場合、ウィンドウクエリに使用されます。たとえば、長方形のビューポート内のコンピューター化されたマップ上のすべての道路を検索したり、3次元シーン内のすべての表示要素を検索したりします。同様のデータ構造はセグメントツリーです。
簡単な解決策は、各間隔にアクセスし、指定されたポイントまたは間隔と交差するかどうかをテストすることです。O（n）時間を必要とします。nはコレクション内の間隔の数です。クエリはすべての間隔を返す場合があるため、たとえばクエリがコレクション内のすべての間隔と交差する大きな間隔である場合、これは漸近的に最適です。ただし、ランタイムがm（クエリによって生成される間隔の数）で表される出力依存アルゴリズムを検討することで、より良い結果を得ることができます。インターバルツリーのクエリ時間はO（log n + m）で、初期作成時間はO（n log n）ですが、メモリ消費はO（n）に制限されます。作成後、間隔ツリーは動的になり、O（log n）で間隔を効率的に挿入および削除できます。間隔の端点が小さな整数範囲内にある場合（たとえば、範囲[1、...、O（n）]）、前処理時間O（n）およびクエリ時間O（ 1 + m）指定されたクエリポイントを含むm個の間隔をレポートします。
他のヒント
編集： このソリューションは、多かれ少なかれ間隔ツリーのようです。間隔ツリーのより完全な実装は、こちらで見つけることができます。
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
};
Prep O（n log n）：
- 範囲のリストを作成
- ピボットポイントを選択します（終了日の並べ替えられたリストを使用することによります）??
- ツリーを構築します。
検索：
- バイナリ検索を使用して、＆gt; = TestRange.Endである最初のピボットを見つけます
-
ピボットまでツリーをたどる＆gt; 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
重複しない範囲：
Prep O（n log n）：
- 範囲の配列/ベクトルを作成します。
- 範囲の終わりまでベクトルを並べ替えます（範囲の先頭で並べ替えてタイを区切ります）
検索：
- バイナリ検索を使用して、End値が＆gt; = TestRange.Startである最初の範囲を見つけます
-
イテレータは、バイナリ検索から開始して、開始が見つかるまで＆gt; TestRange.End：
2a。現在の範囲がTestRange内にある場合、範囲を結果に追加します。
これは、あなたの正確な問題、リンクされた質問、明確で共通部分のない範囲、および検索範囲が複数の範囲に及ぶ可能性があることに依存します。あなたの問題が同じなら、それは本当に簡単です： 範囲の配列を取得し、それらの最低値で並べ替えます（重複しないため、これは上限値で並べ替えられた順序と同じ順序になります）。
ターゲットの下限値（または正確でない場合は小さい）のbinsearchと、ターゲットの上限値（または正確でない場合は大きい）のbinsearchを作成します。結果のインデックスは、カバーされる範囲です。インデックス自体の範囲がインであるか除外されているかを確認する必要がありますが、それはたった2つのチェックです。全体的な複雑さO（log n）。
重複する範囲：
Prep O（n log n）：
- 範囲の配列/ベクトルを作成します。
- 範囲の終わりまでベクトルを並べ替えます（範囲の先頭で並べ替えてタイを区切ります）
-
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]); }
検索：
- バイナリ検索を使用して、End値が＆gt; = TestRange.Startである最初の範囲を見つけます
-
イテレータは、バイナリ検索からstop [i]まで続く＆gt; TestRange.End：
2a。現在の範囲がTestRange内にある場合、範囲を結果に追加します。
範囲が重複しており、特定の対象範囲と重複する（または含む）範囲をすべてすべて取得したい場合、上記のソリューションのほとんどは機能しないようです。
いくつかの人が指摘したように、（最悪の場合）すべて範囲がターゲット範囲と交差する場合（たとえば、ターゲット範囲が{0..MAXINT}または同様の場合）もちろん、n個の範囲を返すにはO（n）が必要です。
しかし、n個の合計範囲のごくわずかな％のみがターゲット範囲と交差する、興味深い典型的な/平均的なケースではありませんか？ do が交差する番号を呼び出します＆quot; m＆quot; -その場合、O（m）と同様にできるかもしれません。また、n = 10 ^ 9およびm = 10の場合、これはメイクまたはブレークの違いです。
「タイプ」用にマークアップされたさまざまな領域を持つテキストドキュメントの単純なケースを考えます。 -おそらく、特定の連続したテキスト範囲（たとえば、段落）を含む、または交差するマークアップされたユニットをすべて検索する必要があります。 HTML、XML、または同様のものでは、それらはターゲット範囲の少なくともいくつかの文字を含むテキストノードの祖先にしかなれません。各ノードに親ポインターがある典型的な表現では、それはO（m）です-特に、mは（短いターゲット範囲または同期ターゲット範囲の場合）単にツリーの入れ子の深さであり、 ln（n）は、実際には大きなXML文書が深みを増すのではなく、深みを増すためです。
おもしろいケースはもっと難しい：あなたの＆quot; elements＆quot; XMLのようにツリーを形成しませんが、MECS、CLIX、LMNL、および他のいくつかのシステムのようにオーバーラップできますか？あなたはまだすべての地域/「要素」を見つけたいです;これはターゲットと重複しますが、それほど簡単には整理できません。
一方、多くのアプリケーションでマークアップされた範囲は最も頻繁に小さいため、非常にうまくいくはずです。本の中には、章よりもはるかに多くの単語、文、段落があります。そのため、ターゲットの前に開始する範囲が非常に多く、ターゲットの後に終了する範囲が非常に多い場合でも、交差点は平均して非常に小さくなります。
それは元の質問者が得ていたものだと思います。その問題に対処する答えが見つからなかったのではないかと心配しています。元の質問の内容ではない場合は、新しい質問として提示します。
SortedSetインターフェースを実装するクラスが必要なようです。 TreeSetは、コアAPIに同梱されている実装です。
最低値でソートされた範囲と最高値でソートされた範囲を保持するセットを1つ用意します。
その後、メモリ内セットを使用して、データベースアルゴリズムに相当するものを実装できます。
これが実際にO（n）より速いかどうかについては、言えませんでした。
クアッドツリーが2次元の点のセットに対して機能するのと同様に、この場合にも単純なバイナリツリーが機能するはずです。範囲でツリーを構築します。
さらに説明するには： ツリーの各ノードには、範囲の最初と最後の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つだけの場合「最高」にするには、ピボットはなく、これがリーフになります。ツリーのバランスを保つために、各ノードのピボットを選択するのが理想的です。
この問題が発生したとき、範囲のソートされた配列とバイナリ検索を使用して交差を探しました。これは、（重複していると思われる）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.
}
}
