摘自 怎么快速找到：附近的人 - 知乎
僅供個人使用
問題描述：如何實現(xiàn) “附近的人” 功能？
暴力法：歐式距離
原理：計算這個用戶與其他用戶的歐氏距離，然后進行排序
優(yōu)點：實現(xiàn)簡單
缺點：時間復(fù)雜度高，當用戶量大時，即使使用類似于 MR 的分布式運算，也需要消耗大量資源。
推薦：GeoHash
原理：將地圖展開成一個平面，將平面切割成小格并為小格編號。將用戶的位置轉(zhuǎn)換成所處小格的編號。與當前用戶同一個格子或附近格子的用戶返回給當前用戶。
GeoHash：為格子編號的一種編碼方式： 『每次將范圍折半，值處于前半部分，得 0；反之，得 1?！?/strong>
// geohash的偽代碼
public String getCode(double value, double min, double max, double codeLen){
StringBuilder sb = new StringBuilder();
// codeLen：對折次數(shù)，即code的長度
for(int i=0; i<codeLen; i++){
double mid = (max + min) / 2.0;
if(value < min){ // 說明 值處于前半?yún)^(qū)
sb.append('0');
} else{ // 說明 值處于后半?yún)^(qū)
sb.append('1');
}
}
return sb.toString();
}
GeoHash計算方式的示例
GeoHash完整的轉(zhuǎn)換
問題：如何快速查找 “附近的人”？
1）將 (user_id, user_geoCode) 存入數(shù)據(jù)庫并在 user_geoCode 建索引
2）select * from locTable where user_geoCode = curUser_geoCode 返回附近的人（即同一格子的人）
更多問題（如下）見參考文獻
- 編碼設(shè)置為多少位比較合適？
- 同一格子內(nèi)沒有人，該如何處理？
