ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый поиск интервалов, в котором наводится точка.
25 сообщений из 26, страница 1 из 2
  1  все
Быстрый поиск интервалов, в котором наводится точка.
    #39055446
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Задача теоритеческая: пусть имеется массив из N интервалов заданных начальной и конечной границей.
Необходимо найти алгоритм с минималной алгоритмической сложностью, который находит все интервалы, которые включают в себя заданную точку. О интервалах ничего заранее не известно. Перед поиском можно предварително обработать массив.
Инетересует есть ли что-нибудь быстрее чем O(N) и что.
...
Рейтинг: 0 / 0
18.09.2015, 17:02
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055462
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Если отсортировать по началам отрезков, то можно перебор с начала массива и остановится как только начало > искомой точки. Немного быстрее O(N)
...
Рейтинг: 0 / 0
18.09.2015, 17:09
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055484
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
А если отсортировать отрезки а потом искать методом половинного деления, то можно сократить O(log n)
...
Рейтинг: 0 / 0
18.09.2015, 17:22
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055487
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Dima TЕсли отсортировать по началам отрезков, то можно перебор с начала массива и остановится как только начало > искомой точки. Немного быстрее O(N)
Это оптимзация не изменяет алгоритмическую сложнось, но на практике конечно плюс.
А можно ещё быстрее?
...
Рейтинг: 0 / 0
18.09.2015, 17:23
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055488
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Dima TЕсли отсортировать по началам отрезков,
какова трудоёмкость сортировки?
...
Рейтинг: 0 / 0
18.09.2015, 17:24
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055493
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
White OwlА если отсортировать отрезки а потом искать методом половинного деления, то можно сократить O(log n)
отсортировать отрезки по какому критерию?
Если по началу интервала то быстрее не будет, потому что нужно будет проверить 1/2 * N интервалов на вхождение.
O(C*N) = O(N)
В вашем случае C = 1/2
...
Рейтинг: 0 / 0
18.09.2015, 17:26
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055494
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
mikron,

Может помочь R-Tree-индекс (Spatial index), насколько я помню.
...
Рейтинг: 0 / 0
18.09.2015, 17:27
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055496
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
ИзопропилDima TЕсли отсортировать по началам отрезков,
какова трудоёмкость сортировки?
Стоимость предварителной обработки не учитывается. Это в условии задачи оговорено.
...
Рейтинг: 0 / 0
18.09.2015, 17:28
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055512
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
R-Tree не подойдут: во первых не мнгомерные данные. Во вторых нужно найти все интервалы а не один.
А вот это похоже годится
...
Рейтинг: 0 / 0
18.09.2015, 17:44
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055541
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
mikronСтоимость предварителной обработки не учитывается. Это в условии задачи оговорено.
В таком случае можно в качестве предобработки поделить весь интервал, покрываемый этими интервалами (min(start)...max(end)) на набор непрерывных отрезков, и составить таблицу, располагается ли конкретный частный интервал на каждом из отрезков, с градацией полностью/частично. Тогда по заданной координате половинным делением получаем сразу список частных интервалов, которые следует проверять на попадание в них точки (те, что частично), и список тех, в которые точка гарантированно попадает (те, что полностью).
Думать, на какое количество отрезков оптимально рубить диапазон, лениво... тем более думать о том, что в оптимуме они могут быть неравными по размеру.
...
Рейтинг: 0 / 0
18.09.2015, 18:04
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055591
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
mikronR-Tree не подойдут: во первых не мнгомерные данные. Во вторых нужно найти все интервалы а не один."Много" легко сводится к одному. И все интервалы вполне себе ищутся.
В некоторых СУБД уже готовая механика для этого есть, например, в MySQL в движке MyISAM.
...
Рейтинг: 0 / 0
18.09.2015, 18:37
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055594
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
AkinaДумать, на какое количество отрезков оптимально рубить диапазон, лениво... тем более думать о том, что в оптимуме они могут быть неравными по размеру.Так прям по списку вершин и рубить. Будет порядка 2N интервалов.
...
Рейтинг: 0 / 0
18.09.2015, 18:39
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055608
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
mikronWhite OwlА если отсортировать отрезки а потом искать методом половинного деления, то можно сократить O(log n)
отсортировать отрезки по какому критерию? По началам или концам, не важно. Главное чтобы можно было сказать: вот это граничный элемент и все элементы левее него не удовлетворяют".

