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

StackOverflow https://stackoverflow.com/questions/615206

  •  03-07-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

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

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

Это было полезно?

Решение

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

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

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

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

Другие советы

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

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

У вас есть:

1: ACOS (SIN A SIN B + COS A COS B COS (A-B))

но 2: COS (A-B) = SIN A SIN B + COS A COS B

который переписывается как 3: SIN A SIN B = COS (A-B) - COS A COS B

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

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

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

дать:

ACOS (X - Y + XY)

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

Измените способ хранения long / lat: 

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

При создании long / lat также рассчитайте трехмерную точку (x, y, z), которая представляет эквивалентную позицию на единичной сфере с центром в начале координат.

Теперь, чтобы определить, находится ли точка B ближе к точке A, чем точка C, сделайте следующее: 

// 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);
}

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

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

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

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

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

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

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

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

Насколько точными должны быть значения?

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

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

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

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

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

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

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

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

Я использую другой алгоритм для расчета расстояния между двумя позициями в латах / лонгах, он может быть легче вашего, поскольку он выполняет только 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;
}

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

вместо

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));

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top