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

Есть массив объектов, которые содержат начало диапазона, конец диапазона и некоторые другие данные. Сам массив и объекты в нем неизменяемые. Диапазоны могут пересекаться или даже быть 2 или более идентичных диапазона. Конец диапазона может быть не указан, в этом случае считается, что это диапазон из одного элемента.
Нужна структура данных или алгоритм, позволяющие найти все диапазоны, в которые входит переданное значение.
  • Вопрос задан
  • 1398 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Дерево интервалов. Оно же interval tree.

Оно как раз позволяет быстро искать все отрезки, пересекающие данную точку, но изменять его очень тяжело. Хорошо, что вам это и не надо.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 3
Alexandroppolus
@Alexandroppolus
кодир
Самый тупой вариант - разрезать весь отрезок на много маленьких отрезков, и в каждом маленьком отрезке держать список объектов, которые его задевают. Тогда сначала по имеющемуся значению бинарным поиском находишь нужный отрезок, и проверяешь все объекты из его списка.
Если у тебя диапазоны объектов очень маленькие по сравнении со всем интервалом, то это даёт оптимизцию - каждый отрезок содержит в среднем небольшой список.
Ответ написан
mindtester
@mindtester Куратор тега C#
http://iczin.su/hexagram_48
попробуйте словарь вместо массива (или сходные типы)
думаю других вариантов нет. от слова совсем убедили коллеги ))

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

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

https://learn.microsoft.com/ru-ru/dotnet/api/syste... в довесок ;)
Ответ написан
LaRN
@LaRN
Senior Developer
А если заиметь список в котором ссылки на диапазоны упорядочены по дате начала и чем-то похожим на бинарный поиск искать нужный диапазон, т.е. дата начала диапазона меньше либо равна дате поиска, а дата окончания больше (тут не ясно брать дату включительно или нет) . Список вроде проще построить и использовать чем дерево.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы