Как найти диапазон из набора смежных диапазонов для данного числа

Question

Проще говоря, это то, что я пытаюсь сделать:

У меня есть коллекция Range объекты, которые являются смежными (не перекрывающимися, без промежутков между ними), каждый из которых содержит start и end int и ссылка на другой объект obj.Эти диапазоны не имеют фиксированного размера (первый может быть от 1 до 49, второй от 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, и до тех пор (но не включая) b, добавлять r.obj к их x.objects набор

Тогда поиск выглядит следующим образом:

• для целого числа x, найди такой i что oir[i].startOfRange <= x и oir[i+1].startOfRange > x
• примечание: i можно найти с помощью деления пополам за время O(log N)!
• ваши объекты oir[i].objects

Answer 3

Если коллекция в порядке, вы можете реализовать двоичный поиск, чтобы найти правильный диапазон за время O(log(n)).Для очень больших коллекций это не так эффективно, как хеширование, но если у вас менее 1000 диапазонов или около того, это может быть быстрее (потому что проще).