Алгоритм пересечения диапазона лучше, чем O (n)?

Question

Пересечение по дальности - простая, но нетривиальная задача.

Его уже дважды ответили:

• Найти пересечение диапазона номеров
• Сравнение диапазонов дат

Первое решение - O (n), а второе решение - для базы данных (конечно, меньше, чем O (n)).

У меня та же проблема, но для большого n я не в базе данных.

Эта проблема, похоже, очень похожа на Хранить 2D-точки для быстрого поиска точек внутри прямоугольника , но я не вижу, как он отображается.

Так в какой структуре данных вы бы сохранили набор диапазонов, чтобы поиск по диапазону стоил меньше, чем O (n)? (Дополнительный кредит за использование библиотек, доступных для Java)

EDIT:

Я хочу получить подмножество всех пересекающихся диапазонов, то есть диапазон поиска может пересекать несколько диапазонов.

Метод, который должен быть меньше, чем O (n) в Java:

public class RangeSet {
    ....
    public Set<Range> intersects(Range range);
    ....
}

Где Range - это просто класс, содержащий пару int начала и конца.

Это не невозможный вопрос, у меня уже есть решение, я просто хотел посмотреть, есть ли более стандартный / более простой способ сделать это

Answer 1

Стандартный подход заключается в использовании дерева интервалов .

В информатике дерево интервалов - это древовидная структура данных для хранения интервалов. В частности, он позволяет эффективно находить все интервалы, которые перекрываются с любым заданным интервалом или точкой. Он часто используется для оконных запросов, например, чтобы найти все дороги на компьютеризированной карте внутри прямоугольного видового экрана или найти все видимые элементы в трехмерной сцене. Аналогичная структура данных - дерево сегментов.

Тривиальное решение состоит в том, чтобы посещать каждый интервал и проверять, пересекает ли он данную точку или интервал, что требует времени O (n), где n - количество интервалов в наборе. Поскольку запрос может возвращать все интервалы, например, если запрос представляет собой большой интервал, пересекающий все интервалы в коллекции, это асимптотически оптимально; однако, мы можем добиться большего, рассматривая чувствительные к выходу алгоритмы, где время выполнения выражается через m, число интервалов, созданных запросом. Деревья интервалов имеют время запроса O (log n + m) и начальное время создания O (n log n), при этом потребление памяти ограничивается O (n). После создания деревья интервалов могут быть динамическими, что позволяет эффективно вставлять и удалять интервалы в O (log n). Если конечные точки интервалов находятся в небольшом целочисленном диапазоне (например, в диапазоне [1, ..., O (n)]), существуют более быстрые структуры данных [1] с временем предварительной обработки O (n) и временем запроса O ( 1 + m) для сообщения m интервалов, содержащих данную точку запроса.

Answer 2

Изменить: Похоже, что это решение более или менее Дерево интервалов . Более полную реализацию дерева интервалов можно найти здесь .

class TreeNode
{
public:
    long pivot;
    List<Range> leaves;  //Any ranges that intersect the pivot
    TreeNode left;        //Tree nodes that fall to the left of the pivot
    TreeNode right;       //Tree nodes that fall to the right of the pivot
};

Prep O (n log n):

1. Создать список диапазонов
2. Выберите опорные точки (возможно, используя отсортированный список дат окончания). ??
3. Построй свое дерево.

Поиск:

1. Используйте бинарный поиск, чтобы найти первый стержень, который> = TestRange.End

2. Пройдите по дереву до разворота> TestRange.Start

   2a. Добавьте листья к вашему результату.

---

* +1032 * Пример: * 1 033 *

Диапазоны:

• 0 - 2
• 1 - 2
• 2 - 3
• 1 - 4
• 2 - 4
• 0 - 5
• 4 - 5
• 2 - 6
• 3 - 7

Дерево:

                             4
               --------------+------------------
               3             |                 7
               |            1-4                |
               |            2-4                |
               |            0-5                |
               |            4-5                |
      ---------+------                 --------+--------
      2        |    null              6        |       null
 -----+----   2-3                 ----+----   3-7
null  |  null                   null  |  null    
     0-2                             2-6
     1-2

Answer 3

Не перекрывающиеся диапазоны:

Prep O (n log n):

1. Создать массив / вектор диапазонов.
2. Сортировка вектора по концу диапазона (разрыв связей при сортировке по началу диапазона)

