Как выбрать диапазоны значений по вхождению значения в диапазон?
Есть массив объектов, которые содержат начало диапазона, конец диапазона и некоторые другие данные. Сам массив и объекты в нем неизменяемые. Диапазоны могут пересекаться или даже быть 2 или более идентичных диапазона. Конец диапазона может быть не указан, в этом случае считается, что это диапазон из одного элемента.
Нужна структура данных или алгоритм, позволяющие найти все диапазоны, в которые входит переданное значение.
Le0Wolf, #, Да, если у вас искомые точки тоже фиксированные, то не надо даже никаких хитрых структур данных: Просто отсортируйте все точки-концы отрезков и точки-запросы (вместе) и потом пройдитесь по этому массиву слева направо. Если встретили "начало" - добавляйте отрезок в множество открытых. Встретили "конец" - удаляйте. Встретили "запрос" - текущее множество копируйте в ответ для этого запроса.
Есть простое правило: если диапазоны пересекаются, то начало любого из них меньше конца другого.
Сортируем имеющиеся отрезки - по возрастанию начал, при равном по возрастанию концов. Ищем первый отрезок, начало которого больше конца заданного. Он и все справа не рассматриваются, ибо находятся правее и заведомо не пересекаются. Теперь просто сканируем все отрезки левее. Отбираем пересекающиеся. Либо по аналогии по другому списку, сортированному по возрастанию концов, убираем заведомо не пересекающиеся, которые находятся левее. Пересекающиеся - встречаются в обоих списках.
Первый вариант выгоден, если прогнозируемое количество пересечений невелико. Иначе выгоднее второй вариант.
Le0Wolf, Akina, угу, предлагая конструкты языка, собственно это и имел в виду. поиск будет не хуже двоичного, а при наличии оперативки и ядер, можно еще и plinq впарить )))
#, не советую... по крайней мере на задачах подобного типа. Я там не нашёл как-то поддержки ни для spatial datatype, ни вообще для R-tree index. То ли документация у них никакая, то ли все силы ушли в нативность.
Самый тупой вариант - разрезать весь отрезок на много маленьких отрезков, и в каждом маленьком отрезке держать список объектов, которые его задевают. Тогда сначала по имеющемуся значению бинарным поиском находишь нужный отрезок, и проверяешь все объекты из его списка.
Если у тебя диапазоны объектов очень маленькие по сравнении со всем интервалом, то это даёт оптимизцию - каждый отрезок содержит в среднем небольшой список.
Я правильно понимаю, что вы предлагаете разбить диапазон всех возможных значений всем точками-концами отрезков и предподсчитать ответ на каждом из получившихся кусочков?
Одна проблема тут, что эти предподсчитанные ответы могут знимать O(N^2) памяти. Правда, эта проблема лечится, если использовать персистентный set. тогда потребление памяти сократиться до O(n log n) (все-равно хуже дерева интервалов с их O(n), но уже хорошо).
Стоит также добавить комментарий, что лучше всего это реализовывать отсортировав все точки-концы отрезков и пройтись по ним слева-направо.
Или вы предлагаете просто распилить весь интервал на M фиксированных кусоков? Этот метод - хорошая эврестическая оптимизация, но в худшем случае не даст никакого припроста производительности вообще.
Или вы предлагаете просто распилить весь интервал на M фиксированных кусоков?
да, именно так. Я, собственно, и написал, что это будет хорошо работать не всегда. Если у объектов длинные интервалы, то в большинстве кейсов точка будет попадать на много объектов (количество, сравнимое со всем списком), и смысла что-то придумывать вообще нет.
Но если автор озадачился вопросом, то возможно у него предполагаются маленькие выборки на точку.
А если заиметь список в котором ссылки на диапазоны упорядочены по дате начала и чем-то похожим на бинарный поиск искать нужный диапазон, т.е. дата начала диапазона меньше либо равна дате поиска, а дата окончания больше (тут не ясно брать дату включительно или нет) . Список вроде проще построить и использовать чем дерево.
Но правда не ясно как решать коллизии, если например диапазоны одинаковой длинны пересекаются со смещением даты начала, то какой диапазон выбрать не ясно, если точка поиска попадает в область пересечения таких диапазонов.
