Работа с диапазонами

[alibek]

Привет, камрады
Вот занялся тут одной задачкой и что-то мозги буксуют.
Вводные: есть ряд диапазонов вида I1-I2, количество диапазонов порядка сотен и тысяч, диапазоны характеризуются большими числами (14 разрядов).
Диапазоны бывают двух типов, Д1 и Д2. Диапазоны Д1 не должны пересекаться между собой. Диапазоны Д2 также не должны пересекаться между собой и вдобавок они должны входить в диапазоны Д1.
Нужно организовать работу с этими диапазонами, т.е. определять, являются ли диапазоны пересекающимися, смежными, несмежными и находить пустоты между несмежными диапазонами (т.к. эти диапазоны задает человек-оператор и он может ошибиться, надо его проверять).
Мне упрямо лезет в голову только решение в лоб: для граничных значений каждого диапазона проверять на предмет вхождения/соседства/не соседства со всеми остальными диапазонами. Просто, понятно, но для тысячи диапазонов это означает миллион проходов, что нехорошо.

[skiperski]

для граничных значений каждого диапазона проверять на предмет вхождения/соседства/не соседства со всеми остальными диапазонами.

Может ты просто не верно выразился, но проверять-то надо не все диапазоны, а только соседние. Но для этого они должны быть отсортированы.

но для тысячи диапазонов это означает миллион проходов, что нехорошо.

а это уже только тысяча - 1 проходов

[alibek]

Диапазоны отсортированы (проиндексированы в базе данных). Тогда проверка введенного пользователем диапазона будет выглядеть как

Код: Выделить всё

select id, i1, i2
from ranges2
where ((r1 between i1 and i2) or (r2 between i1 and i2))


Запрос возвратит диапазоны, с которым пересекается r1-r2, если возвратится пустой запрос, то диапазон корректен. Но это два прохода по всем диапазонам (хотя возможно оптимизатор БД улучшит ситуацию).
Но надо убедится, что этот диапазон также входит в Д1. Проблема в том, что в Д1 может быть ряд смежных диапазонов, которые необходимо объединить перед проверкой (т.к. если i11-i12 и i21-i22 смежные диапазоны и r1-r2 входит в i11-i22, то это корректный диапазон).
Как осуществить такое слияние через SQL я никак не соображу, а значит надо пробегаться кодом по Д1 и объединять смежные диапазоны во вспомогательную таблицу.

Код: Выделить всё

select r1.id, r1.i1, r1.i2, decode(r1.i1,r2.i2+1,1,0) rl, decode(r1.i2,r2.i1-1,1,0) rr
from ranges1 r1, ranges1 r2
where r1.id <> r2.id
  and (r1.i1 = r2.i2+1 or r1.i2 = r2.i1-1)


А потом анализировать rl и rr (сосед слева/справа) и выводить граничные значения во вспомогательную таблицу. Отсюда и n^2 проходов.

[Rainbow]

Традиционно, деревья поиска дают результат лучше. Но на построение дерева надо затратить определенные усилия - это понятно.

Есть "дерево промежутков" - дерево поиска, где в качестве вершин диапазоны. Вершина выше, если левая граница больше. Дополнительно в узле хранится максимум из правых границ поддерева. Дерево промежутков - это красно-черное дерево. Вставку нового элемента и поиск пересекающегося элемента обещают за O(logN)

[alibek]

СУБД - Oracle на брэндовой машине
Я себя конечно ценю, но навряд-ли я смогу на клиентской машине (в коде) сделать лучшую оптимизацию и поиск, чем оптимизатор Oracle и многоуровневые индексы
Появилась такая мысль, чтобы "складывать" диапазоны. Берется базовый диапазон (пустой) и на него поочередно накладываются все диапазоны Д1, тогда имеем не n^2, а n проходов. Только мысля эта смутная и никак не реализуется в коде.
Т.е. мысля конечно не смутная, можно создать битовое поле, выводить на него диапазоны, а потом сравнивать наложением маски. Только числа в диапазонах очень большие, никакой памяти не хватит. Попробую еще посоображать.

[skiperski]

Да, задачка ешё та... Вот тоже сидю, голову ломаю. Ничего не выдумывется