Поиск диапазона в Java

Question

Предположим, у меня есть несортированный массив перекрывающихся ranges.Каждый range - это просто пара целых чисел begin и end.Теперь я хочу выяснить, принадлежит ли данный key хотя бы одному из ranges.Вероятно, я должен знать ranges, к которому он принадлежит.

Можно предположить, что массив ranges занимает ~ 1M и умещается в памяти.Я ищу простой алгоритм, который использует только стандартные коллекции JDK без каких-либо сторонних библиотек и специальных структур данных, но работает достаточно быстро.

Что бы вы предложили?

Answer 1

Сортируйте диапазоны численно по пользовательскому Comparator, затем для каждого ключа k создайте диапазон из одного элемента [ k , k ] и выполните бинарный поиск для этого диапазона с другим Comparator.

Comparator для поиска compare(x,y) должно вернуть

• <0, если x.max < y.min
• >0 если x.min > y.max
• 0 в противном случае (два аргумента диапазона перекрываются).

Как отметил @Per, вам нужен другой, более строгий Comparator для сортировки, но первые два предложения все еще остаются в силе.

Это должно работать, даже если диапазоны перекрываются, хотя вы можете объединить перекрывающиеся диапазоны после сортировки, чтобы ускорить поиск. Объединение может быть выполнено за O ( N ) времени.

Это фактически статическое дерево интервалов , т. Е. Одно без вставки или удаления O (lg N ), так же, как отсортированный массив можно считать статическим двоичным файлом. дерево поиска.

Answer 2

Если вам не нужно знать , какой интервал содержит вашу точку (РЕДАКТИРОВАТЬ: я думаю, что вы, вероятно, знаете, но я оставлю этот ответ для других с этим вопросом, которые не имеют), тогда

1. Предварительная обработка интервалов путем вычисления двух массивов B и E. B - это значения начала в отсортированном порядке.E - значения конца в отсортированном порядке.

2. Чтобы запросить точку x, используйте бинарный поиск, чтобы найти наименьший индекс i такой, что B [i]> x и наименьший индекс jтакой, что E [j] ≥ x.Число интервалов [начало, конец], содержащих x, равно i - j.

---

class Interval {
    double begin, end;
}

class BeginComparator implements java.util.Comparator<Interval> {
    public int compare(Interval o1, Interval o2) {
        return Double.compare(o1.begin, o2.begin);
    }
};

public class IntervalTree {
    IntervalTree(Interval[] intervals_) {
        intervals = intervals_.clone();
        java.util.Arrays.sort(intervals, new BeginComparator());
        maxEnd = new double[intervals.length];
        initializeMaxEnd(0, intervals.length);
    }

    double initializeMaxEnd(int a, int b) {
        if (a >= b) {
            return Double.NEGATIVE_INFINITY;
        }
        int m = (a + b) >>> 1;
        maxEnd[m] = initializeMaxEnd(a, m);
        return Math.max(Math.max(maxEnd[m], intervals[m].end), initializeMaxEnd(m + 1, b));
    }

    void findContainingIntervals(double x, int a, int b, java.util.Collection<Interval> result) {
        if (a >= b) {
            return;
        }
        int m = (a + b) >>> 1;
        Interval i = intervals[m];
        if (x < i.begin) {
            findContainingIntervals(x, a, m, result);
        } else {
            if (x <= i.end) {
                result.add(i);
            }
            if (maxEnd[m] >= x) {
                findContainingIntervals(x, a, m, result);
            }
            findContainingIntervals(x, m + 1, b, result);
        }
    }

    java.util.Collection<Interval> findContainingIntervals(double x) {
        java.util.Collection<Interval> result  = new java.util.ArrayList<Interval>();
        findContainingIntervals(x, 0, intervals.length, result);
        return result;
    }

    Interval[] intervals;
    double[] maxEnd;

    public static void main(String[] args) {
        java.util.Random r = new java.util.Random();
        Interval[] intervals = new Interval[10000];
        for (int j = 0; j < intervals.length; j++) {
            Interval i = new Interval();
            do {
                i.begin = r.nextDouble();
                i.end = r.nextDouble();
            } while (i.begin >= i.end);
            intervals[j] = i;
        }
        IntervalTree it = new IntervalTree(intervals);
        double x = r.nextDouble();
        java.util.Collection<Interval> result = it.findContainingIntervals(x);
        int count = 0;
        for (Interval i : intervals) {
            if (i.begin <= x && x <= i.end) {
                count++;
            }
        }
        System.out.println(result.size());
        System.out.println(count);
    }
}

Answer 3

Я считаю, что это то, что вы ищете: http://en.wikipedia.org/wiki/Interval_tree

Но сначала проверьте это более простое решение, чтобы убедиться, что оно соответствует вашим потребностям: Использование карты Java для поиска по диапазону

Answer 4

Учитывая только вашу спецификацию, я был бы склонен упорядочить диапазоны по размеру, в первую очередь с самыми широкими диапазонами (используйте специальный компаратор для облегчения этого).Затем просто переберите их и верните true, как только вы найдете диапазон, содержащий ключ.Поскольку мы ничего не знаем о данных, конечно, самые широкие диапазоны, скорее всего, содержат данный ключ;сначала их поиск может быть (небольшой) оптимизацией.

Вы можете предварительно обработать список другими способами.Например, вы можете исключить любые диапазоны, которые полностью заключены в другие диапазоны.Вы можете сделать заказ на begin и досрочно выйти, как только встретите значение begin больше, чем ваш ключ.

Answer 5

простое решение со сложностью O (n):

for(Range range: ranges){
  if (key >= range.start && key <= range.end)
    return range;
} 

Более умный алгоритм может быть применен, если мы знаем больше информации о диапазонах.Они отсортированы?Они перекрываются?и так далее