您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發基礎

地理空間距離計算優化實戰:把 140ms 壓到 20ms 的三個招數

編輯:iOS 開發基礎

一、問題從哪裡來

打開美團 App,無論篩選團購還是篩選商家,預設排序都是「離我最近」或「智能排序」。

兩者都離不開一件事:計算用戶位置與每一個團購單或商家的距離(智能排序中,距離是打分的重要參數)。以商家篩選為例,北京地區有 5~6 萬個 POI(本文把商家統稱為 POI)。當用戶進入商家頁,請求「北京全城 + 所有品類 + 離我最近/智能排序」時,篩選服務必須把用戶位置與全城所有 POI 的距離算上一遍。

這種大規模距離計算極度吃資源。實測顯示,5 萬個點算一輪需要 7ms,資料量漲到 100 萬時就變成 140 多 ms。隨著資料快速膨脹,篩選服務的效能前景實在令人擔心。

如何優化距離計算、進而提升速度並降低 CPU 使用率,已經是當務之急。美團移動後台團購組在這個方向上做了一些探索,下文分四部分展開:地理空間距離計算原理、Lucene 採用的公式、優化方案、實際落地。

二、地理空間距離計算原理

算法有許多種,我們使用的可分兩類:一是球面模型,把地球當成標準球體,球面上兩點的最短路徑即大圓弧長,通用性強,是我們服務端的主力;二是橢球模型,最貼近真實地球、精度最高,但計算複雜,目前僅客戶端在用——而我們的業務場景對精度其實沒那麼苛求。

下面重點說明最常用的球面模型公式,推導只需高中數學即可。

經緯度距離計算示意圖

把地球視為圓球,設地表上有 A(ja,wa)、B(jb,wb) 兩點(ja、jb 為經度,wa、wb 為緯度)。A、B 的球面距離就是 AB 弧長,而 AB 弧長 = R × ∠AOB(O 為球心,R 為地球半徑,約 6367000 公尺)。要拿到 ∠AOB,可以先求出三角形最大邊 AB 的長度,再用餘弦定理反推夾角。

AB 怎麼求?

1)依經緯度與地球半徑 R,把 A、B 的經緯度轉換成球體三維座標;

2)由兩點的三維座標算出 AB 長度;

3)用餘弦定理求出 ∠AOB;

4)AB 弧長 = R × ∠AOB。

三、Lucene 用的距離算法

美團團購 App 後台以 Lucene 篩選團購單與商家,Lucene 透過 spatial4j 工具包計算地理空間距離。spatial4j 提供了多種球面模型公式,其中一個就是上面推導出來的版本,稱為球面餘弦公式;另一個更常用的是 Haversine 公式,也是 spatial4j 的預設算法。

Haversine 本質上是球面餘弦函數的一種變換。原式含 cos(jb-ja) 項,當系統浮點精度不足時,計算兩點相距很近的情況會產生較大誤差;Haversine 透過變換消掉了這一項,因此不必再為短距離計算的精度問題操心。

1)Haversine 公式程式碼

public static double distHaversineRAD(double lat1, double lon1, double lat2, double lon2) {
        double hsinX = Math.sin((lon1 - lon2) * 0.5);
        double hsinY = Math.sin((lat1 - lat2) * 0.5);
        double h = hsinY * hsinY +
                   (Math.cos(lat1) * Math.cos(lat2) * hsinX * hsinX);
        return 2 * Math.atan2(Math.sqrt(h), Math.sqrt(1 - h)) * 6367000;
    }

2)Haversine 的效能表現

當時北京地區線上服務有 5 萬個 POI,算一輪距離要 7ms。資料成長速度很快,一旦北京 POI 增至 100 萬,篩選服務光是算距離就要吃掉 144 多 ms,效能堪憂。(測試環境:2.9GHz Intel Core i7、8GB 1600 MHz DDR3、OS X 10.8.3,單執行緒執行)

四、優化方案

抓 stack 之後發現,吃掉最多 CPU 的執行緒大多卡在距離公式裡的三角函數上,例如 atan2。方向因此非常明確:削減甚至徹底消除三角函數。以下逐一介紹嘗試過的幾種做法。

4.1 座標轉換法

1)基本思路

原本 POI 存的是經緯度(lon, lat),而我們的場景是拿用戶位置去比對篩選出來的所有 POI,其中充滿三角函數運算。一個思路是:POI 不存經緯度,改存球面模型下的三維座標(x, y, z),映射方式如下:

x = Math.cos(lat) * Math.cos(lon);

y = Math.cos(lat) * Math.sin(lon);

z = Math.sin(lat);

如此一來,求夾角 ∠AOB 只需做一次點乘。要算 (lon1,lat1) 與 (lon2,lat2) 的夾角,只算 x1x2 + y1y2 + z1*z2 即可,大量三角函數就省下來了。

得到夾角後仍需執行 arccos 把它轉成角度,最後 AB 弧長 = ∠AOB × R。

此方法的效能如下:

2)再往前一步

美團做的是本地生活服務,距離計算幾乎都在單一朝在建工程內進行,因此 ∠AOB 往往很小。此時 sin∠AOB ≈ ∠AOB,於是我們把 Math.acos(cosAOB) * R 改寫為 Math.sqrt(1 - cosAOB * cosAOB) * R,三角函數就此完全消失。優化後效能如下:

4.2 簡化距離公式法

1)基本思路

