与えられた数の連続した範囲のセットから範囲を検索する方法
-
20-12-2019 - |
質問
簡単に言えば、これは私がやろうとしていることです:
私はのコレクションを持っています Range
連続している(重複していない、それらの間にギャップがない)オブジェクト。 start
と end
int、および別のオブジェクトへの参照 obj
.これらの範囲は固定サイズではありません(最初のものは1-49、2番目のものは50-221などです)。).このコレクションはかなり大きくなる可能性があります。
コレクション全体を反復処理して各範囲に数値が含まれているかどうかを確認することなく、指定された数値を含む範囲(またはより具体的には、これらのルックアップは頻繁に実行されるため、速度/パフォーマンスが重要です。
誰かがここで私を助けるかもしれないアルゴリズム/方程式を知っていますか?私はJavaで書いています。必要に応じて詳細を提供できますが、シンプルに保つようにしていると思いました。
ありがとう!.
解決
あなたが使用したいように聞こえる場合 TreeMap
, ここで、キーは範囲の最下部であり、値は範囲の最下部です。 Range
オブジェクト。
次に、正しい範囲を識別するには、次のようにします。 floorEntry()
非常に迅速に最も近い(より少ないか等しい)を取得する方法 Range
, 、次のようにキーを含める必要があります:
TreeMap<Integer, Range> map = new TreeMap<>();
map.put(1, new Range(1, 10));
map.put(11, new Range(11, 30));
map.put(31, new Range(31, 100));
// int key = 0; // null
// int key = 1; // Range [start=1, end=10]
// int key = 11; // Range [start=11, end=30]
// int key = 21; // Range [start=11, end=30]
// int key = 31; // Range [start=31, end=100]
// int key = 41; // Range [start=31, end=100]
int key = 101; // Range [start=31, end=100]
// etc.
Range r = null;
Map.Entry<Integer, Range> m = map.floorEntry(key);
if (m != null) {
r = m.getValue();
}
System.out.println(r);
ツリーは常に下の範囲境界の自然順序でソートされるため、すべての検索は最悪の場合O(log(n))になります。
キーが完全に範囲外にある場合(たとえば、キーがマップの終わりを超えている場合、最後のキーを返します)の健全性チェックを追加する必要があります Range
マップで)、しかしこれはあなたにどのように進めるかのアイデアを与えるはずです。
他のヒント
検索を最も重要であると仮定して、o(n)メモリと約O(n ^ 2)前処理時間を予備することができます、アルゴリズムは次のとおりです。
- クラス
ObjectsInRange
を紹介します。範囲の開始(int startOfRange
)と一連のオブジェクト(Set<Object> objects
) -
ArrayList<ObjectsInRange> oir
を含むObjectsInRange
を紹介します。 - 各
startOfRange
の場合は、Range r
とObjectsInRange
などのa
があることを確認してください。次に、b
の間のすべてのa.startOfRange = r.start
の場合、およびb.startOfRange = b.end
まで、ObjectsInRange x
セット に
a
を追加します。
ルックアップ、次のように:
- integer
b
の場合は、r.obj
とx.objects
のような - 注:
i
は、o(log n)時間でBisectionで見つけることができます! - あなたのオブジェクトは
oir[i].startOfRange <= x
です。
x
を見つけます。
コレクションが順番にある場合は、2進検索を実装して、o内の正しい範囲を見つけることができます(log(n))。それは非常に大きなコレクションのためのハッシュと同じくらい効率的ではありませんが、あなたが1000以下の範囲を持っているならば、それはより速くなるかもしれません(それはより単純だから)。