Tối ưu hóa chức năng tính toán khoảng cách

Question

Trong mã của tôi, tôi phải thực hiện rất nhiều phép tính khoảng cách giữa các cặp giá trị lat/long.

mã trông như thế này:

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

(lat2rad ví dụ là vĩ độ chuyển đổi sang radian).

Tôi đã xác định chức năng này là nút cổ chai hiệu suất của ứng dụng của tôi. Có cách nào để cải thiện điều này không?

(Tôi không thể sử dụng bảng tra cứu vì các tọa độ khác nhau). Tôi cũng đã xem xét this question nơi đề xuất một sơ đồ tra cứu như một lưới, có thể là một khả năng.

Cảm ơn bạn đã dành thời gian! ;-)

Answer 1

Nếu mục tiêu của bạn là để xếp hạng (so sánh) khoảng cách, sau đó xấp xỉ (sin và cos bảng tra cứu) có thể làm giảm đáng kể số tiền của bạn tính toán yêu cầu (thực hiện nhanh chóng từ chối.)

Mục tiêu của bạn là chỉ tiến hành tính toán lượng giác thực tế nếu chênh lệch giữa khoảng cách gần đúng (được xếp hạng hoặc so sánh) giảm xuống dưới một ngưỡng nhất định.

Ví dụ: sử dụng các bảng tra cứu với 1000 mẫu (ví dụ: sin và cos lấy mẫu mỗi 2*pi/1000), độ không đảm bảo tra cứu tối đa là 0,006284. Sử dụng uncertainty calculation cho tham số là ACos, độ không đảm bảo tích lũy, cũng là độ không đảm bảo ngưỡng, sẽ có nhiều nhất là 0,018731.

Vì vậy, nếu đánh giá Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) sử dụng sin và cos bảng tra cứu cho hai cặp phối hợp-set (khoảng cách) mang lại một thứ hạng nhất định (một khoảng cách dường như lớn hơn khác dựa trên xấp xỉ), và mô đun của sự khác biệt lớn hơn ngưỡng trên, khi đó xấp xỉ là hợp lệ. Nếu không thì hãy tiến hành tính toán lượng giác thực tế.

Answer 2

Bạn cần giá trị chính xác đến mức nào?

Nếu bạn làm tròn các giá trị của mình một chút thì bạn có thể lưu trữ kết quả của tất cả tra cứu và kiểm tra xem có thay thế được sử dụng cho mỗi phép tính không?

Answer 3

Chuyển sang bảng tra cứu cho sin/cos/acos. Sẽ nhanh hơn, có rất nhiều thư viện điểm cố định c/C++ cũng bao gồm các thư viện đó.

Đây là mã của người khác trên Memoization. Điều này có thể hoạt động nếu các giá trị thực tế được sử dụng được nhóm nhiều hơn.

Đây là câu hỏi SO trên Fixed Point.

Answer 4

Thuật toán CORDIC có hoạt động cho bạn (liên quan đến tốc độ/độ chính xác) không?

Answer 5

Vâng, vì lat và lon được thu hút trong một phạm vi nhất định, bạn có thể thử sử dụng một số dạng bảng tra cứu cho bạn gọi phương thức Math. *. Giả sử, một Dictionary<double,double>

Answer 6

Sử dụng cảm hứng từ @Brann Tôi nghĩ rằng bạn có thể giảm tính toán một chút (Cảnh báo một thời gian dài kể từ khi tôi thực hiện bất kỳ điều này và nó sẽ cần được xác minh). Một số loại tra cứu các giá trị precalculated lẽ là nhanh nhất mặc dù

Bạn có:

1: ACOS (SIN Một SIN B + COS Một COS B COS (AB))

nhưng 2: COS (AB) = SIN SIN Một B + COS COS Một B

được viết lại như 3: SIN SIN Một B = COS (AB) - COS COS Một B

thay SIN SIN Một B trong 1. bạn có:

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

Bạn tính trước X = COS (AB) và Y = COS A COS B và bạn đặt các giá trị thành 4

để cung cấp cho:

ACOS (XY + XY)

tính toán

4 trig thay vì 6!

Answer 7

Cổ chai là gì? Các cuộc gọi hàm sine/cosine hay gọi hàm arcsine?

Nếu sin/cuộc gọi cosin của bạn chậm, bạn có thể sử dụng định lý sau đây để ngăn ngừa rất nhiều cuộc gọi:

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

Nhưng tôi thích ý tưởng lập bản đồ để bạn không cần phải recompute giá trị bạn' đã được tính toán. Mặc dù cẩn thận vì bản đồ có thể rất lớn rất nhanh.

Answer 8

Tôi cho rằng bạn có thể muốn kiểm tra lại cách bạn nhận thấy chức năng đó là nút cổ chai. (IE bạn có hồ sơ ứng dụng?)

Phương trình với tôi có vẻ rất nhẹ cân và không nên gây ra bất kỳ sự cố nào. Đã cấp, tôi không biết ứng dụng của bạn và bạn nói rằng bạn thực hiện rất nhiều tính toán này.

Tuy nhiên, đó là điều cần cân nhắc.

Answer 9

Thay đổi cách bạn lưu trữ dài/lat:

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

Khi tạo một chặng đường dài/lat, cũng tính toán (x, y, z) điểm 3D đại diện cho vị trí tương đương trên một quả cầu đơn vị tập trung ở nguồn gốc.

Bây giờ, để xác định xem điểm B là gần với điểm A so với điểm C, làm như sau:

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

và để có được khoảng cách giữa hai điểm:

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

Bạn có thể loại bỏ thuật ngữ 'bán kính', hiệu quả bình thường hóa khoảng cách.

Answer 10

Khi người khác chỉ ra, bạn có chắc đây là nút cổ chai của bạn không?

Tôi đã thực hiện một số thử nghiệm hiệu suất của một ứng dụng tương tự Tôi đang xây dựng nơi tôi gọi một phương pháp đơn giản để trả về khoảng cách giữa hai điểm sử dụng tiêu chuẩn trig. 20.000 cuộc gọi đến nó đẩy nó ngay trên đầu của đầu ra profiling, nhưng không có cách nào tôi có thể làm cho nó nhanh hơn ... Nó chỉ là cắt # số cuộc gọi.

Trong trường hợp này, tôi cần phải giảm # cuộc gọi đến ... Không phải đây là nút cổ chai.

Answer 11

Tôi sử dụng thuật toán khác để tính khoảng cách giữa 2 vị trí lati/longi, nó có thể nhẹ hơn của bạn vì nó chỉ thực hiện 1 cuộc gọi Cos và 1 cuộc gọi 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

ai đó đã đề cập đến memoisation và điều này hơi giống một chút. nếu bạn so sánh cùng một điểm với nhiều điểm khác thì tốt hơn là tính toán trước các phần của phương trình đó.

thay vì

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

có:

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

và tôi nghĩ rằng đó là công thức giống như ai đó đã đăng tải vì một phần của phương trình sẽ biến mất khi bạn mở rộng khung :)