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

Программирование на Visual Basic, главный форум. Обсуждение тем программирования на VB 1—6.
Даже если вы плохо разбираетесь в VB и программировании вообще — тут вам помогут. В разумных пределах, конечно.
Правила форума
Темы, в которых будет сначала написано «что нужно сделать», а затем просьба «помогите», будут закрыты.
Читайте требования к создаваемым темам.
alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 04.11.2003 (Вт) 9:41

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

skiperski
Идеолог
Идеолог
Аватара пользователя
 
Сообщения: 1386
Зарегистрирован: 25.06.2002 (Вт) 15:52

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

Сообщение skiperski » 04.11.2003 (Вт) 12:37

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

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

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

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Сообщение alibek » 04.11.2003 (Вт) 13:16

Диапазоны отсортированы (проиндексированы в базе данных). Тогда проверка введенного пользователем диапазона будет выглядеть как
Код: Выделить всё
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 проходов.
Lasciate ogni speranza, voi ch'entrate.

Rainbow
Человек-радуга
Человек-радуга
 
Сообщения: 543
Зарегистрирован: 13.05.2003 (Вт) 14:16

Сообщение Rainbow » 04.11.2003 (Вт) 14:26

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

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Сообщение alibek » 04.11.2003 (Вт) 16:26

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

skiperski
Идеолог
Идеолог
Аватара пользователя
 
Сообщения: 1386
Зарегистрирован: 25.06.2002 (Вт) 15:52

Сообщение skiperski » 04.11.2003 (Вт) 17:53

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


Вернуться в Visual Basic 1–6

Кто сейчас на конференции

Сейчас этот форум просматривают: AhrefsBot и гости: 8

    TopList  
cron