Алгоритм пересечения диапазона лучше, чем O(n)?
https://stackoverflow.com/questions/303591
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Пересечение диапазона - простая, но нетривиальная задача.
На него уже дважды был дан ответ:
Первое решение - O (n), а второе решение - для базы данных (которая, конечно, меньше O (n)).
У меня такая же проблема, но для большого числа n, и я не нахожусь в базе данных.
Эта проблема, по-видимому, очень похожа на Сохраняйте 2D точки для быстрого поиска тех, что находятся внутри прямоугольника но я не понимаю, как это соотносится.
Итак, в какой структуре данных вы бы сохранили набор диапазонов, чтобы поиск по диапазону стоил меньше, чем O (n)?(Дополнительная оценка за использование библиотек, доступных для Java)
Редактировать:
Я хочу получить подмножество всех пересекающихся диапазонов, что означает, что диапазон поиска может пересекать несколько диапазонов.
Метод, который должен быть меньше O (n) в Java, является:
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
Где Range - это просто класс, содержащий пару int start и end .
Это не невыполнимый вопрос, у меня уже есть решение, я просто хотел посмотреть, есть ли более стандартный / простой способ сделать это
Решение
Стандартный подход заключается в использовании дерево интервалов.
В информатике дерево интервалов - это древовидная структура данных для хранения интервалов.В частности, это позволяет эффективно находить все интервалы, которые перекрываются с любым заданным интервалом или точкой.Он часто используется для оконных запросов, например, для поиска всех дорог на компьютерной карте внутри прямоугольного окна просмотра или для поиска всех видимых элементов внутри трехмерной сцены.Аналогичной структурой данных является дерево сегментов.
Тривиальное решение состоит в том, чтобы посетить каждый интервал и проверить, пересекает ли он заданную точку или интервал, что требует 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 интервалов, содержащих заданную точку запроса.
Другие советы
Редактировать: Похоже, что это решение более или менее дерево интервалов.Более полную реализацию Интервального дерева можно найти здесь.
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
};
Подготовка O (n log n):
- Создайте список диапазонов
- Выберите точки разворота (возможно, используя отсортированный список конечных дат).) ??
- Постройте свое дерево.
Поиск:
- Используйте двоичный поиск, чтобы найти первый стержень, который является >= TestRange.End
Перемещайтесь по дереву до тех пор, пока не найдете pivot > TestRange.Начните
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
Неперекрывающиеся Диапазоны:
Подготовка O (n log n):
- Создайте массив / вектор диапазонов.
- Отсортируйте вектор по концу диапазона (разорвите связи, отсортировав по началу диапазона)
Поиск:
- Используйте двоичный поиск, чтобы найти первый диапазон с конечным значением >= TestRange.Начать
Итератор, начинающийся с двоичного поиска, пока вы не найдете Start > TestRange.End:
2а.Если диапазон, если текущий диапазон находится в пределах диапазона тестирования, добавьте его к своему результату.
Это зависит от вашей конкретной проблемы, в связанном вопросе диапазоны, в которых различны, нет общей части, а искомый диапазон может охватывать несколько диапазонов.Если ваша проблема такая же, то это действительно просто:Возьмите массив диапазонов, отсортируйте их по наименьшим значениям (поскольку они не перекрываются, это также будет тот же порядок, что и сортировка по их верхним значениям).
Теперь просто выполните поиск по бинсу для вашего целевого нижнего значения (или меньшего, если не точного) и одного для целевого верхнего значения (или большего, если не точного).Результирующие индексы - это диапазоны, которые являются coverd.Вы должны проверить, включены или исключены диапазоны в самих индексах, но это всего лишь 2 проверки.Общая сложность O(log n).
Перекрывающиеся Диапазоны:
Подготовка O (n log n):
- Создайте массив / вектор диапазонов.
- Отсортируйте вектор по концу диапазона (разорвите связи, отсортировав по началу диапазона)
Создайте второй вектор целых чисел.Это представляет собой точку, в которой вы можете прекратить поиск.
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.Начать
Итератор, начинающийся с двоичного поиска до остановки[i] > TestRange.End:
2а.Если диапазон, если текущий диапазон находится в пределах диапазона тестирования, добавьте его к своему результату.
Если диапазоны перекрываются, и кто-то хочет получить ВСЕ диапазоны, которые перекрывают (или содержат) заданный целевой диапазон, большинство приведенных выше решений, похоже, не работают.
Как указывали некоторые, если (в наихудшем случае) ВСЕ диапазоны случайно пересекают целевой диапазон (например, если целевой диапазон равен {0..MAXINT} или аналогичен), то, конечно, для возврата n диапазонов требуется O (n).
Но разве это не интересный и типичный / средний случай, когда лишь очень небольшой % из n общих диапазонов пересекает целевой диапазон?Позвоните по номеру, который делай пересеките "m" - в этом случае, возможно, вы сможете сделать это так же хорошо, как O (m).И если n = 10 ^ 9 и m = 10, это существенная разница.
Рассмотрим простой случай текстового документа, в котором различные области помечены в соответствии с их "типом" - возможно, вы хотите найти все отмеченные блоки, которые содержат данный непрерывный диапазон текста (например, абзац) или пересекают его.В HTML, XML или аналогичных они могут быть только предками текстовых узлов, содержащих по крайней мере некоторые символы целевого диапазона.В типичных представлениях с родительскими указателями в каждом узле это O (m) - намного лучше, чем O (n), особенно потому, что m - это (для коротких или синхронных целевых диапазонов) просто глубина вложенности дерева, которая, как правило, даже ниже, чем ln (n), потому что большие XML-документы на практике становятся объемнее, а не глубже.
Интересный случай сложнее:что, если ваши "элементы" не образуют дерево, как в XML, но могут перекрываться, как в MECS, CLIX, LMNL и некоторых других системах?Вы по-прежнему хотите найти все области / "элементы", которые перекрывают вашу цель, но организовать их не так-то просто.
С другой стороны, у вас должно получиться очень хорошо, потому что выделенные диапазоны во многих приложениях чаще всего невелики - в книге гораздо больше слов, предложений и абзацев, чем глав.Таким образом, даже при том, что может существовать огромное количество диапазонов, которые начинаются перед целью, и огромное количество диапазонов, которые заканчиваются после нее, пересечение будет в среднем очень небольшим.
Я думаю, это то, к чему клонил первоначальный спрашивающий, и, боюсь, я не увидел ответа, который бы решал эту проблему.Если это не то, о чем был первоначальный вопрос, тогда я хотел бы задать его как новый вопрос.
Похоже, вам нужен класс, который реализует интерфейс SortedSet.TreeSet - это реализация, которая поставляется вместе с основным API.
Имейте один набор, содержащий диапазоны, отсортированные по наименьшему значению, и один, отсортированный по наибольшему значению.
Затем вы можете реализовать эквивалент алгоритма базы данных, используя наборы данных в памяти.
Что касается того, действительно ли это быстрее, чем O (n), я не могу сказать.
Точно так же, как четырехугольное дерево работает для набора 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)
Более подробная информация:Двоичное дерево было бы структурировано как одномерная версия четырехъядерного дерева.Каждый узел будет содержать три целых числа (извините, я сказал два выше, но теперь я понимаю, что вам нужно три), наименьшее, представляющее наименьшее значение наименьшего диапазона, который находится ниже этого узла, наибольшее, представляющее наибольшее значение наибольшего диапазона, который находится ниже этого узла, и стержень.Левый дочерний элемент будет простираться от самого низкого уровня этого узла до его оси.Правильный дочерний элемент будет простираться от центра этого узла до самого высокого уровня этого узла.Если бы существовал только один диапазон, который идет от "самого низкого" до "самого высокого", у вас не было бы стержня, и это был бы лист.В идеале вы бы выбрали точки опоры для каждого узла, чтобы сохранить дерево сбалансированным.
Когда у меня возникла эта проблема, я использовал отсортированный массив диапазонов и двоичный поиск для поиска пересечений.Это (я полагаю) Высокая производительность (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.
}
}
