расстояние межу точками

[Профессор Снэйп]

PAV в сообщении #270792 писал(а):

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

Ну там ведь $x_a$ и $y_a$ фиксированы...

Надо тогда, наверное, вместо суммы модулей взять норму, где максимум из двух модулей, а потом не модуль считать, а четыре сравнения ($-\delta < x_a - x_y < \delta$ и то же самое с игреками).

[Xaositect]

PAV в сообщении #270792 писал(а):

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

Нет, для взятия можуля числа в регистре можно применить какую-то хитрую инструкцию и xor вроде.

[Профессор Снэйп]

Xaositect в сообщении #270796 писал(а):

2Профессор Снэйп
Да ну, умножение не настолько медленнее сложения. Данные читать все равно дольше будет.

Возможно. Я не раз писал, что от практики программирования довольно далёк. Высказал мысль в порядке предположения.

Просто представил себя на месте компьютера. Вот я сижу с листком бумаги, выполняя на нём действия "столбиком", а мне подают координаты точек, одну за другой. Я храню текущее значение минимума. И когда мне дают очередную точку, я прежде чем что-то возводить в квадрат, для начала прикину по каждой из координат, а не верно ли, что очередная точка заведомо дальше, чем уже найденная минимальная. Просто для человека, в отличие от компьютера, умножение --- гораздо более трудоёмкая операция, чем сложение/вычитание.

-- Вс дек 13, 2009 03:20:48 --

Xaositect в сообщении #270800 писал(а):

Нет, для взятия модуля числа в регистре можно применить какую-то хитрую инструкцию и $\mathrm{xor}$ вроде.

Меня тоже заинтересовал этот вопрос, который хочется задать присутствующим здесь программистам. Если число целое и хранится в двоично-дополнительном коде, то сравнение с нулём и вычиление модуля происходят моментально. А если с плавающей точкой... просто не знаю.

[Xaositect]

Профессор Снэйп в сообщении #270801 писал(а):

Меня тоже заинтересовал этот вопрос, который хочется задать присутствующим здесь программистам. Если число целое и хранится в двоично-дополнительном коде, то сравнение с нулём и вычиление модуля происходят моментально. А если с плавающей точкой... просто не знаю.

Вот, я нашел для целых чисел ассемблер:

Используется синтаксис ASM

cdq
add eax, edx
xor eax, edx

Для floating point есть специальные инструкции сопроцессора, в том числе FABS для вычисления модуля.


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

[ewert]

Для плавающей точки модуль берётся гораздо быстрее, чем для целого -- надо просто убить знаковый бит. Т.е. просто наложить маску на соотв. байт по AND.

Профессор Снэйп в сообщении #270789 писал(а):

Теперь если евклидово расстояние от $(x_a,y_a)$ до различных точек массива различается больше, чем в $2$ раза, то можно смело использовать норму $\| \cdot \|_1$ и будет найдена нужная точка. А если разброс расстояний просто велик, то можно сначала из огромного массива точек выделить малую часть таких точек, что расстояние от выбранной до каждой из них в норме $\| \cdot \|_1$ не более чем в $2$ раза больше чем расстояние от выбранной до минимальной в той же норме, а потом этой части уже смотреть минимум по евклидовой норме.

Можно; а накладные расходы?...

"Выделить малую часть" -- значат поставить на этих точках флажки. Ну или переписывать"подозрительные" точки в отдельный массив. В любом случае понадобится дополнительная память. Причём при добавлении каждой новой подозрительной точки придётся пересматривать все ранее добавленные, чтобы пересмотреть их статус.

В общем, Ваш метод имеет только одно преимущество -- он сложнее. Но зато гораздо медленнее.

[venco]

Быстрее, чем за O(n) всё равно не получится - надо все точки хотя бы по разу пройти.
Решение в лоб уже O(n). Осталось только уменьшить константу. Во первых, не брать корень - очень медленная операция. Во вторых loop unrolling. В третьих SSE.
Но это уже не математика, а программирование.

-- Сб дек 12, 2009 22:56:21 --

Sasha2 в сообщении #270704 писал(а):

Наверное единственное, что Вам тут поможет (если это можно так назвать), так это только использование равносильности двух неравенств

$(x_1-a)^2+(y_1-b)^2\geq{(x_2-a)^2+(y_2-b)^2}$
и
$(x_1-x_2)(x_1+x_2-2a)+(y_1-y_2)(y_1+y_2-2b)\geq{0}$

Умножений меньше. Хотя, стоит ли оно того, ведь не миллион же точек у Вас.

Умножений столько же. В первом случае одна из величин уже посчитана - текущий минимум. Так что в обоих случаях придётся умножать по два раза, но во втором случае гораздо больше сложений.

[Профессор Снэйп]

ewert в сообщении #270817 писал(а):

"Выделить малую часть" -- значат поставить на этих точках флажки. Ну или переписывать"подозрительные" точки в отдельный массив. В любом случае понадобится дополнительная память. Причём при добавлении каждой новой подозрительной точки придётся пересматривать все ранее добавленные, чтобы пересмотреть их статус.

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

[ewert]

Профессор Снэйп в сообщении #270856 писал(а):

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

Да, насчёт гораздо медленнее я погорячился. Но -- всё равно медленнее. Вы на каждом шаге заменяете одно умножение на одно взятие модуля, выгода от чего сомнительна. Но при этом добавляете от одной до трёх весьма не безобидных операции: одну операцию сравнения плюс иногда ещё одно сравнение и одно умножение на два. А если не повезёт с отбраковкой ни в ту, ни в другую сторону, то объём вычислений (на этом шаге) и вовсе удваивоится.

Причём "иногда" -- это если точки разбросаны более-менее равномерно. А если в кольце с не слишком различающимися радиусами -- то довольно часто. В пределе: если почти на окружности -- так и вовсе почти постоянно.

[Sasha2]

А вообще я так понял, что если каждую точку $(x_i, y_i)$ обратить в точку $(x_i, y_i, i)$ то все равно нет такой формулы, при помощи которой можно выделить тот самый индекс $i$, который дает минимум (или максимум).