mikronЕсли по началу интервала то быстрее не будет, потому что нужно будет проверить 1/2 * N интервалов на вхождение.
O(C*N) = O(N)
В вашем случае C = 1/2Ну.... да с я поторопился. Но в общем, если начать с бинарного поиска, то получится: на поиск любого удовлетворяющего отрезка по критерию одного конца. И потом проход влево и вправо от него для поиска остальных интервалов. И это уже будет ...
...
Рейтинг: 0 / 0
18.09.2015, 18:48
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055613
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
А еще можно сократить исходный массив.
В основном массиве оставляем отрезки с уникальными началами и минимальными концами. И к каждому элементу привязываем дополнительный массив в который скидываем все отрезки у которых такие-же начала, но которые более длинные. Тогда будет достаточно найти все "минимальные" отрезки и автоматом взять все привязанные к ним более длинные отрезки.
Суммарная сложность поиска все равно O(N) останется, но если в исходном наборе было много отрезков с повторяющимися началами - может хорошо ускорить.
...
Рейтинг: 0 / 0
18.09.2015, 19:02
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055617
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
White OwlА еще можно сократить исходный массив.
В основном массиве оставляем отрезки с уникальными началами и минимальными концами. И к каждому элементу привязываем дополнительный массив в который скидываем все отрезки у которых такие-же начала, но которые более длинные. Тогда будет достаточно найти все "минимальные" отрезки и автоматом взять все привязанные к ним более длинные отрезки.
Суммарная сложность поиска все равно O(N) останется, но если в исходном наборе было много отрезков с повторяющимися началами - может хорошо ускорить.Не, соврал опять. Не самые минимальные надо оставлять в основном массиве, а такие чтобы обеспечивали непрерывное покрытие всего диапазона. И те которые меньше.
...
Рейтинг: 0 / 0
18.09.2015, 19:06
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055751
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
miksoftmikronR-Tree не подойдут: во первых не мнгомерные данные. Во вторых нужно найти все интервалы а не один."Много" легко сводится к одному. И все интервалы вполне себе ищутся.
В некоторых СУБД уже готовая механика для этого есть, например, в MySQL в движке MyISAM.
Объясните пожалуйста, как должен работатъ алгоритм поиска всех интервалов на одномерном R+-Tree.
Так-же интересно, какое преимущество даёт использование вырожденного R+ дерева по сравнению c B+ деревом для данной задачи.
И пожалуйста конструктивно, без лозунгов и словоблудия.
...
Рейтинг: 0 / 0
18.09.2015, 23:07
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055757
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
По приведённой мной ссылке пока лучший алгоритм O(log n + m)
Там же указывает что для дискретного случая известен алгоритм O(1 + m)
Странно что неизвестно подобного для общего случая со сложностью O(1 + m)
...
Рейтинг: 0 / 0
18.09.2015, 23:20
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055765
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eNose
Участник
[не активирован]
[не одобрен]
mikronИнетересует есть ли что-нибудь быстрее чем O(N) и что. напрямую зависит от границ интервалов, ограничения на начальную инициализацию и языка.

а то ведь можно инициализировать по адресуемой памяти (со смещением) заранее.и задача сведется к обращению по адресу.
...
Рейтинг: 0 / 0
18.09.2015, 23:38
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39055771
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eNose
Участник
[не активирован]
[не одобрен]
mikronЗадача теоритеческая "Решение существует" - воскликнет математик/физик.
Потому программирование - ПРИКЛАДНАЯ математика. Исходя из ограничений решение надо искать, а не теоретическое.
В теории может быть всё плохо, а на практике - прекрасно. И наоборот.
...
Рейтинг: 0 / 0
18.09.2015, 23:50
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39057117
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
mikronWhite OwlА если отсортировать отрезки а потом искать методом половинного деления, то можно сократить O(log n)
отсортировать отрезки по какому критерию?
Если по началу интервала то быстрее не будет, потому что нужно будет проверить 1/2 * N интервалов на вхождение.
O(C*N) = O(N)
В вашем случае C = 1/2


2 вложенных сортировки

