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

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

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

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

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

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

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

EDIT:

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

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

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

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

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

Ответ 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 интервалов, содержащих заданную точку запроса.

Ответ 2

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

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):

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

Поиск:

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

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

Пример:

Диапазоны:

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

Ответ 3

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

Prep O (n log n):

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

Поиск:

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

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

Ответ 4

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

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

Ответ 5

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

Prep O (n log n):

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

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

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]);
}

Поиск:

Используйте двоичный поиск, чтобы найти первый диапазон с конечным значением >= TestRange.Start
Итератор, начинающийся с двоичного поиска до остановки [i] > TestRange.End:

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

Ответ 6

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

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

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

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

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

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

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

Ответ 7

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

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

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

Это должно быть O (logN)

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

Ответ 8

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

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

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

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

Ответ 9

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

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

- EDIT -

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

- END EDIT -

Класс 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.
        }
    }