Евклидово расстояние - оптимизация и литья


Я пытаюсь оптимизировать простую функцию Евклидово расстояние в C. Это для библиотеки DLL, и вычисляет расстояния от одной точки ко многим. У меня есть:

Версия 1:

int CalcDistance (int y1, int x1, int *y2, int *x2, int nb , int *distances)
{
    double dx,dy = 0;

    for (int i = 0;i<nb;i++)
    {
        dx = x2[i] - x1;
        dy = y2[i] - y1;

        distances[i]=(int)sqrt((dx*dx)+(dy*dy));
    }

    return nb;
}

Версия 2:

int CalcDistance (int y1, int x1, int *y2, int *x2, int nb , int *distance)
{
    int dx,dy =0;

    for (int i = 0;i<nb;i++)
    {
        dx = x2[i] - x1;
        dy = y2[i] - y1;

        distances[i]=(int)sqrt((double)(dx*dx)+(dy*dy));
    }

    return nb;
}

По сути, мне не нужны дополнительные высокой точности, поэтому я экономлю на ИНЦ, не парный. Для моего конкретного случая использования, окончательное расстояние будет не больше, чем тип int (int32) В может держать.

Я был поражен, как медленная версия 2 была. Я понял, что в версии 1 расчета и бы неявно приведен к двойной дважды, в то время как в версии 2 я просто явно литье один раз. Что происходит? И в конце концов, что может быть еще быстрее?

(И я попробовал _hypot, который был как ни странно самый медленный из всех...)



535
4
задан 25 мая 2011 в 09:05 Источник Поделиться
Комментарии
4 ответа

dstances[i]=(int)sqrt((dx*dx)+(dy*dy));

Это только преобразует один раз двойной. он будет делать все математические стиле целое число, а затем преобразовать его в двойной раз перед вызовом корень.

    distances[i]=(int)sqrt((double)(dx*dx)+(dy*dy));

Это фактически то же, что:

    distances[i]=(int)sqrt(  ((double)(dx*dx))   + (dy*dy));    

не:

    distances[i]=(int)sqrt((double)(  (dx*dx)) + (dy*dy)  );    

В результате преобразования ДХ*ДХ в два раза, затем преобразовать ды*ды, чтобы затем дважды добавить их и пройти его до sqrt.

В современных ЭВМ числа с плавающей точкой очень быстро, в некоторых случаях даже быстрее, чем целые. Как результат, вы же значительно лучше использовать двойное запрещено, а затем преобразования из целых чисел в парном разряде и снова. Преобразование между int и Double-это дорого, так что избежать его на самом деле может быть вашим лучшим выбором.

Обычный прием, используемый в алгоритмах, которые должны работать с расстояния переработать алгоритм, так что вы можете использовать квадрату расстояния. Таким образом, вы можете избежать дорогостоящих корень звонка. Это работает, потому что Х*Х < г*г мкФ х < г. Будьте осторожны, или вы не можете сделать это зависит от того, что вы делаете с такого расстояния.

6
ответ дан 25 мая 2011 в 11:05 Источник Поделиться

Даже если результат укладывается в int, ДХ*ДХ может переполниться. Лучше бросать перед умножением

sqrt((double)dx*dx+(double)dy*dy); 

4
ответ дан 26 мая 2011 в 01:05 Источник Поделиться

В зависимости от X,Y значения, вы могли бы рассмотреть с помощью поплавков, а не удваивается. Это должно помочь немного.

1
ответ дан 27 мая 2011 в 09:05 Источник Поделиться

Если вам действительно нужно расстояние, я понятия не имею, но если вам просто надо сравнить расстояния, можно опустить функция sqrt-функция, которая oftten довольно дорогостоящим. Конечно, вы должны переименовать функцию для этой цели.

0
ответ дан 27 мая 2011 в 02:05 Источник Поделиться