. | Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > СУБД, общие вопросы > Построение таблицы поиска отрезков, |
| Автор: Guest 18.8.2005, 14:29 |
| Есть множество отрезков {(a, b)}. Они м.б. любыми: пересекающимися, нулевыми и проч. Нужно построить таблицу, чтобы можно было организовать к ней запрос на SQL для выборки всех отрезков, которые содержат заданную точку c. Конечно, время работы должно быть ~ LogN, где N - число отрезков. Как это организовать? Надеюсь, кто-нить знает, слышал, или выдел. Заранее спасибо. |
| Автор: Akina 18.8.2005, 14:33 | ||
| ТаблицаОтрезков ID FirstPoint SecondPoint Запрос
|
| Автор: Guest 19.8.2005, 21:19 |
| Спасибо, Akina, но здесь время будет порядка O(N), а нужно O(logN) . |
| Автор: LSD 21.8.2005, 00:44 | ||
Для запроса
при наличии индекса на столбцы first_point и second_point СУБД, вначале просканирует индекс и получит идентификаторы строк, а затем по нему будет произведена выборка. Для индекса поиск значения равного константе как раз имеет время порядка log(N). |
| Автор: Guest 21.8.2005, 21:23 |
| Спасибо, может я неправильно выразился: отрезок (a, b) содержит точку с значит, что a <= c <= b. Так нужно выбрать все такие отрезки, не только по граничным значениям. |
| Автор: Akina 21.8.2005, 22:42 | ||
В таком случае та же структура, индекс по обеим точкам, гарантированно FirstPoint < SecondPoint и запрос
который на индексе работает за log(N) |
| Автор: Guest 22.8.2005, 21:08 |
| Спасибо. Просто логарифм очь важен: а как тогда отсортирована таблица должна быть? По левой границе, а по правой? Ведь он сначала найдет по левым границам - ну за logN, а потом ведь по правым границам возможны разрывы хоть через один или несколько отрезков: если правая граница будет лежать левее точки с, то каждый такой отрезок -- в отсев. |
| Автор: LSD 22.8.2005, 21:26 |
| 1. Время сильно зависит от того какие данные будут в таблице, может получиться так, что 90% запросов будут вытягивать 50% данных, а в этом случае индес не эффективен. И логарифма тут не будет. 2. Как именно будет выполняться запрос зависит от СУБД. Чтобы разговор был более предметным стоит указать какая база используется. |
| Автор: Akina 22.8.2005, 21:35 | ||
Ты что, ничего не знаешь про индексы? ну почитай ХОТЬ ЧТО-НИБУДЬ!!! |
| Автор: Guest 23.8.2005, 02:54 |
| Индексы знаю, но вот цели пока не добился. Нельзя же отсортировать сразу по обеим границам одновременно, а без этого бинарный поиск не будет работать для второй границы и log на смарку. |
| Автор: Akina 23.8.2005, 07:52 |
| Может я чего не понимаю... но если идет бинарный поиск по первому, индекс, соответственно О=log(N), а внутри отобранного уже прямое сканирование и О=N, то совокупно-то получается O=log(N)... |
| Автор: Guest 23.8.2005, 17:52 |
| Я тоже ничего не понял. Второй поиск тоже должен быть бинарным. Я так думаю создать два B-дерева для обеих границ. Выбрать по первой, выбрать по второй. Это будет O(LogN) + O(LogN) = O(LogN). Затем сделать пересечение записей. Легко сказать - сложно сделать. |
| Автор: maxim1000 23.8.2005, 18:05 | ||
с базами данных я не очень знаком, но...
такое не всегда возможно по очень простой причине время выполнения запроса не может быть меньше чем O(M), где M - количество результатов так что, если M будет сравнимо с N (а это может часто бывать, когда мнго отрезков имеют большое пересечение), то O(log N) никак не получится... |
| Автор: LSD 23.8.2005, 19:17 | ||||
Сделать то можно, на Oracle я получил такой план:
Вот только кто сказал что выборка значений по B-дереву займет O(LogN)? Все зависит от того сколько записей надо выбрать, время будет порядка O(LogN) только если будет выбираться малое количество записей. А потом еще пересечение полученных результатов, тоже может занять много времени. В общем случае, если ничего не известно о исходных данных, ничего гарантировать нельзя. Может максимальная длинна известна, или отрезки можно разбить на некие "участки", или еще что нибудь? |
| Автор: Guest 23.8.2005, 21:58 |
| Инфы никакой нет. Хотя отрезки уже даны -- но использование специфики, наверное, приведет к усложнению при добавлении/удалении отрезков. Если множество отреззков будет меняться динамически, то не на что и опереться то в общем случае. Спасибо большое, LSD  . С O(LogN) ты верно подметил. Просто есть понятия скорости работы в среднем, в худшем и в лучшем случае. Здесь как раз O(LogN) в среднем и получается. Про пересечение ничего определенногог сказать не могу -- все зависит от того, как оно в СУБД реализовано внутренне, но думаю, что время будет не больше, чем число пересекаемых записей, а значит в среднем даже o(LogN).Буду с этим разбираться.  |