Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Задача:
Есть таблица с координатами точек (PoindId i, coordX i, coordY i) Нужно найти в этой таблице точку, ближайшую к заданным координатам. Т.е. что-то вроде
Проблема: слишком медленно. Данные в исходной таблице не меняются, меняются только координаты искомой точки, Поэтому исходную таблицу предварительно можно как угодно сортировать, индексировать, менять структуру и т.д. Лишь бы потом в ней быстро искалось. Или поиск на сях переписать. Или и то и другое. Видел кто подходящие алгоритмы - ничего толкового придумать не могу. ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
А если запросом?
|
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Не, запрос примерно в два раза дольше скана выполняется.
Тут, как мне кажется, нужно изначальную таблицу как-то оптимизировать для быстрого поиска. ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Вот чего в голову пришло:
Думаю дальше. ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер Исправлено 1 раз(а). Последнее : Goodwin, 01.03.10 17:27 |
Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Извлечение квадратного корня - лишняя операция на стадии определения минимума.
Функция квадратного корня гладкая и возрастающая. Это значит, что если значение функции минимальное, то минимально и значение аргумента этой функции. Если взять формулу определения расстояния без корня, то имеем (lnPointX-coordX)^2+(lnPointY-coordY)^2 После раскрытия скобок и некоторого переупорядочивания получим (lnPointX^2 + lnPointY^2) - 2*(lnPointX*coordX + lnPointY*coordY) + (coordX^2 + coordY^2) В этом переупорядочивании 3 группы: (lnPointX^2 + lnPointY^2) - константа, которую можно вычислить до начала расчета (coordX^2 + coordY^2) - значение, никак не зависящее от положения точки, расстояние до которой определяем. Т.е. это значение можно добавить отдельным столбцом в таблицу координат Ну, и третье слагаемое, которое, собственно, и придется рассчитывать
Правда, тут я не уверен, насколько предварительное вычисление части выражения ускорит/замедлит поиск по сравнению с запросом без предварительных вычислений
Это можно проверить только экспериментально |
Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Упрощаем логику дальше
Функция квадрата - это парабола. Если "разрезать" по вертикальной оси, то опять же имеем гладкую возрастающую функцию. Т.е. минимум функции совпадает с минимумом аргумента. Убираем квадрат. Прямая линия тоже гладкая возрастающая. Но в контексте данной задачи для поиска минимума подходит только положительная часть. Отрицательную часть надо брать по модулю. В общем, вместо суммы квадратов можно использовать суммы по модулю
Что будет быстрее - опять же проверяется экспериментально. |
Re: Поиск ближайшей точки | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Не знаю, как это повлияет на скорость, но можно попробовать сначала отсечь ненужные области сравнения, а потом вычислять расстояния по оставшимся точкам.
Исправлено 1 раз(а). Последнее : ry, 01.03.10 12:41 |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Попробовал оптимизировать через добавление поля и избавление от корня по варианту Владимира.
Время поиска не изменилось. Т.е. тормоза не от вычислений, а от перебора записей. Стало быть помогут только индексы и отсечение записей без просмотра оных. Попробую индексами разбить всё поле на клетки, и рассматривать их по разворачивающейся спирали... ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Нет, так не получится. Точка (0.6, 0.6) ближе к началу координат, чем (1, 0), а сумма модулей у нее больше. |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Если ф-ия имеет несколько экстремумов, то нахождение min-значения возможно только перебором всего массива, другие численные методы не подойдут.
------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Точно. А я все думаю, что-то меня смущает в этом переходе от квадратов к числам, но проверять не стал. Для целочисленных коордитат тоже не подходит: (3,3) ближе к (0,0), чем (5,0), хотя сумма модулей будет больше в первом случае. Но уже выяснилось, что проблема не в вычислениях. Интересно, а сколько записей в таблице и как она проиндексирована? |
Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Да, забыл про переход через 1. Если известно, что расстояние по любой координате всегда больше 1, то замена квадратов на модуль - подойдет. Если нет, то не получится |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Кстати, надо вычислить для каждой точки длину вектора относительно точки начала координат, затем вычислить длину ветора для исходной точки и искать сравнивая длины векторов.
------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Как мне кажется, данный код в принципе не корректен. По сути, ты пытаешся сделать ограничение по каждой координате в отдельности, что, в общем случае, некорректно. Например, если разница по X = 0, зато по Y = 1000, то вместо минимального расстояния ты вполне можешь найти максимальное. Просто по первой анализируемой координате ты попал в минимум, хотя расстояние в этой координате максимальное. Или есть какие-то еще ограничения? |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Типа этого:
Только нет уверенности, что будет "летать" (тот же самый scan), вообще надо задаваться доверительным интервалом, тогда будет значительно быстрее ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Я выше приводил код, просто отсекающий в плоскости координат прямоугольник с центром в искомой точке, в котором гарантированно будет как минимум одна (а если повезет, то только одна) точка из таблицы. Дальше поиск по этой области, по идее, должен быть быстрым. Хотя будет ли быстрым само такое отсечение, можно проверить только на практике. Исправлено 2 раз(а). Последнее : ry, 01.03.10 17:48 |
Re: Поиск ближайшей точки | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Ересь все это, никакая оптимизация здесь невозможна. Дабы убедиться проведите мысленный эксперимент. Пусть эту же задачу вам предстоит решать, пользуясь только калькулятором, а исходная таблица перед вами на бумаге. Ежу понятно, что для каждой новой точки решить задачу можно только последовательно перебрав все строки в таблице. И любые дополнительные телодвижения, как то вычисление индексов, каких то предварительных рез-тов и пр.,
только замедлят процесс. Потому что все эти доп. телодвижения сводятся к одному и тому же - чтению всех записей из таблицы. ЗЫ. Шальная мысль. Что, если для каждой точки исходной таблицы определить геометрическое место точек, расстояние от которых до этой точке не больше расстояния до любой другой точки этой таблицы? Тогда при переборе не надо вычислять сумму квадратов, достаточно проверить лежит ли наша точка в том самом "геометрическом месте".Тут одно плохо, я даже не представляю себе как это геометрическое место будет выглядеть Возможно, проверка на принадлежность точки этому месту будет гораздо дольше чем посчитать 2 квадрата. Хотя в любом случае, как уже было сказано, время вычислений здесь пренебрежимо мало по сравнению со временем перебора записей. Хм, а вот и нифига я не прав. Если получится определить такое геометрическое место для каждой точки (в чем я вобще то не уверен), то задачу можно будет решать и без полного перебора. Полный перебор понадобится только если искомая точка в последней записи. Исправлено 1 раз(а). Последнее : medstrax, 01.03.10 19:10 |
Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
При использовании индексов чтение всех записей не происходит. Другой вопрос, можно ли здесь как-то "прикрутить" индекс. Хотя бы с целью предварительного ограничения области поиска. Кроме того, чем больше операций надо совершить, тем медленне все работает. Значит, уменьшая количество операций (например, убрав лишнее извлечение корня) и упрощая сами операции также можно получить ускорение.
Собственно, почти это и предложил ry. Только он вычислял расстояния до соседних (ближайших) точек. Но проблема данного решения в том, что оно не работает, если искомая точка окажется вне диапазона исходных точек. Ну, например, возьмем для простоты одномерную систему (линию). Есть всего две точки с координатами 1 и 2. Расстояние между ними 1. Если искомая точка будет лежать в координатах от 0 до 3, то предварительное ограничение прекрасно работает. А если искомая точка будет иметь координату, скажем 5? Предварительная отсечка диапазона не оставит нам вообще ни одной точки! |
Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
В порядке "бреда сумасшедшего"
Сама координатная сетка бесконечна? Т.е. координаты могут быть +/- бесконечность? Шаг сетки также никак не ограничен? Это я к тому, нельзя ли заранее рассчитать минимальное расстояние для любой возможной точки координатной сетки? Загоняем результаты расчета в таблицу и дальше просто ищем по индексу заданную точку и считываем заранее рассчитанный результа. |
Re: Поиск ближайшей точки | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Дык в том и суть - чтобы построить индексы для надо сперва прочитать все записи. Где здесь выигрыш? А строить индекс надо каждый раз заново для новых входных данных. |
© 2000-2024 Fox Club  |