摘自 怎么快速找到：附近的人 - 知乎
僅供個(gè)人使用
問題描述：如何實(shí)現(xiàn) “附近的人” 功能衩匣？
暴力法：歐式距離
原理：計(jì)算這個(gè)用戶與其他用戶的歐氏距離蕾总，然后進(jìn)行排序
優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單
缺點(diǎn)：時(shí)間復(fù)雜度高，當(dāng)用戶量大時(shí)琅捏，即使使用類似于 MR 的分布式運(yùn)算生百，也需要消耗大量資源。
推薦：GeoHash
原理：將地圖展開成一個(gè)平面柄延，將平面切割成小格并為小格編號(hào)蚀浆。將用戶的位置轉(zhuǎn)換成所處小格的編號(hào)。與當(dāng)前用戶同一個(gè)格子或附近格子的用戶返回給當(dāng)前用戶搜吧。
GeoHash：為格子編號(hào)的一種編碼方式： 『每次將范圍折半市俊，值處于前半部分，得 0滤奈；反之摆昧，得 1⊙殉蹋』
// geohash的偽代碼
public String getCode(double value, double min, double max, double codeLen){
StringBuilder sb = new StringBuilder();
// codeLen：對(duì)折次數(shù)绅你，即code的長(zhǎng)度
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計(jì)算方式的示例
GeoHash完整的轉(zhuǎn)換
問題：如何快速查找 “附近的人”伺帘？
1）將 (user_id, user_geoCode) 存入數(shù)據(jù)庫(kù)并在 user_geoCode 建索引
2）select * from locTable where user_geoCode = curUser_geoCode 返回附近的人（即同一格子的人）
更多問題（如下）見參考文獻(xiàn)
- 編碼設(shè)置為多少位比較合適？
- 同一格子內(nèi)沒有人忌锯，該如何處理伪嫁？
