与えられた範囲のペア値を見つける
ニコJ。
配列またはNペア(v1, v2)がありv1 <= v2ます。これらは、で開始v1および終了する時間内のイベントを表すことになっていますv2。それらは等しくなる可能性があり、その場合、イベントは瞬時に発生します。配列は開始時刻でソートされv1ます。
与えられた範囲について(L, R)、私は任意のペアを見つけたいと思いますL <= v1 <= R or L <= v2 <= R。ここでの考え方は、指定された範囲でイベントを開始、発生、または終了させることです。
私の主な問題は効率です。配列には、数十万のイベントが含まれる可能性があります。したがって、すべてのペアを通過する線形検索だけはオプションではありません。
kd-treeについて少し読みましたが、問題は、範囲の境界が除外され、が返されるだけであるということL <= v1 <= R AND L <= v2 <= Rです。つまり、範囲内で実際に発生するイベント（開始と終了）のみが返されますが、開始または終了（または明らかに両方）が必要です。
2つのルックアップテーブルを保持することも考えました（時間にdoubleを使用します）
std::map<double, Event*> startPoints;
std::map<double, Event*> endPoints;
std::find両方でアルゴリズムを使用して、結果をマージします。
アドバイスを探すだけで、それが良い解決策であるかどうか、またはもっと賢い方法があるかどうか。
編集：
それについて考え直すと、もっと複雑になります。これが期待される結果の例です
- L <R：範囲が十分に大きい
|---Ev1---| |---Ev3---| |---Ev5---|
|---Ev2---| |---Ev4---|
| |
L R
ここでは、Ev2（範囲内で終了）、Ev3（範囲内で発生）、Ev4（怒りで開始）を取得したいと思います。
- L <R：範囲が小さすぎて完全なイベントにはなりません
|---Ev1---| |---Ev3---| |---Ev5---|
|---Ev2---| |---Ev4---|
| |
L R
ここでは、現在範囲内で実行されているEv3と、範囲内で開始されているEv4を取得したいと思います。
- L == R：ある時点で何が起こっているのか知りたい場合
|---Ev1---| |---Ev3---| |---Ev5---|
|---Ev2---| |---Ev4---|
|
LR
現在実行されているのはEv2だけなので、ここではEv2のみが必要です。
路上で
指定された範囲で開始、発生、または終了する3つのケースを処理する必要があるため、3つの部分に分割できます。
- 開始：に
v1あります[L,R]。 - エンディング：に
v2あります[L,R]。
3番目のケースはとして定式化できますv1 <= R and L <= v2が、最初の2つのケースはこのケースを部分的にカバーしているため、衝突を回避するために異なる定式化を使用します。
- ハプニング：
v1 < L and R < v2
イベントの配列をで並べ替えることができれば、対数と報告されたイベントの数の時間で最初のケースを処理するのは簡単v1です。同じトリックが2番目のケースでも機能します。
3番目のケースはトリッキーです。描きましょう：
ピンクの領域はすべての間隔を表しますL <= R。赤い点は間隔であり、緑がかった領域は、キャプチャしたいすべての可能なイベントを表しています。このようなキャプチャを行うには、k2-treeを使用できます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
編集
関連記事
Related 関連記事
- 1
与えられた数の範囲を見つける方法は？
- 2
与えられた値の範囲で最大の奇数フィボナッチ数を見つける
- 3
与えられた範囲の交差点を見つけますか？
- 4
値の範囲から指定された値を見つける方法は？
- 5
与えられた範囲の回文数を見つけるJavaプログラム
- 6
与えられた範囲内の倍数を見つけるアルゴリズムの高速化
- 7
与えられた範囲内のn個の数の倍数の数を見つける
- 8
与えられた範囲の間にあるインデックスを見つける
- 9
範囲の最大値を見つける
- 10
範囲内の値を見つける
- 11
合計が指定された値の範囲内にある整数の配列内のすべての順序付けられた要素のペアを見つける方法
- 12
指定された範囲と範囲値から残りのKMを見つけます：最小= 0、最大= 999999
- 13
VBA-数式の範囲から値を見つける
- 14
SPARQLの文字列値から日付範囲を見つける
- 15
与えられた範囲でxより大きい要素の数を見つけます
- 16
arraylistの範囲間の最大値または最小値を見つける方法は？
- 17
整数の2つのリストが与えられた場合、重複しない範囲を見つける方法は？
- 18
与えられた数として合計を作るリストで数のペアを見つける方法
- 19
特定の値がどの範囲に含まれるかを見つけるためのC＃コード/式-
- 20
指定された範囲内で差がある直列の2つの数値のインデックスを見つけるアルゴリズム
- 21
特定の範囲から欠落している値を見つける
- 22
rの均一な事前分布から値の範囲を見つける方法は？
- 23
特定の範囲の配列からピーク値を見つける
- 24
特定の条件が満たされているときに範囲内の最大値を見つける方法
- 25
与えられた範囲内の整数の数を見つける方法は、ビットを設定しています
- 26
与えられた時間範囲の間で可能なすべての時間の組み合わせを見つける
- 27
範囲内の最高値と後続の値を見つける
- 28
ゼロに最も近いセル範囲の値を見つけるための数式。これらのセルには文字が含まれます。
- 29
カウントの範囲から最大値を見つける方法
コメントを追加