Поиск

1. Используйте двоичный поиск, чтобы найти первый диапазон с конечным значением> = TestRange.Start

2. Итератор, начиная с двоичного поиска, пока не найдете Start> TestRange.End:

   2a. Если диапазон, если текущий диапазон находится в пределах TestRange, добавьте его в свой результат.

Answer 4

Если диапазоны перекрываются, и кто-то хочет извлечь все диапазоны, которые перекрывают (или содержат) заданный целевой диапазон, большинство из приведенных выше решений не работают.

Как указали некоторые, если (наихудший случай) все диапазоны пересекают целевой диапазон (например, если целевой диапазон равен {0..MAXINT} или подобному), то из Конечно, требуется O (n), чтобы вернуть n диапазонов.

Но разве не интересный и типичный / средний случай, когда только очень маленький% от n общих диапазонов пересекают целевой диапазон? Позвоните по номеру, который do пересекает «m» - в этом случае вы, вероятно, сможете сделать так же, как O (m). А если n = 10 ^ 9 и m = 10, это разница «сделай или сломай».

Рассмотрим простой случай текстового документа, в котором различные области размечены для их «типа» - возможно, вы хотите найти все размеченные единицы, которые содержат или пересекают данный непрерывный диапазон текста (например, параграф). В HTML, XML или подобных им могут быть только предки текстовых узлов, содержащих хотя бы несколько символов целевого диапазона. В типичных представлениях с родительскими указателями в каждом узле это O (m) - намного лучше, чем O (n), особенно потому, что m (для коротких или синхронных целевых диапазонов) просто глубина вложения дерева, которая имеет тенденцию быть даже ниже, чем ln (n), потому что большие XML-документы на практике становятся глубже, а не глубже.

Интересный случай сложнее: что если ваши «элементы» не образуют дерево, как в XML, но могут перекрываться, как в MECS, CLIX, LMNL и некоторых других системах? Вы все еще хотите найти все регионы / "элементы", которые перекрывают вашу цель, но их не так легко организовать.

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

Я думаю, что это то, к чему стремился первоначальный спрашивающий, и я боюсь, что не увидел ответа, который решает эту проблему. Если это не то, о чем был первоначальный вопрос, то я бы хотел сформулировать его как новый вопрос.

Answer 5

Перекрывающиеся диапазоны:

Prep O (n log n):

1. Создать массив / вектор диапазонов.
2. Сортировка вектора по концу диапазона (разрыв связей при сортировке по началу диапазона)

3. Создайте второй вектор целых. Это точка, в которой вы можете прекратить поиск.

   int stop[size];
   stop[size-1] = Ranges[size - 1].start;
   for (int i = size - 2; i >= 0; i--)
   {
       stop[i] = min(Ranges[i].start, stop[i+1]);
   }
   

Поиск:

1. Используйте двоичный поиск, чтобы найти первый диапазон с конечным значением> = TestRange.Start

2. Итератор запускается при бинарном поиске до остановки [i]> TestRange.End:

   2a. Если диапазон, если текущий диапазон находится в пределах TestRange, добавьте его к своему результату.

Answer 6

Это зависит от вашей конкретной проблемы, в связанном вопросе, диапазоны, где различны, нет общей части, и диапазон поиска может охватывать несколько диапазонов. Если ваша проблема такая же, это действительно легко: Возьмите массив диапазонов, отсортируйте их по их наименьшим значениям (поскольку они не перекрываются, это также будет порядок сортировки по их верхним значениям).

Теперь просто создайте binsearch для целевого нижнего значения (или меньшего, если не точного) и один для целевого верхнего значения (или большего, если не точного). Результирующие индексы - это диапазоны, которые охватываются. Вы должны проверить, включены ли диапазоны в сами индексы или нет, но это всего лишь две проверки. Общая сложность O (log n).

Answer 7

Когда у меня возникла эта проблема, я использовал отсортированный массив диапазонов и двоичный поиск для поиска пересечений. Это (я полагаю) производительность O (log n), с небольшими накладными расходами для работы с перекрывающимися диапазонами.

Ответ на ваш вопрос, я думаю, выводится из приведенного ниже кода, но без вставки. Я представляю весь код, чтобы избежать путаницы из-за различий контекста - мне нужно было вставить диапазон кодов Unicode в список диапазонов кодов.

