Optimización de una función de cálculo de distancia.

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

  •  03-07-2019
  •  | 
  •  

Pregunta

En mi código tengo que hacer muchos cálculos de distancia entre pares de valores de latitud/longitud.

el código se ve así:

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

(lat2rad p.ej.es la latitud convertida a radianes).

He identificado esta función como el cuello de botella en el rendimiento de mi aplicación.¿Hay alguna manera de mejorar esto?

(No puedo usar tablas de búsqueda porque las coordenadas varían).yo también he mirado esta pregunta donde se sugiere un esquema de búsqueda como una cuadrícula, lo que podría ser una posibilidad.

¡Gracias por tu tiempo!;-)

¿Fue útil?

Solución

Si tu objetivo es clasificar (comparar) distancias, entonces aproximaciones (sin y cos búsquedas de tablas) podría reducir drásticamente la cantidad de cálculos necesarios (implementar rechazo rápido.)

Su objetivo es proceder únicamente con el cálculo trigonométrico real si la diferencia entre las distancias aproximadas (que se clasificarán o compararán) cae por debajo de un cierto umbral.

P.ej.utilizando tablas de búsqueda con 1000 muestras (es decir, sin y cos muestreado cada 2*pi/1000), la incertidumbre de búsqueda es como máximo 0,006284.Usando cálculo de incertidumbre para que el parámetro ACos, la incertidumbre acumulada, que también será la incertidumbre umbral, será como máximo 0,018731.

Entonces, si se evalúa Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) usando sin y cos Las tablas de búsqueda para dos pares de conjuntos de coordenadas (distancias) arrojan una clasificación determinada (una distancia parece mayor que la otra según la aproximación) y el módulo de diferencia es mayor que el umbral anterior, entonces la aproximación es válida.De lo contrario, proceda con el cálculo trigonométrico real.

Otros consejos

¿Funcionaría el algoritmo CORDIC para usted (en cuanto a velocidad / precisión)?

Usando la inspiración de @Brann, creo que puedes reducir un poco el cálculo (Advertencia, hace mucho tiempo que no hice nada de esto y será necesario verificarlo). Sin embargo, algún tipo de búsqueda de valores precalculados probablemente sea el más rápido

Tienes:

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

pero 2: COS (A-B) = SIN A SIN B + COS A COS B

que se reescribe como 3: SIN A SIN B = COS (A-B) - COS A COS B

reemplaza SIN A SIN B en 1. tienes:

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

Precalcula X = COS (A-B) e Y = COS A COS B y pone los valores en 4

para dar:

ACOS (X - Y + XY)

¡4 cálculos trigonométricos en lugar de 6!

Cambie la forma en que almacena long / lat: 

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

Al crear un largo / lat, también calcule el punto 3D (x, y, z) que representa la posición equivalente en una esfera unitaria centrada en el origen.

Ahora, para determinar si el punto B está más cerca del punto A que del punto C, haga lo siguiente: 

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

y para obtener la distancia entre dos puntos: 

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

Puede eliminar el término 'radio', normalizando efectivamente las distancias.

Cambio a tablas de búsqueda para sin / cos / acos. Será más rápido, hay muchas bibliotecas de punto fijo c / c ++ que también incluyen esas.

Aquí hay un código de otra persona en Memoization . Lo que podría funcionar si los valores reales utilizados están más agrupados.

Aquí hay una pregunta SO sobre Punto fijo .

¿Qué es el cuello de la botella? ¿La función seno / coseno llama o la llamada arcoseno?

Si sus llamadas seno / coseno son lentas, puede usar el siguiente teorema para evitar tantas llamadas: 

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

Pero me gusta la idea de mapeo para que no tenga que volver a calcular los valores que ya ha calculado. Aunque tenga cuidado ya que el mapa podría hacerse muy grande muy rápidamente.

¿Qué tan exactos necesita que sean los valores?

Si redondea un poco sus valores, ¿podría almacenar el resultado de todas las búsquedas y verificar si se han utilizado para cada cálculo?

Bueno, dado que se garantiza que lat y long están dentro de un cierto rango, podría intentar usar alguna forma de tabla de búsqueda para sus llamadas al método Math. *. Digamos, un Dictionary<double,double>

Yo diría que es posible que desee volver a examinar cómo descubrió que esa función es el cuello de botella. (¿IE perfiló la aplicación?)

La ecuación me parece muy ligera y no debería causar ningún problema. De acuerdo, no conozco tu aplicación y dices que haces muchos de estos cálculos.

Sin embargo, es algo a considerar.

Como alguien más señaló, ¿estás seguro de que este es tu cuello de botella?

He realizado algunas pruebas de rendimiento de una aplicación similar que estoy construyendo, donde llamo a un método simple para devolver una distancia entre dos puntos usando trigonométrico estándar. 20,000 llamadas lo colocan justo en la parte superior de la salida de creación de perfiles, sin embargo, no hay forma de que pueda hacerlo más rápido ... Es solo el número de corte de llamadas.

En este caso, necesito reducir las # llamadas a él ... No es que este sea el cuello de botella.

Utilizo un algoritmo diferente para calcular la distancia entre 2 posiciones lati / longi, podría ser más ligero que el tuyo ya que solo hace 1 llamada Cos y 1 llamada 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;
}

alguien ya ha mencionado la memorización y esto es un poco similar. si compara el mismo punto con muchos otros puntos, entonces es mejor calcular previamente partes de esa ecuación.

en lugar de 

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

tener: 

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

y creo que esa es la misma fórmula que alguien más ha publicado porque parte de la ecuación desaparecerá cuando expanda los corchetes :)

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top