:: Игры Разума
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14095
Откуда: Москва
Дата регистрации: 02.09.2000
medstrax
Владимир Максимов
При использовании индексов чтение всех записей не происходит. Другой вопрос, можно ли здесь как-то "прикрутить" индекс. Хотя бы с целью предварительного ограничения области поиска.
Дык в том и суть - чтобы построить индексы для надо сперва прочитать все записи. Где здесь выигрыш? А строить индекс надо каждый раз заново для новых входных данных.

По условию задачи входные данные - есть величина постоянная.

Goodwin
Данные в исходной таблице не меняются, меняются только координаты искомой точки

Поэтому достаточно один раз построить индекс, а потом им пользоваться.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Здесь константа это таблица координат точек. Координаты точки, для которой нужно найти ближайшую из этой таблицы, всякий раз произвольные. Поэтому и индекс не может быть константой. Как бы он не строился, он не может не учитывать эти произвольные координаты, поэтому всякий раз индексы надо строить заново.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Щас посмотрел на бумаге свою мыслю насчет геометрического места точек, расстояние от которых до некоторой точки из таблицы будет не больше, чем до любой другой точки из этой таблицы. Такое место существует для любой точки, получается либо многоугольник, либо полуплоскость(ограниченная либо прямой, либо ломаной, либо двумя параллельными прямыми). Осталось только придумать нормальный алгоритм, на проверку принадлежности заданной точки этому многоугольнику или полуплоскости.
Ну и естественно закодить алгоритм нахождения этого самого места. На бумаге то все просто. Соединил данную точку со всеми остальными отрезками, построил к отрезкам серединные перпендикуляры. По точкам (причем не всем)пересечений этих перпендикуляров и будет проходить граница искомой области, либо открытая, либо замкнутая. А вот составить алгоритм тут явно непросто.



Исправлено 2 раз(а). Последнее : medstrax, 01.03.10 21:20
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Задача может иметь реальное применение. Только надо от плоскости перейти к точкам на поверхности шара ;)
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Goodwin
Вот чего в голову пришло:
index on bintoc(coordx)+bintoc(coordy) tag xy
set Near On
seek bintoc(nPointX)
seek bintoc(coordx)+bintoc(nPointY)
lnDistance=d()
seek bintoc(nPointX-lnDistance)
scan rest while coordX<=nPointX+lnDistance for lnDistance>d()
lnDistance=d()
lnMinPointId=pointId
endscan
function d
return sqrt((nPointX-coordX)^2+(nPointY-coordY)^2)
индексирует долго, за то потом ищет разов в сто быстрее скана.

Думаю дальше.

Родион, идея неплоха, но ошибочка вкралась. Проверьте хотя бы на таких данных
create cursor tmp (pointId i, coordx i, coordy i)
insert into tmp values (1, 0, 2)
insert into tmp values (2, 0, 0)
insert into tmp values (3, 0, 1)
nPointX = 0
nPointY = 0

Scan нужно подправить.

На самом деле могут быть такие данные, что полный перебор - лучший способ. Представьте, что все точки находятся на равном расстоянии от заданной, и распределены по окружность примерно равномерно, и только одна точка расположена чуть-чуть ближе. Никакие отсечения не помогут, пока мы не просчитаем расстояние именно для этой точки, а она может попасться последней. В то же время во многих случаях улучшить алгоритм можно. Идея - достаточно быстро найти точку, которая расположена ближе к заданной, чем подавляющее большинство других, а потом отсеять большинство с помощью индекса. Вы, я так понял, именно это и пытались реализовать. Но я бы сделал отдельные индексы по X и по Y. Тогде на последнем этапе можно больше точек отсеять.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
PaulWist

Сообщений: 14601
Дата регистрации: 01.04.2004
ry
PaulWist
вообще надо задаваться доверительным интервалом, тогда будет значительно быстрее
Я выше приводил код, просто отсекающий в плоскости координат прямоугольник с центром в искомой точке, в котором гарантированно будет как минимум одна (а если повезет, то только одна) точка из таблицы. Дальше поиск по этой области, по идее, должен быть быстрым. Хотя будет ли быстрым само такое отсечение, можно проверить только на практике.

Теория говорит, что если экстремум единственный, то можно использовать какие-то численные методы (тот же самый градиент или метод случайного поиска), а вот если экстремумов несколько, то только перебором.

Более того, наименьшее значение может и не быть минимумом.


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
PaulWist
Теория говорит, что если экстремум единственный, то можно использовать какие-то численные методы (тот же самый градиент или метод случайного поиска), а вот если экстремумов несколько, то только перебором.
Теория, конечно, говорит, только совсем не это. Не надо все валить в одну кучу. Градиентный метод применяется для нахождения экстремумов функций непрерывных переменных (потому как для дискретных понятие градиента не определено), а перебор - только для дискретных (потому как для непрерывных слишком много перебирать надо).
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Леонид, фокс не сможет комбинировать 2 отдельных индекса в 1 при поиске - это серьёзно мешает реализации алгоритма отсечения "заведомо плохих". Для отсечения же вариант с "прямоугольником" от ry мне кажется более правильным и простым - конечно его надо подправить для практического применения - это если искомая точка лежит далеко "вне" области расположения известных точек (тогда в "прямоугольник" с фиксированными размерами реально может не попасть ни одной точки).
Внутри же "области допустимых решений" скорее всего только перебором и можно искать.
Как "улучшение" алгоритма - определять не "максимальные" расстояния между ближайшими точками по осям, а некие средние (да хоть бы и средние арифметические - т.е. (мах(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 - думаю что "начальное значение" можно эмпирически подбирать...
Потом крутим цикл. Итого:

lnSec = SECONDS()
lnX = 10000
lnY = 600000
lnDelta = 1
SELECT * FROM Points ;
WHERE x BETWEEN m.lnX-m.lnDelta AND m.lnX+m.lnDelta ;
AND Y BETWEEN m.lnY-m.lnDelta AND m.lnY+m.lnDelta ;
INTO CURSOR t1 NOFILTER
DO WHILE _TALLY = 0
Delta = m.Delta*10
SELECT * FROM Points ;
WHERE x BETWEEN m.lnX-m.lnDelta AND m.lnX+m.lnDelta ;
AND Y BETWEEN m.lnY-m.lnDelta AND m.lnY+m.lnDelta ;
INTO CURSOR t1 NOFILTER
ENDDO
? m.Delta, _TALLY
* Далее ищем в курсоре t1 перебором
? SECONDS() - m.lnSec
Нофильтр важен - т.к. иначе фокс тупо наложит фильтр (выражение полностью оптимизируемо, учитывая что для теста DELETED=OFF - мне лень ещё индекс по DELETED() городить было), а значит потом при скане/выборке по сути второй раз придётся отбор делать.


------------------
WBR, Igor




Исправлено 1 раз(а). Последнее : Igor Korolyov, 02.03.10 03:32
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
PaulWist

Сообщений: 14601
Дата регистрации: 01.04.2004
leonid
PaulWist
Теория говорит, что если экстремум единственный, то можно использовать какие-то численные методы (тот же самый градиент или метод случайного поиска), а вот если экстремумов несколько, то только перебором.
Теория, конечно, говорит, только совсем не это. Не надо все валить в одну кучу. Градиентный метод применяется для нахождения экстремумов функций непрерывных переменных (потому как для дискретных понятие градиента не определено), а перебор - только для дискретных (потому как для непрерывных слишком много перебирать надо).

Леонид.

Не понял, при чем здесь непрерывные ф-ии.

Мы говорим о численном решении ф-ии, для которой известны узлы X, Y, те не надо задаваться приращением, оно уже определено в точках эксперимента.


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Владимир Максимов
Сама координатная сетка бесконечна?
Система координат в int
Т.е. +- 2^31
Шаг, соответственно, тоже целое число.
Используется большая часть диапазона.

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


Владимир Максимов
По сути, ты пытаешся сделать ограничение по каждой координате в отдельности, что, в общем случае, некорректно.
Нет, идея не в этом.
Я ищу первую попавшуюся точку, близкую по X,
и сразу отсекаю все заведомо далёкие по Х точки.
Профит получается если первая точка достаточно близка к искомой.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер




Исправлено 2 раз(а). Последнее : Goodwin, 02.03.10 09:25
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
leonid
Родион, идея неплоха, но ошибочка вкралась.
Ага. Косячёк.
Забыл lnMinPointId инициализировать.

Вот так лучше работает:
index on bintoc(coordx)+bintoc(coordy) tag xy
set Near On
seek bintoc(nPointX)
seek bintoc(coordx)+bintoc(nPointY)
lnDistance=d()
lnMinPointId=pointId
seek bintoc(nPointX-lnDistance)
scan rest while coordX<=nPointX+lnDistance for lnDistance>d()
lnDistance=d()
lnMinPointId=pointId
endscan
function d
return sqrt((nPointX-coordX)^2+(nPointY-coordY)^2)


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер




Исправлено 1 раз(а). Последнее : Goodwin, 02.03.10 09:25
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Игорь, браво!
Всё гениальное просто.
Я никак не мог допетрить, как два индекса связать - с составным пытался выкрутиться.

Сейчас буду сравнивать все варианты.

Что касается исходных данных:
точек порядка 50тыс, разбросаны хаотично.
Приемлимое время поиска <10^(-2) сек.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive
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

Цитата:
Мы говорим о численном решении ф-ии, для которой известны узлы X, Y, те не надо задаваться приращением, оно уже определено в точках эксперимента.
Вот именно поэтому тут градиентный метод вообще неприменим, а вовсе не потому, что экстремумов может быть несколько. И все-таки полный перебор не единственно возможный в подобных случаях метод.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14095
Откуда: Москва
Дата регистрации: 02.09.2000
Goodwin
Владимир Максимов
По сути, ты пытаешся сделать ограничение по каждой координате в отдельности, что, в общем случае, некорректно.
Нет, идея не в этом.
Я ищу первую попавшуюся точку, близкую по X,
и сразу отсекаю все заведомо далёкие по Х точки.
Профит получается если первая точка достаточно близка к искомой.

Да не работает это. В принципе. Нельзя выполнять поиск по очереди. Сначала по одной координате, потом по другой. Можно только ОДНОВРЕМЕННО!

Ну, представь, что у тебя две точки

X1 = 2 Y1 = 100
X2 = 50 Y2 = 0

Задаются координаты X3 = 1 Y3 = 1

Ты определишь, что ближайшая точка по X = это первая точка. А вторую точку ты вообще не найдешь!
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
leonid
Игорь, у тебя в методе есть один недостаток. Если, например, при Delta=10 получим _tally=1 и в этом квадрате будет содержаться точка (9, 9), то это вовсе не означает, что на ней будет достигаться минимум, он может достигаться, например, в точке (11, 0). Т.е. нужно сделать еще один шаг, умножив Delta на sqrt(2).
Тогда, как вариант, рассматривать после определения дельта не прямоугольник, а круг с центром в заданной точке, увеличивая радиус при _tally=0.
SELECT * FROM Points ;
WHERE (X-lnX)^2+(Y-lnY)^2<m.lnDelta ;
INTO CURSOR t1 NOFILTER
DO WHILE _TALLY = 0
Delta = m.Delta*2
SELECT * FROM Points ;
WHERE (X-lnX)^2+(Y-lnY)^2<m.lnDelta ;
INTO CURSOR t1 NOFILTER
ENDDO



Исправлено 2 раз(а). Последнее : ry, 02.03.10 12:03
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14095
Откуда: Москва
Дата регистрации: 02.09.2000
Igor Korolyov
Для отсечения же вариант с "прямоугольником" от ry мне кажется более правильным и простым - конечно его надо подправить для практического применения

Я на эти "грабли" тоже радостно налетел. В смысле - идея хорошая, но надо поправить. А идея в корне не верна!

Проблема в том, что расстояние - это радиус. Т.е. описывает окружность. А делать "отсечку" прямоугольником - это заведом потерять некоторые значения.

Ну, представь круг в который вписан прямоугольник. Вершины прямоугольника находятся на линии окружности. Соответственно, всегда есть точки, лежащие внтури круга, но вне прямоугольника.

Как следствие, искать какие-то минимумы/максимумы по каждой координате в отдельности, а потом это все сводить - бессмысленно. Ничего это не даст. Ну, разве что, в каких-то исключительных случаях.

В идеале, хорошо бы перейти в полярные координаты. Но сдвиг начала координат в искомую точку сведет "на нет" весь выигрыш от изменения системы координат.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Итоги (в секундах):
алгоритм/записей 10^7 10^6 10^5
Igor Korolyov 0.050 0.005 0.000
PaulWist 0.164 0.012 0.001
Goodwin 0.111 0.256 0.093
просто scan 17.761 1.800 0.180
Считал на разных таблицах - результаты практически не меняются.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Владимир Максимов
Да не работает это. В принципе.
Очень даже работает.
Если на пальцах: нахожу точку ближайшую по Х
(не оптимальну, но что дали.)
Считаю расстояние до этой точки - D.
И сразу отсекаю все точки,
отстоящие по Х от стартовой более чем на D,
т.к. расстояние до них заведомо больше, чем до уже найденной.
На больших массивах очень даже помогает.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Кстати, про ошибки в алгоритмах: пока они выдают одинаковые результаты

Вот, собсно, весь бенчмарк:

Возможно, подёргав за nDeltaStart и nDeltaStep можно улучшить результаты шаговых алгоритмов.
set Deleted off
_screen.FontSize=7
clear
rand(-1)
create cursor points (PointId i, coordX i, coordY i, ds b)
for lnRow=1 to 10^6
insert into points values (lnRow, rnd(), rnd(), 0)
endfor
replace all ds with sqrt(coordX^2+coordY^2)
index on ds tag ds
index on bintoc(coordx)+bintoc(coordy) tag xy
index on CoordX tag x
index on CoordY tag y
nDeltaStart=1024
nDeltaStep=8
nPointX=rnd()
nPointY=rnd()
nDS=sqrt(nPointX^2+nPointY^2)
for i=1 to 2
scan1()
scan1()
Igor()
Igor()
Goodwin()
Goodwin()
Paul()
Paul()
endfor
function rnd
return 2000000*(rand()-.5)
function Igor
s=seco()
lnDelta=nDeltaStart
do while _tally=0 or lnDelta=nDeltaStart
lnDelta=lnDelta*nDeltaStep
select * from points ;
where CoordX between nPointX-lnDelta and nPointX+lnDelta ;
and CoordY between nPointY-lnDelta and nPointY+lnDelta ;
into cursor OutCrs nofilter
enddo
lnMinDistance=-1
lnMinPointId=0
scan
lnDistance=d()
if lnDistance<lnMinDistance or lnMinPointId=0
lnMinDistance=lnDistance
lnMinPointId=pointId
endif
endscan
use in OutCrs
sele points
?'igor', lnMinPointId, lnMinDistance, seco()-s
endfunc
function Paul
s=seco()
lnDelta=nDeltaStart
lnMinDistance=-1
lnMinPointId=0
set Order To ds
set Near on
do while lnMinPointId=0 or lnMinDistance>lnDelta
seek nDS-lnDelta
scan rest while ds<=nDS+lnDelta
lnDistance=d()
if lnDistance<lnMinDistance or lnMinPointId=0
lnMinDistance=lnDistance
lnMinPointId=pointId
endif
endscan
lnDelta=lnDelta*nDeltaStep
enddo
set Near off
?'paul', lnMinPointId, lnMinDistance, seco()-s
endfunc
function scan1
lnMinDistance=-1
lnMinPointId=0
s=seco()
set Order To
scan
lnDistance=d()
if lnMinDistance=-1 or lnDistance<lnMinDistance
lnMinDistance=lnDistance
lnMinPointId=PointId
endif
endscan
?'scan', lnMinPointId, lnMinDistance, seco()-s
endfunc
function goodwin
s=seco()
set Near On
set Order To xy
seek bintoc(nPointX)
seek bintoc(coordx)+bintoc(nPointY)
lnMinDistance=d()
lnMinPointId=pointId
seek bintoc(nPointX-lnMinDistance)
scan rest while coordX<=nPointX+lnMinDistance
lnDistance=d()
if lnDistance<lnMinDistance
lnMinDistance=lnDistance
lnMinPointId=pointId
endif
endscan
set Near off
?'goodwin', lnMinPointId, lnMinDistance, seco()-s
endfunc
function d
return sqrt((nPointX-coordX)^2+(nPointY-coordY)^2)


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер




Исправлено 1 раз(а). Последнее : Goodwin, 02.03.10 12:10
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
PaulWist

Сообщений: 14601
Дата регистрации: 01.04.2004
leonid

2 PaulWist

Цитата:
Мы говорим о численном решении ф-ии, для которой известны узлы X, Y, те не надо задаваться приращением, оно уже определено в точках эксперимента.
Вот именно поэтому тут градиентный метод вообще неприменим, а вовсе не потому, что экстремумов может быть несколько.

Хорошо, чем численное решение непрерывной ф-ии будет отличаться от решения когда есть дискреты приращения по X и Y, только одним - величиной приращения, по другому не бывает - это численное решение, а не аналитическое.

leonid
И все-таки полный перебор не единственно возможный в подобных случаях метод.

Согласен, не единственно возможный, НО единственный дающий однозначное решение во всей области определения.




------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)




Исправлено 1 раз(а). Последнее : PaulWist, 02.03.10 12:24
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 4 (Гостей: 4)

© 2000-2024 Fox Club 
Яндекс.Метрика