1 по началу отрезка
2 внутри сортировки по началу,
отсортировать по убыванию длины.

Сохранить точки в которых длина увеличиватеся в порядке
сортировки по началу в отдельном списке.

Путем вычитания проверяем вхождение.
Как только в диапазон не попадаем переходим
к следующей точке с большей длиной.

Некоторые наборы диапазонов могут
потребовать другой сортировки,
сначала сортируем по длине, внутренюю сортирорвку
делаем по точке начала.

Приблизительно так.....
...
Рейтинг: 0 / 0
21.09.2015, 11:22
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39057139
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
ДохтаРmikronпропущено...

отсортировать отрезки по какому критерию?
Если по началу интервала то быстрее не будет, потому что нужно будет проверить 1/2 * N интервалов на вхождение.
O(C*N) = O(N)
В вашем случае C = 1/2


2 вложенных сортировки

1 по началу отрезка
2 внутри сортировки по началу,
отсортировать по убыванию длины.

Сохранить точки в которых длина увеличиватеся в порядке
сортировки по началу в отдельном списке.

Путем вычитания проверяем вхождение.
Как только в диапазон не попадаем переходим
к следующей точке с большей длиной.

Некоторые наборы диапазонов могут
потребовать другой сортировки,
сначала сортируем по длине, внутренюю сортирорвку
делаем по точке начала.

Приблизительно так.....


Первый вариант сортировок годится если имеет много
диапазонов с одинаковым началом но разной длиной.
Второй вариант , сначала по длине внутри по точке начала
для случаев равномерного распределения.

Второй варинат сортировки по длине думаю будет
оптимальнее по производительности на среднепотолочныз отрезках.
...
Рейтинг: 0 / 0
21.09.2015, 11:35
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39057150
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
miksoftВ некоторых СУБД уже готовая механика для этого есть, например, в MySQL в движке MyISAM.
Подскажи как конкретно эта механика называется. Почитаю. Нагуглить не получилось.
...
Рейтинг: 0 / 0
21.09.2015, 11:49
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39057174
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Dima TmiksoftВ некоторых СУБД уже готовая механика для этого есть, например, в MySQL в движке MyISAM.
Подскажи как конкретно эта механика называется. Почитаю. Нагуглить не получилось. FAQ: Нахождение записей, где заданное значение находится между значениями полей
...
Рейтинг: 0 / 0
21.09.2015, 12:13
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39057247
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
AkinamikronСтоимость предварителной обработки не учитывается. Это в условии задачи оговорено.
В таком случае можно в качестве предобработки поделить весь интервал, покрываемый этими интервалами (min(start)...max(end)) на набор непрерывных отрезков, и составить таблицу, располагается ли конкретный частный интервал на каждом из отрезков, с градацией полностью/частично. Тогда по заданной координате половинным делением получаем сразу список частных интервалов, которые следует проверять на попадание в них точки (те, что частично), и список тех, в которые точка гарантированно попадает (те, что полностью).
Думать, на какое количество отрезков оптимально рубить диапазон, лениво... тем более думать о том, что в оптимуме они могут быть неравными по размеру.

А если длину каждого отрезка устремить к нулю(ведь объем предварительных расчётов нас не волнует), то результирующая асимптотика будет O(1).
...
Рейтинг: 0 / 0
21.09.2015, 13:09
| Ответить | Цитировать | Написать  
Быстрый поиск интервалов, в котором наводится точка.
    #39057318
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
miksoft FAQ: Нахождение записей, где заданное значение находится между значениями полей
Спасибо за ссылку. В форум по MySQL не догадался заглянуть. В MSSQL тоже есть что-то похожее .

SashaMercuryА если длину каждого отрезка устремить к нулю(ведь объем предварительных расчётов нас не волнует), то ...
... то объем метаданных устремится в бесконечность
...
Рейтинг: 0 / 0
21.09.2015, 13:53
| Ответить | Цитировать | Написать  
25 сообщений из 26, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый поиск интервалов, в котором наводится точка.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39057247&tid=1340927]:
 0ms
get settings:
 12ms
get forum list:
 18ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 34ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 59ms
get tp. blocked users:
 1ms
others: 238ms
total:  384ms
созд. / загр.: 384ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]