거리 계산 기능의 최적화
https://stackoverflow.com/questions/615206
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
내 코드에서는 LAT/긴 값 쌍 사이에서 많은 거리 계산을 수행해야합니다.
코드는 다음과 같습니다.
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 두 개의 좌표 세트 쌍 (거리)에 대한 조회 테이블은 특정 순위를 산출합니다 (한 거리는 근사치에 따라 다른 거리보다 더 크게 나타납니다). 그렇지 않으면 실제 삼각 계산을 진행하십시오.
다른 팁
할 것입니다 고문 알고리즘은 귀하에게 작동합니다 (속도/정확도와 관련하여)?
@brann의 영감을 사용하여 계산을 조금 줄일 수 있다고 생각합니다 (이 작업을 수행 한 이후로 오랜 시간을 경고하면 확인해야합니다). 미리 계산 된 값의 일종의 조회는 아마도 가장 빠릅니다.
당신은 :
1 : acos (죄 A sin b + cos a cos b cos (ab))
그러나 2 : cos (ab) = 죄 A sin b + cos a cos b
3 : sin a sin b = cos (ab) - cos a cos b로 다시 작성됩니다.
1의 죄 b를 대체하십시오. 당신은 다음과 같습니다.
4 : ACOS (COS (AB) -COS A COS B + COS A COS B COS (AB))
당신은 x = cos (ab)와 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) 3D 포인트를 계산합니다.
이제 점 B 지점이 지점 C보다 지점 A에 더 가깝는지 확인하려면 다음을 수행하십시오.
// 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);
}
'반경'항을 제거하여 거리를 효과적으로 정규화 할 수 있습니다.
병 목은 무엇입니까? 사인/코사인 기능은 호출 또는 아크 신 호출입니까?
사인/코사인 호출이 느리면 다음 정리를 사용하여 많은 통화를 방지 할 수 있습니다.
1 = sin(x)^2 + cos(x)^2
cos(x) = sqrt(1 - sin(x)^2)
그러나 나는 당신이 이미 계산 한 값을 다시 작성할 필요가 없도록 매핑 아이디어를 좋아합니다. 지도가 매우 빠르게 커질 수 있으므로주의하십시오.
값이 얼마나 정확한가?
값을 조금 반올림하면 모든 조회의 결과를 저장하고 각 계산에 사용되었는지 확인할 수 있습니까?
글쎄, LAT와 LON은 특정 범위 내에 있어야하므로 수학을위한 조회 테이블의 형태를 사용해 볼 수 있습니다.* 메소드 호출. a Dictionary<double,double>
나는 당신이 그 기능이 병목 현상이라는 것을 어떻게 찾았는지 재검토하고 싶을 수도 있다고 주장합니다. (즉, 응용 프로그램을 프로필 했습니까?)
나에게 방정식은 매우 가벼워 보인다 그렇지 않아야합니다 문제가 발생합니다.물론, 나는 당신의 응용 프로그램을 모르고 당신은 당신이 이러한 계산을 많이한다고 말합니다.
그럼에도 불구하고 그것은 고려해야 할 것입니다.
다른 사람이 지적했듯이 이것이 당신의 병목 현상이라고 확신합니까?
표준 트리그를 사용하여 두 지점 사이의 거리를 반환하는 간단한 방법을 호출하는 비슷한 응용 프로그램에 대한 성능 테스트를 수행했습니다. 20,000 통화는 프로파일 링 출력의 맨 위에 바로 밀어 넣지 만 더 빨리 만들 수있는 방법은 없습니다.
이 경우 # 호출을 줄여야합니다. 이것이 병목 현상이 아닙니다.
나는 2 개의 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;
}
누군가가 이미 MEMOISATION을 언급했으며 이것은 약간 비슷합니다. 같은 지점을 다른 많은 지점과 비교하면 해당 방정식의 일부를 사전 계산하는 것이 좋습니다.
대신에
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));
그리고 나는 그것이 다른 사람이 게시 한 것과 같은 공식이라고 생각합니다. 왜냐하면 당신이 괄호를 확장 할 때 방정식의 일부가 사라질 것이기 때문입니다 :)
