Оптимизация функции вычисления расстояния

Question

В моем коде я должен сделать много расчетов расстояний между парами значений lat/long.

код выглядит следующим образом:

double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad)); 

(например, lat2rad широта преобразуется в радианах).

Я определил эту функцию как узкое место в производительности моего приложения. Есть ли способ улучшить это?

(Я не могу использовать справочные таблицы, так как координаты меняются). Я также посмотрел на this question, где предлагается схема поиска, такая как сетка, что может быть возможно.

Спасибо за ваше время! ;-)

Answer 1

Если ваша цель ранжировать (сравнивать) расстояния, то приближения (sin и cos табличного поиска) может резко сократить свой объем вычислений, необходимых для (реализации быстро отклонять.)

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

E.g. используя таблицы поиска с 1000 выборками (то есть sin и cos с выборочной выборкой каждые 2*pi/1000), неопределенность поиска составляет не более 0,006284. Используя uncertainty calculation для параметра ACos, суммарная неопределенность также будет пороговой неопределенностью, будет не более 0,018731.

Таким образом, если оценки Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) с помощью sin и cos таблицы поиска для двух координат множество пар (расстояния) дает определенный рейтинг (один расстояние появляется больше, чем другие на основе аппроксимации), и модуль разницу является больше, чем порог выше, то справедливо приближение. В противном случае приступайте к фактическому тригонометрическому расчету.

Answer 2

Насколько точны ваши значения?

Если вы немного округлите свои значения, вы можете сохранить результат всех поисков и проверить, использовались ли они для каждого расчета?

Answer 3

Переключение на таблицы поиска для sin/cos/acos. Будет быстрее, есть много библиотек с фиксированной точкой c/C++, которые также включают их.

Вот код от кого-то еще на Memoization. Что может работать, если используемые фактические значения более сгруппированы.

Вот вопрос на Fixed Point.

Answer 4

Будет ли работать алгоритм CORDIC (относительно скорости/точности)?

Answer 5

Ну, так как lat и lon являются garenteed, чтобы быть в пределах определенного диапазона, вы можете попробовать использовать некоторую форму таблицы поиска для вызовов Math. *. Скажем, Dictionary<double,double>

Answer 6

Используя вдохновение от @Brann, я думаю, что вы можете немного уменьшить вычисление (предупреждая его о том, что я сделал какое-либо из этого, и это нужно будет проверить). Своего рода поиска из предвычисленных значений, вероятно, самый быстрый, хотя

У вас есть:

1: АКОС (согрешающего SIN B + COS Категория обслуживания B COS (AB))

но 2: COS (AB) = SIN грех B + COS Категория обслуживания B

, который переписывается в виде 3: SIN A SIN B = COS (AB) - COS Категория обслуживания B

заменить SIN A SIN B в 1. вы имеете:

4: ACOS (COS (AB) - COS A COS B + COS A COS B COS (AB))

Вы предварительно вычисляете X = COS (AB) и Y = COS A COS B, и вы ставите значения в 4

дать:

ACos (XY + XY)

4 тригонометрические вычисления вместо 6!

Answer 7

Что такое шея бутылки? Являются ли вызовы функции синус/косинус или вызов арксина?

Если синус/косинус звонки медленно, вы можете использовать следующую теорему, чтобы предотвратить так много звонков:

1 = sin(x)^2 + cos(x)^2 
cos(x) = sqrt(1 - sin(x)^2) 

Но мне нравится идея отображения так, что вам не придется пересчитывать значения, которые вы» уже вычислен. Хотя будьте осторожны, так как карта может стать очень большой очень быстро.

Answer 8

Я бы сказал, что вы можете пересмотреть, как вы обнаружили, что функция является узким местом. (IE вы профилировали заявку?)

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

Тем не менее это то, что нужно учитывать.

Answer 9

Изменить способ хранить длинные/Lat:

struct LongLat 
{ 
    float 
    long, 
    lat, 
    x,y,z; 
} 

При создании длинных/лат, а также вычислить (х, у, г) 3D точку, которая представляет эквивалентную позицию на единичной сфере с центром в точке Происхождение.

Теперь, чтобы определить, является ли точка B ближе к точке А, чем точка С, сделайте следующее:

// is B nearer to A than C? 
bool IsNearer (LongLat A, LongLat B, LongLat C) 
{ 
    return (A.x * B.x + A.y * B.y + A.z * B.z) < (A.x * C.x + A.y * C.y + A.z * C.z); 
} 

и получить расстояние между двумя точками:

float Distance (LongLat A, LongLat B) 
{ 
    // radius is the size of sphere your mapping long/lats onto 
    return radius * acos (A.x * B.x + A.y * B.y + A.z * B.z); 
} 

Вы можете удалить термин «радиус», эффективно нормализуя расстояния.

Answer 10

Как заметил кто-то еще, вы уверены, что это ваше узкое место?

Я провел некоторое тестирование производительности аналогичного приложения, которое я создаю, когда я называю простой метод, чтобы вернуть расстояние между двумя точками, используя стандартный триггер. 20 000 звонков на него выталкивают его прямо вверху профилирующего вывода, но я не могу сделать это быстрее ... Это просто сдвиг вызовов.

В этом случае мне нужно уменьшить # звонков на него ... Не то, чтобы это было узким местом.

Answer 11

Я использую другой алгоритм для вычисления расстояния между двумя положениями lati/longi, он может быть более легким, чем ваш, поскольку он выполняет только 1 вызов Cos и 1 вызов Sqrt.

public static double GetDistanceBetweenTwoPos(double lat1, double long1, double lat2, double long2) 
{ 
    double distance = 0; 
    double x = 0; 
    double y = 0; 

    x = 69.1 * (lat1 - lat2); 
    y = 69.1 * (long1 - long2) * System.Math.Cos(lat2/57.3); 

    //calculation base : Miles 
    distance = System.Math.Sqrt(x * x + y * y); 

    //Distance calculated in Kilometres 
    return distance * 1.609; 
} 

Answer 12

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

вместо

 
double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad)); 

есть:

 
double result = Math.Acos(lat2rad.sin * lat1rad.sin 
+ lat2rad.cos * lat1rad.cos * (lon2rad.cos * lon1rad.cos + lon1rad.sin * lon2rad.sin)); 

и я думаю, что это та же формула, как кто-то писал, потому что часть уравнения исчезнет, ​​когда вы расширяете скобки :)