Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14095 Откуда: Москва Дата регистрации: 02.09.2000 |
По условию задачи входные данные - есть величина постоянная.
Поэтому достаточно один раз построить индекс, а потом им пользоваться. |
Re: Поиск ближайшей точки | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Здесь константа это таблица координат точек. Координаты точки, для которой нужно найти ближайшую из этой таблицы, всякий раз произвольные. Поэтому и индекс не может быть константой. Как бы он не строился, он не может не учитывать эти произвольные координаты, поэтому всякий раз индексы надо строить заново.
|
Re: Поиск ближайшей точки | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Щас посмотрел на бумаге свою мыслю насчет геометрического места точек, расстояние от которых до некоторой точки из таблицы будет не больше, чем до любой другой точки из этой таблицы. Такое место существует для любой точки, получается либо многоугольник, либо полуплоскость(ограниченная либо прямой, либо ломаной, либо двумя параллельными прямыми). Осталось только придумать нормальный алгоритм, на проверку принадлежности заданной точки этому многоугольнику или полуплоскости.
Ну и естественно закодить алгоритм нахождения этого самого места. На бумаге то все просто. Соединил данную точку со всеми остальными отрезками, построил к отрезкам серединные перпендикуляры. По точкам (причем не всем)пересечений этих перпендикуляров и будет проходить граница искомой области, либо открытая, либо замкнутая. А вот составить алгоритм тут явно непросто. Исправлено 2 раз(а). Последнее : medstrax, 01.03.10 21:20 |
Re: Поиск ближайшей точки | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Задача может иметь реальное применение. Только надо от плоскости перейти к точкам на поверхности шара ;)
|
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Родион, идея неплоха, но ошибочка вкралась. Проверьте хотя бы на таких данных
Scan нужно подправить. На самом деле могут быть такие данные, что полный перебор - лучший способ. Представьте, что все точки находятся на равном расстоянии от заданной, и распределены по окружность примерно равномерно, и только одна точка расположена чуть-чуть ближе. Никакие отсечения не помогут, пока мы не просчитаем расстояние именно для этой точки, а она может попасться последней. В то же время во многих случаях улучшить алгоритм можно. Идея - достаточно быстро найти точку, которая расположена ближе к заданной, чем подавляющее большинство других, а потом отсеять большинство с помощью индекса. Вы, я так понял, именно это и пытались реализовать. Но я бы сделал отдельные индексы по X и по Y. Тогде на последнем этапе можно больше точек отсеять. |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14601 Дата регистрации: 01.04.2004 |
Теория говорит, что если экстремум единственный, то можно использовать какие-то численные методы (тот же самый градиент или метод случайного поиска), а вот если экстремумов несколько, то только перебором. Более того, наименьшее значение может и не быть минимумом. ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Теория, конечно, говорит, только совсем не это. Не надо все валить в одну кучу. Градиентный метод применяется для нахождения экстремумов функций непрерывных переменных (потому как для дискретных понятие градиента не определено), а перебор - только для дискретных (потому как для непрерывных слишком много перебирать надо). |
Re: Поиск ближайшей точки | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Внутри же "области допустимых решений" скорее всего только перебором и можно искать. Как "улучшение" алгоритма - определять не "максимальные" расстояния между ближайшими точками по осям, а некие средние (да хоть бы и средние арифметические - т.е. (мах(x)-min(x))/число точек) а потом последовательно расширять интервал (например удваивая "ширину" прямоугольника) пока в нём не окажется хотя-бы одна точка, а сцепка их в одно выражение бессмысленна, т.к. "диапазон" по первому из включенных полей сделает невозможным задание диапазона по второму полю. Ну т.е. если взять для наглядности не BINTOC а обычный STR(x)+STR(y) - то для задания "прямоугольника поиска" по X от 10 до 15 и по Y от 100 до 120 это выливается в условие диапазона индекса от "__10_100" до "__15_120" - что включает совершенно неподходящее "__11_999" и т.п. P.S. Не знаю как у Родиона, а у меня для локальной таблицы в 1000000 записей (13Мб) полный перебор с обычным выражением для расстояния между 2-мя точками занимает всего 3.5 секунды, что IMHO вполне приемлемо Поделился бы стат. параметрами таблицы точек (диапазоны по осям, число точек, равномерность заполнения и т.п.), и заданным критерием на скорость поиска - т.е. до скольких секунд разгонять надобно P.P.S. Чё-то на ночь глядя пургу гоню, это ж он сцеплять таблицы не могЁт по 2-м индексам, а искать как раз очень даже могЁт! Итого - делаем индексы по X и по Y (2 отдельных), потом определяем (MAX - MIN) по обеим осям (если это не известно заранее) берём RECCOUNT (предположим что удалённых записей нет) вычисляем "волшебный диапазон" - например Delta=(MAX-MIN)/RECCOUNT как самый простой, и даже тупо ставим 1 хотя всё зависит от "плотности" заполнения - у меня в стресс-тесте при значении этого коэффициента = 1 и размере таблицы в 10млн записей (124М таблица, 96М индекс) реально "точки" попадают в отбор лишь при Delta = 2048 - думаю что "начальное значение" можно эмпирически подбирать... Потом крутим цикл. Итого:
------------------ WBR, Igor Исправлено 1 раз(а). Последнее : Igor Korolyov, 02.03.10 03:32 |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14601 Дата регистрации: 01.04.2004 |
Леонид. Не понял, при чем здесь непрерывные ф-ии. Мы говорим о численном решении ф-ии, для которой известны узлы X, Y, те не надо задаваться приращением, оно уже определено в точках эксперимента. ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Система координат в int Т.е. +- 2^31 Шаг, соответственно, тоже целое число. Используется большая часть диапазона. Весьма! Попробую реализовать. Нет, идея не в этом. Я ищу первую попавшуюся точку, близкую по X, и сразу отсекаю все заведомо далёкие по Х точки. Профит получается если первая точка достаточно близка к искомой. ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер Исправлено 2 раз(а). Последнее : Goodwin, 02.03.10 09:25 |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Ага. Косячёк. Забыл lnMinPointId инициализировать. Вот так лучше работает:
------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер Исправлено 1 раз(а). Последнее : Goodwin, 02.03.10 09:25 |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Игорь, браво!
Всё гениальное просто. Я никак не мог допетрить, как два индекса связать - с составным пытался выкрутиться. Сейчас буду сравнивать все варианты. Что касается исходных данных: точек порядка 50тыс, разбросаны хаотично. Приемлимое время поиска <10^(-2) сек. ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Игорь, у тебя в методе есть один недостаток. Если, например, при Delta=10 получим _tally=1 и в этом квадрате будет содержаться точка (9, 9), то это вовсе не означает, что на ней будет достигаться минимум, он может достигаться, например, в точке (11, 0). Т.е. нужно сделать еще один шаг, умножив Delta на sqrt(2). Кстати, nofilter нужен только на этом последнем шаге, все остальные лучше делать без него. Кроме того, Delta вполне можно найти и поточнее половинным делением, так, что при Delta = M-1 _tally=0, а при Delta = M _tally>0. И еще для поиска Delta можно вместо select использовать обычный locate, может быть это чуть побыстрее будет. Но все-таки, в самом плохом случае, если в область, полученную после умножения Delta на sqrt(2) попадут все точки, без полного перебора не обойтись.
2 PaulWist Цитата:Вот именно поэтому тут градиентный метод вообще неприменим, а вовсе не потому, что экстремумов может быть несколько. И все-таки полный перебор не единственно возможный в подобных случаях метод. |
Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14095 Откуда: Москва Дата регистрации: 02.09.2000 |
Да не работает это. В принципе. Нельзя выполнять поиск по очереди. Сначала по одной координате, потом по другой. Можно только ОДНОВРЕМЕННО! Ну, представь, что у тебя две точки X1 = 2 Y1 = 100 X2 = 50 Y2 = 0 Задаются координаты X3 = 1 Y3 = 1 Ты определишь, что ближайшая точка по X = это первая точка. А вторую точку ты вообще не найдешь! |
Re: Поиск ближайшей точки | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Тогда, как вариант, рассматривать после определения дельта не прямоугольник, а круг с центром в заданной точке, увеличивая радиус при _tally=0.
Исправлено 2 раз(а). Последнее : ry, 02.03.10 12:03 |
Re: Поиск ближайшей точки | |
---|---|
Владимир Максимов Сообщений: 14095 Откуда: Москва Дата регистрации: 02.09.2000 |
Я на эти "грабли" тоже радостно налетел. В смысле - идея хорошая, но надо поправить. А идея в корне не верна! Проблема в том, что расстояние - это радиус. Т.е. описывает окружность. А делать "отсечку" прямоугольником - это заведом потерять некоторые значения. Ну, представь круг в который вписан прямоугольник. Вершины прямоугольника находятся на линии окружности. Соответственно, всегда есть точки, лежащие внтури круга, но вне прямоугольника. Как следствие, искать какие-то минимумы/максимумы по каждой координате в отдельности, а потом это все сводить - бессмысленно. Ничего это не даст. Ну, разве что, в каких-то исключительных случаях. В идеале, хорошо бы перейти в полярные координаты. Но сдвиг начала координат в искомую точку сведет "на нет" весь выигрыш от изменения системы координат. |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Итоги (в секундах):
------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Очень даже работает. Если на пальцах: нахожу точку ближайшую по Х (не оптимальну, но что дали.) Считаю расстояние до этой точки - D. И сразу отсекаю все точки, отстоящие по Х от стартовой более чем на D, т.к. расстояние до них заведомо больше, чем до уже найденной. На больших массивах очень даже помогает. ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Кстати, про ошибки в алгоритмах: пока они выдают одинаковые результаты
Вот, собсно, весь бенчмарк: Возможно, подёргав за nDeltaStart и nDeltaStep можно улучшить результаты шаговых алгоритмов.
------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер Исправлено 1 раз(а). Последнее : Goodwin, 02.03.10 12:10 |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14601 Дата регистрации: 01.04.2004 |
Хорошо, чем численное решение непрерывной ф-ии будет отличаться от решения когда есть дискреты приращения по X и Y, только одним - величиной приращения, по другому не бывает - это численное решение, а не аналитическое.
Согласен, не единственно возможный, НО единственный дающий однозначное решение во всей области определения. ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) Исправлено 1 раз(а). Последнее : PaulWist, 02.03.10 12:24 |
© 2000-2024 Fox Club  |