- РЕДАКТИРОВАТЬ -

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

- КОНЕЦ РЕДАКТИРОВАНИЯ -

Класс Range содержит:

final int                               lower;                                  // lower end of range
final int                               upper;                                  // upper end of range

public int compareTo(Object obj) {
    if(obj==null) { return -1; }

    Range                           oth=(Range)obj;

    if(lower<oth.lower) { return -1; }
    if(lower>oth.lower) { return  1; }
    if(upper<oth.upper) { return -1; }
    if(upper>oth.upper) { return  1; }
    return 0;
    }

Установка диапазона:

public Builder addRange(int fir, int las) {
    if(fir!=-1) { fir&=0x001FFFFF; }
    if(las!=-1) { las&=0x001FFFFF; }

    if(codepoints==null || codepoints.length==0) {
        codepoints=new Range[]{new Range(fir,las)};
        }
    else {
        int                         idx=Range.findChar(codepoints,fir);
        int                         ins=(idx<0 ? -(idx+1) : idx);

        if(idx<0) {
            if     (ins>0                 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); }  // new range adjoins the following range (can't overlap or idx would be >=0)
            else if(ins<codepoints.length && las>=(codepoints[ins  ].lower-1)) { idx=ins;     }  // new range overlaps or adjoins the following range
            }

        if(idx<0) {
            codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
            }
        else {
            boolean                 rmv=false;

            for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
                if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
                codepoints[xa]=null;
                rmv=true;
                }
            if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
                codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
                }
            if(rmv) { codepoints=Range.removeNulls(codepoints); }
            }
        }
    return this;
    }

Двоичный поиск:

static int findChar(Range[] arr, int val) {
    if(arr.length==1) {
        if     (val< arr[0].lower) { return -1; }                             // value too low
        else if(val<=arr[0].upper) { return  0; }                             // value found
        else                       { return -2; }                             // value too high
        }
    else {
        int                             lowidx=0;                               // low index
        int                             hghidx=(arr.length-1);                  // high index
        int                             mididx;                                 // middle index
        Range                           midval;                                 // middle value

        while(lowidx<=hghidx) {
            mididx=((lowidx+hghidx)>>>1);
            midval=arr[mididx];
            if     (val< midval.lower) { hghidx=(mididx-1); }                   // value too low
            else if(val<=midval.upper) { return mididx;     }                   // value found
            else                       { lowidx=(mididx+1); }                   // value too high
            }
        return -(lowidx+1);                                                     // value not found.
        }
    }

Answer 8

Похоже, вам нужен класс, который реализует интерфейс SortedSet. TreeSet - это реализация, которая поставляется с базовым API.

Один набор содержит диапазоны, отсортированные по наименьшему значению, и один набор по наибольшему.

Затем вы можете реализовать эквивалент алгоритма базы данных, используя наборы в памяти.

Что касается того, действительно ли это быстрее, чем O (n), я не могу сказать.

Answer 9

Так же, как квад-дерево работает для набора 2d точек, для этого случая должно работать простое бинарное дерево. Постройте дерево с вашими диапазонами.

Чтобы объяснить дальше: Каждый узел в дереве содержит два целых числа, начало и конец диапазона, и два дочерних элемента, если это не листовой узел. Чтобы найти диапазоны, в которые входит ваш диапазон ввода, а затем начать сверху дерева

  - if the node range intersects the input range:
     - if it's a leaf node, then add the range to your result list
     - if it's not a leaf node, then traverse down to the child nodes and repeat this process.

Должно быть O (logN) * ​​1006 *

Подробнее: Двоичное дерево будет структурировано как 1-я версия четырехугольного дерева. Каждый узел будет иметь три целых числа (извините, я сказал два выше, но теперь я понимаю, что вам нужно три), самое низкое из которых представляет самое низкое значение самого низкого диапазона, который находится ниже этого узла, самое высокое, представляющее самое высокое значение самого высокого диапазона, который находится ниже этого узел и стержень. Левый дочерний элемент будет проходить от самого нижнего узла до его оси. Правый дочерний элемент будет охватывать от оси этого узла до самого высокого узла. Если есть только один диапазон, который идет от «самого низкого» до «самого высокого», у вас не будет разворота, и это будет лист. В идеале вы должны выбрать стержни для каждого узла, чтобы дерево было сбалансированным.