与えられた数の連続した範囲のセットから範囲を検索する方法

Question

簡単に言えば、これは私がやろうとしていることです:

私はのコレクションを持っています Range 連続している（重複していない、それらの間にギャップがない）オブジェクト。 start と end int、および別のオブジェクトへの参照 obj.これらの範囲は固定サイズではありません（最初のものは1-49、2番目のものは50-221などです）。).このコレクションはかなり大きくなる可能性があります。

コレクション全体を反復処理して各範囲に数値が含まれているかどうかを確認することなく、指定された数値を含む範囲（またはより具体的には、これらのルックアップは頻繁に実行されるため、速度/パフォーマンスが重要です。

誰かがここで私を助けるかもしれないアルゴリズム/方程式を知っていますか？私はJavaで書いています。必要に応じて詳細を提供できますが、シンプルに保つようにしていると思いました。

ありがとう！.

Answer 1

あなたが使用したいように聞こえる場合 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 マップで）、しかしこれはあなたにどのように進めるかのアイデアを与えるはずです。

Answer 2

検索を最も重要であると仮定して、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
のようなxを見つけます。
• 注：iは、o（log n）時間でBisectionで見つけることができます！
• あなたのオブジェクトはoir[i].startOfRange <= x
です。

Answer 3

コレクションが順番にある場合は、2進検索を実装して、o内の正しい範囲を見つけることができます（log（n））。それは非常に大きなコレクションのためのハッシュと同じくらい効率的ではありませんが、あなたが1000以下の範囲を持っているならば、それはより速くなるかもしれません（それはより単純だから）。