 |
|
Модераторы: LSD |
 
|
|
Построение таблицы поиска отрезков, содержащих указанную точку 
| Guest |
|
|||
|
Unregistered |
Есть множество отрезков {(a, b)}. Они м.б. любыми: пересекающимися, нулевыми и проч. Нужно построить таблицу, чтобы можно было организовать к ней запрос на SQL для выборки всех отрезков, которые содержат заданную точку c. Конечно, время работы должно быть ~ LogN, где N - число отрезков. Как это организовать? Надеюсь, кто-нить знает, слышал, или выдел. Заранее спасибо.
|
|||
|
||||
Загрузка ...
| Akina |
|
|||
|
Советчик  Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 13 Всего: 454 |
ТаблицаОтрезков
ID FirstPoint SecondPoint Запрос
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| Guest |
|
|||
|
Unregistered |
Спасибо, Akina, но здесь время будет порядка O(N), а нужно O(logN)
 . |
|||
|
||||
| LSD |
|
|||
 Leprechaun Software Developer Профиль Группа: Модератор Сообщений: 15718 Регистрация: 24.3.2004 Где: Dublin Репутация: 24 Всего: 538 |
Для запроса
при наличии индекса на столбцы first_point и second_point СУБД, вначале просканирует индекс и получит идентификаторы строк, а затем по нему будет произведена выборка. Для индекса поиск значения равного константе как раз имеет время порядка log(N). -------------------- Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it. |
|||
|
||||
| Guest |
|
|||
|
Unregistered |
Спасибо, может я неправильно выразился: отрезок (a, b) содержит точку с значит, что a <= c <= b. Так нужно выбрать все такие отрезки, не только по граничным значениям.
|
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 13 Всего: 454 |
В таком случае та же структура, индекс по обеим точкам, гарантированно FirstPoint < SecondPoint и запрос
который на индексе работает за log(N) -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| Guest |
|
|||
|
Unregistered |
Спасибо. Просто логарифм очь важен: а как тогда отсортирована таблица должна быть? По левой границе, а по правой? Ведь он сначала найдет по левым границам - ну за logN, а потом ведь по правым границам возможны разрывы хоть через один или несколько отрезков: если правая граница будет лежать левее точки с, то каждый такой отрезок -- в отсев.
|
|||
|
||||
| LSD |
|
|||
|
Leprechaun Software Developer Профиль Группа: Модератор Сообщений: 15718 Регистрация: 24.3.2004 Где: Dublin Репутация: 24 Всего: 538 |
1. Время сильно зависит от того какие данные будут в таблице, может получиться так, что 90% запросов будут вытягивать 50% данных, а в этом случае индес не эффективен. И логарифма тут не будет.
2. Как именно будет выполняться запрос зависит от СУБД. Чтобы разговор был более предметным стоит указать какая база используется. -------------------- Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it. |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 13 Всего: 454 |
Ты что, ничего не знаешь про индексы? ну почитай ХОТЬ ЧТО-НИБУДЬ!!! -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| Guest |
|
|||
|
Unregistered |
Индексы знаю, но вот цели пока не добился. Нельзя же отсортировать сразу по обеим границам одновременно, а без этого бинарный поиск не будет работать для второй границы и log на смарку.
|
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 13 Всего: 454 |
Может я чего не понимаю... но если идет бинарный поиск по первому, индекс, соответственно О=log(N), а внутри отобранного уже прямое сканирование и О=N, то совокупно-то получается O=log(N)...
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| Guest |
|
|||
|
Unregistered |
Я тоже ничего не понял. Второй поиск тоже должен быть бинарным.
Я так думаю создать два B-дерева для обеих границ. Выбрать по первой, выбрать по второй. Это будет O(LogN) + O(LogN) = O(LogN). Затем сделать пересечение записей. Легко сказать - сложно сделать. |
|||
|
||||
| maxim1000 |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: нет Всего: 110 |
с базами данных я не очень знаком, но...
такое не всегда возможно по очень простой причине время выполнения запроса не может быть меньше чем O(M), где M - количество результатов так что, если M будет сравнимо с N (а это может часто бывать, когда мнго отрезков имеют большое пересечение), то O(log N) никак не получится... -------------------- qqq |
|||
|
||||
| LSD |
|
||||
|
Leprechaun Software Developer Профиль Группа: Модератор Сообщений: 15718 Регистрация: 24.3.2004 Где: Dublin Репутация: 24 Всего: 538 |
Сделать то можно, на Oracle я получил такой план:
Вот только кто сказал что выборка значений по B-дереву займет O(LogN)? Все зависит от того сколько записей надо выбрать, время будет порядка O(LogN) только если будет выбираться малое количество записей. А потом еще пересечение полученных результатов, тоже может занять много времени. В общем случае, если ничего не известно о исходных данных, ничего гарантировать нельзя. Может максимальная длинна известна, или отрезки можно разбить на некие "участки", или еще что нибудь? -------------------- Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it. |
||||
|
|||||
| Guest |
|
|||
|
Unregistered |
Инфы никакой нет. Хотя отрезки уже даны -- но использование специфики, наверное, приведет к усложнению при добавлении/удалении отрезков. Если множество отреззков будет меняться динамически, то не на что и опереться то в общем случае.
Спасибо большое, LSD  . С O(LogN) ты верно подметил. Просто есть понятия скорости работы в среднем, в худшем и в лучшем случае. Здесь как раз O(LogN) в среднем и получается. Про пересечение ничего определенногог сказать не могу -- все зависит от того, как оно в СУБД реализовано внутренне, но думаю, что время будет не больше, чем число пересекаемых записей, а значит в среднем даже o(LogN).Буду с этим разбираться.  |
|||
|
||||
|
|
| Правила форума "Общие вопросы по базам данных" | |
|
|
Данный форум предназначен для обсуждения вопросов о базах данных не попадающих под тематику других форумов:
Данный форум не предназначен для:
Если вы не соблюдаете эти правила, не удивляйтесь потом не найдя свою тему/сообщение.
Полезные советы: Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, LSD, Zloxa. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | СУБД, общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.1613 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |