алгоритмы поиска.

[Vlad Drakula]

вот столкнулся с проблеммой поиска.

у меня есть набор точек ~(10000 - 1000000)
задается точка (А) и надо найти все точки расстояние между которыми и А > r.

точка задается тремя координатами с плавающей точкой.

как быстрее всего это вожно сделать.
учитывая то такой поиск надо производить примерно 10,000,000 раз?

[bilytur]

Имхо надо их отсортировать по расстоянию от А.
А дальше просто.
Правда проблемы поиска плавно переходят в проблему сортировки. На крайняк qsort неплох.

[Greyman]

bilytur
Какой смысл их сортировать? Этих же данных изначально нет (расстояний), так что перед сортировкой их все равно надо вычислять. При вычислении расстояния (корень суммы квадратов разностей координат) и сравнивается с R, и в случае удовлетворения условия точка помечается как удовлетворяющая требованиям (добавлением в выделенный массив либо установкой флага в массиве, описывающем точки). Сортировка бы имела смысл, если бы менялась не точка А, а ограничение расстояния - R.


Добавлено:

Vlad Drakula
А у тебя точки произвольно располагаются, или лежат на поверхности некоторой геометрической фигуры (например - шар). Во втором случае можно ускорить поиск проведением предварительного преобразования координат, иначе особых методов ускорения поиска ИМХО нет, тут уже чисто ворос кодирования.

[vasketsov]

Vlad Drakula
Здесь можно произвести следующую оптимизацию.

Предположим, что тестируемая точка - (X,Y), точка А - это (A,B).

Условие большего расстояния (исключая случай r < 0) удобней записывать в виде (X-A)*(X-A) + (Y-B)*(Y-B) > r*r, то есть, без корней и степеней, так быстрее будет работать.

Сейчас неплохо бы выяснить, зачем такое количество измерений. Судя по всему, какие-то (либо все) параметры меняются. Если существуют неизменные параметры (например, все исходные точки и r постоянны, меняется только A и B), то надо заранее вычислить неизменную часть (в примере - каждой точке будет сопоставлено число r*r - X*X - Y*Y, как его потом использовать, надеюсь, ясно).

Даже если ни одной постоянной величины нет, отчаиваться тоже рано. В случае нашего пространства можно написать небольшую проверочку ДО проверки указанного неравенства, которая может позволить вообще не вычислять произведений: если |X-A| > r, то дальше можно уже не проверять, аналогично для другой координаты.

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


Добавлено:

Естественно, если есть возможность задать систему координат, адекватную задаче, надо это делать обязательно, тогда формула для проверки изменится, но основные принципы останутся теми же, то есть 1) не считать одно и то же, 2) грубо упростить проверку.

[Vlad Drakula]

vasketsov
во первых у меня три координаты
во вторых все написанное я уже применил
в третьих асм не применим, прога должна быть партируемой!

вот пришла идея, а что есть выбирать точки для скавнания только из промежутка между двумя сферами, то это достаточно быстро получится, так первая реальзация привела к снижкнию затрат от 2100с до 645с. причем самый тупой способ!

может у кого еще какие идеи есть?

Добавлено:

bilytur
qsort - не работает под VS2003, он работает но присылает указатель на пустое место!

Greyman
все точки действительно лежат на геометрических фигурах, но вот только на каждой фигуре их очень много.

может тогда кто скажет алгоритм сортировки, но не деревом?

[bilytur]

Если Входная точка А меняется то любая сортировка будет работать медленнее даже простого линейного поиска Greyman, надо признать прав.

Могу предложить следующее. Если памяти хватает создать 3 индекса на каждую координату. (Индексы упорядочены)
Бинарным поиском (очень быстрым) отсечь явно не нужные точки лежащие за описанным кубом. И принять все во вписанном кубе.
При наличии индексов это пройдет практически моментально. А вот дальше остается небольшой кубический слой.
И в нем уже вести поиск.

[Greyman]

Vlad Drakula
Т.е. фигура не одна а несколько? Тогда смысла в смене системы координат ИМХО нет. Вот если бы все точки лежали на поверхности одной фигуры, тогда можно было бы вместо 3-х использовать только 2-е координаты.
* * Кстати, идея bilytur мне очень понравилась. При этом отсекать можно не только внешнее пространство куба (>r), но внутренний куб (<r*cos(пи/4)^2). Дальше распылятся наверно уже не имеет смысла, хотя в случае, если в оставшемся диапазоне все равно много точек, то можно провести проверку с использованием округленных целочисленных координат (насколько я понял они именно они могут использоваться как раз в качестве упомянутых индексов). Тогда потом останется уже проверить в настоящих дробных координах точки, лежащие в спорной ступенчатой сфере (толщина сферы при этом равна единице измерения координат).

[Vlad Drakula]

bilytur
экспериметр показал что с момощью сортировки одного индекса я снизил время до 36с ( напомню в начала было 2100с ), но это снишком медленно.

если знаешь алгоритм как производить выборку по дрем интексам то буду очень презначател если ты им поделишься.

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

Greyman
округление не допустимо, и так мне нехватает пары порядков точноси!

в данный момент я использую два индекса - расстояние до (0, 0, 0) и рассточние до (100, 100, 100).

[bilytur]

Vlad Drakula
Готового алгоритма у меня нет. К тому-же может это и не быть столь эффективно.
Все зависит от конкретных параметров. Соотношения A, r, масштабы пространства.
Если много точек попадают в кубический слой то выигрыш явно будет не большим.

[Greyman]

Vlad Drakula
округление не допустимо, и так мне нехватает пары порядков точноси!
Так я же и не говорил об округлении. Я говорил об скоростной выгоде при использовании целочисленной арифметики. Применив которую можно прошерстить большинство имеющихся точек, а оставшиеся уже проверять по дробным координатам. Перевод в целочисленную форму не значит просто округлить, если требуется большая точность после запятой, можно и увеличить все числа на несколько порядков (на тысячу предварительно умножаешь, например), тем самым ты просто уменьшаещь размерность единицы измерения, главное не забыть тогда и r на столько же порядков увеличить. ИМХО, если сделать второй массив для целочисленных координат и сделать предварительные преобразования для всех точек, то поиск заметно ускорится. Потом с дробной арифметикой останется проверять только точки, лежащие в упомянутой ступенчатой сфере. Если точек очень много, то выгода в скорости д/б сильно заметна.