7

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

私は連続しているオブジェクトのコレクションを持っていRangeます (重なり合っておらず、それらの間にギャップはありません)。それぞれに astartとendint が含まれており、別の object への参照が含まれていますobj。これらの範囲は固定サイズではありません (最初の範囲は 1 ～ 49、2 番目の範囲は 50 ～ 221 など)。このコレクションは非常に大きくなる可能性があります。

コレクション全体を反復処理して各範囲に番号が含まれているかどうかを確認することなく、特定の番号を含む範囲 (より具体的には、それが参照するオブジェクト) を検索する方法を見つけたいと考えています。これらのルックアップは頻繁に実行されるため、速度/パフォーマンスが重要です。

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

ありがとう。

4

3 に答える 3

4

キー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を返す場合) の健全性チェックを追加する必要がありますが、これでどのように考えられるかがわかります。続行します。

于 2014-07-28T21:12:23.777 に答える