既然場景僅限城市範圍,兩點距離通常不超過兩百多公里。範圍夠小,就可以近似認為經線與緯線互相垂直。要求 A(116.8, 39.78)與 B(116.9, 39.68)的距離,可以先算南北向距離 AM,再算東西向距離 BM,最後用矩形對角線求解,即 sqrt(AM² + BM²)。

簡化距離計算示意圖

南北方向 AM = R × 緯度差 × Math.PI / 180.0;

東西方向 BM = R × 經度差 × Cos(當地緯度) × 180.0 / Math.PI。

這種算法只需要呼叫一次 cos 函數。

public static double distanceSimplify(double lat1, double lng1, double lat2, double lng2, double[] a) {
        double dx = lng1 - lng2;          // 經度差值
        double dy = lat1 - lat2;          // 緯度差值
        double b = (lat1 + lat2) / 2.0;   // 平均緯度
        double Lx = toRadians(dx) * 6367000.0 * Math.cos(toRadians(b));  // 東西距離
        double Ly = 6367000.0 * toRadians(dy);  // 南北距離
        return Math.sqrt(Lx * Lx + Ly * Ly);    // 用平面的矩形對角距離公式計算總距離
    }

接著我們驗證這個方法的有效性和效能。

1.1)有效性驗證

首先要確認簡化後的精度能否滿足業務要求,若誤差過大就無法上生產。我們的方法叫 distanceSimplify,Lucene 的叫 distHaversineRAD,下表列出兩者在不同尺度下的差異。

可以看到,百米與千米尺度上幾乎沒有差別,萬米尺度也只差到分米級。由於業務僅在城市範圍內排序,我們特意挑選北京左下角與右上角兩點做對比,兩點相距 260 多公里,兩個方法相差 17 公尺。就精度而言,這個優化完全能滿足需求。

1.2)效能驗證

2)再往前一步

這裡仍呼叫了一次 cos。如果能把它也消掉,效率還能再上一層。

怎麼消除?用多項式擬合 cos 函數,三角運算就只剩下加減乘除。多項式的最高次數需要決定:1 次和 2 次都擬合得不好,那就先試 3 次。注意次數並非越高越好,過高會導致過擬合。

我們用 org.apache.commons.math3 這個數學工具包來做擬合。中國緯度範圍約在 10~60 之間,就把這個區間離散成 Length 份作為訓練集。

public static double[] trainPolyFit(int degree, int Length){
    PolynomialCurveFitter polynomialCurveFitter = PolynomialCurveFitter.create(degree);
    double minLat = 10.0;   // 中國最低緯度
    double maxLat = 60.0;   // 中國最高緯度
    double interv = (maxLat - minLat) / (double)Length;
    List weightedObservedPoints = new ArrayList();
    for(int i = 0; i < Length; i++) {
        WeightedObservedPoint weightedObservedPoint = new WeightedObservedPoint(1,  minLat + (double)i * interv, Math.cos(toRadians(minLat + (double)i * interv)));
        weightedObservedPoints.add(weightedObservedPoint);
    }
    return polynomialCurveFitter.fit(weightedObservedPoints);
}

public static double distanceSimplifyMore(double lat1, double lng1, double lat2, double lng2, double[] a) {
        //1) 計算三個參數
        double dx = lng1 - lng2;          // 經度差值
        double dy = lat1 - lat2;          // 緯度差值
        double b = (lat1 + lat2) / 2.0;   // 平均緯度
        //2) 計算東西方向距離和南北方向距離(單位:公尺),東西距離採用三階多項式
        double Lx = (a[3] * b*b*b  + a[2]* b*b  + a[1] * b  + a[0] ) * toRadians(dx) * 6367000.0;  // 東西距離
        double Ly = 6367000.0 * toRadians(dy);  // 南北距離
        //3) 用平面的矩形對角距離公式計算總距離
        return Math.sqrt(Lx * Lx + Ly * Ly);
    }

2.1)有效性驗證

優化方法叫 distanceSimplifyMore,對照組仍是 distHaversineRAD,不同尺度下的差異如下表。

百米尺度上幾乎無差,千米尺度僅分米級;72 公里處差 5.6 公尺,264 公里處差 8.1 公尺。精度足以支撐業務需求。

2.2)效能驗證

五、實際落地

座標轉換與簡化公式兩種方案效能都很出色,相比 Lucene 的 Haversine 有大幅提升。但座標轉換法存在幾個明顯缺點:

a)轉換後的資料無法直接套用空間索引。Lucene 可以直接對經緯度做 geohash 空間索引,一旦變成三維資料就用不上了。而我們的應用有「附近範圍篩選」功能(例如附近 5 公里的團購單),靠 geohash 能顯著提升範圍篩選效率;

b)增加記憶體開銷。座標會寫入倒排索引,原本 2 欄(經度、緯度)變成 3 欄(x, y, z),而這些資料通常會放進 cache,記憶體佔用量隨之上升;

c)增加建索引開銷。本質上它把計算從查詢階段前移到索引階段,建索引成本自然提高。

基於上述權衡,我們最終採用簡化距離公式法(以三次多項式擬合 cos)。該方案已在團購篩選與商家篩選的距離排序、智能排序中上線。效果很直接:北京全城美食品類的距離排序響應時間從 40ms 降至 20ms。

六、參考資料

https://blog.csdn.net/liminlu0314/article/details/8553926

https://www.movable-type.co.uk/scripts/gis-faq-5.1.html

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved