Как выбрать диапазоны значений по вхождению значения в диапазон?

Question

[Le0Wolf]

Есть массив объектов, которые содержат начало диапазона, конец диапазона и некоторые другие данные. Сам массив и объекты в нем неизменяемые. Диапазоны могут пересекаться или даже быть 2 или более идентичных диапазона. Конец диапазона может быть не указан, в этом случае считается, что это диапазон из одного элемента.
Нужна структура данных или алгоритм, позволяющие найти все диапазоны, в которые входит переданное значение.

Comments

[Алексей Уколов]

Чем не устраивает банальный цикл с проверкой внутри?

[Le0Wolf]

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

[#]

Le0Wolf,

массив и объекты в нем неизменяемые

а

массив значений для проверки на вхождение

изменяемый?

[Wataru]

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

[Akina]

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

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

Первый вариант выгоден, если прогнозируемое количество пересечений невелико. Иначе выгоднее второй вариант.

[#]

Le0Wolf, Akina, угу, предлагая конструкты языка, собственно это и имел в виду. поиск будет не хуже двоичного, а при наличии оперативки и ядер, можно еще и plinq впарить )))

[Akina]

PS. Я бы скормил всё это в базу данных, построил по ним spatial index...

[#]

Akina, .. если я заставлю себя освоить brightstardb, попробовал бы там прогнать подобное ;))

[Akina]

#, не советую... по крайней мере на задачах подобного типа. Я там не нашёл как-то поддержки ни для spatial datatype, ни вообще для R-tree index. То ли документация у них никакая, то ли все силы ушли в нативность.

[#]

Akina, хм.. возможно вы сэкономили мне время )) спасибо

Answer 1

[Wataru]

Дерево интервалов. Оно же interval tree.

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

Answer 2

[Alexandroppolus]

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

Comments

[Wataru]

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

Одна проблема тут, что эти предподсчитанные ответы могут знимать O(N^2) памяти. Правда, эта проблема лечится, если использовать персистентный set. тогда потребление памяти сократиться до O(n log n) (все-равно хуже дерева интервалов с их O(n), но уже хорошо).

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

Или вы предлагаете просто распилить весь интервал на M фиксированных кусоков? Этот метод - хорошая эврестическая оптимизация, но в худшем случае не даст никакого припроста производительности вообще.

[Alexandroppolus]

Wataru,

Или вы предлагаете просто распилить весь интервал на M фиксированных кусоков?

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

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

[Alexandroppolus]

Wataru, но, пожалуй, проголосую за Дерево интервалов. Раз уж оно используется для данной задачи, то не стоит велосипедить...

Answer 3

[#]

попробуйте словарь вместо массива (или сходные типы)
думаю других вариантов нет. от слова совсем убедили коллеги ))

ps есть еще разнообразные БД. но целесообразность зависит от объема данных в соотношении с доступной оперативкой..

pps если в достатке оперативка и ядра, то запрос plinq поможет... но все же рекомендую бенчмарки ))

https://learn.microsoft.com/ru-ru/dotnet/api/syste... в довесок ;)

Comments

[Wataru]

Есть варианты, есть)

[#]

Wataru, тогда подпишусь ))
жгите маэстро! ))

Answer 4

[Руслан .]

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

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