每周日下午，老王又如約跟大家聊技術幹貨了。
想必大家都用過微信的“附近的人”這個功能，可以看到你周圍都有誰，然後加個好友啥的。而我們出去吃飯，經常拿出大衆點評，看看附近有哪些好吃的。更有，我們現在經常用uber或者滴滴打車，你發出一個路線請求，就有附近的司機來搶單。或者，當你用百詞斬背單詞的時候，可以找個附近的人PK單詞量（哈哈哈，看到内置廣告了吧~）
我們今天不讨論這個功能在産品上的意義，而是讨論讨論在技術上，他是怎麼樣來實作的。
好了，正式開始今天的話題吧~
關于經緯度
說到附近的人，第一個要談到的就是經緯度。想必大家在國中（或者是高中）的地理課本裡早就學過了。我們把地球分成橫豎交錯的一些格子，每個點都可以用橫豎坐标來表示。橫線表示緯度（範圍在[-90°, +90°]），豎線表示經度（範圍在[-180°, +180°]）。比如老王所在的位置，就可以在地圖上用經緯度來表示：
如何擷取經緯度
既然每個人所在位置都可以用經緯度來表示，那我們如何擷取呢？我們現在智能手機基本都可以通過GPS或者基站進行定位，隻要app調用系統的定位函數，就可以輕易拿到這樣的資料（當然，需要使用者的确認）。當用戶端拿到這樣的資料以後，就可以将位置資訊上傳伺服器，由伺服器來判定附近有哪些人。
如何查找
好了，該切入關鍵點了。當伺服器收到很多使用者的位置資訊以後，怎麼來判斷你周圍有哪些人呢？我們先想一個最簡單的實作。當平面上隻有兩個點（分别代表兩個人）的時候，我們怎麼計算出他們之間的距離呢？
如果把地球看成一個球體，我們比較容易就用立體幾何的知識去計算出他們之間的距離。但是這個過程會比較複雜。如果我們相距的兩點不是特别遠（相對地球半徑而言），我們就可以把他們近似看成平面上的兩點，用最簡單的歐式距離公式d(A,B) = sqrt((x1-x2)^2 + (y1-y2)^2)，便可以得到A和B之間的距離，對吧。
好了，當我們的使用者不是太多的時候，我們就可以采用周遊的方法，依次計算出其他所有的點同我的距離d1 d2 ... dk，然後按照距離從小到大排序，得到我們想要的結果，對吧？
看起來一切都很美妙，我們來算算時間複雜度。周遊所有的點，計算距離，是一個O(n)複雜度的算法，然後排序做Top，基本上是一個O(n * lgn)的複雜度。是以，總的看來，是一個O(n * lgn)複雜度的算法。當然，在計算和排序的過程中我們可以做優化。當在幾千個點的時候，我們的伺服器都可以輕松應對，如果我們的點變多了呢？比如，幾萬、幾十萬……
第一種方案：分布式計算
還記得以前老王講分布式的文章（忘了的同學請到老王的微信simplemain裡尋找哈）嘛？
很顯然涉及到大量運算的時候，我們可以将這些運算拆分到多個伺服器來進行，這樣就可以提高我們并行計算的速度和效率。那當我們有幾萬、十幾萬使用者的時候，我們就可以将這些使用者分布到不同的機器上，讓每個機器都計算一部分，然後每個機器給出自己機器的Top，最後由某一台或幾台彙總，給出最後的結果。
比如，第一台機器計算uid從1-10000的使用者和我的距離，并給出最後的top100；第二台機器計算uid從10001-20000的使用者和我的距離，并給出最後的top100……以此類推。最後由computer-R來彙總這些top100，并給出排序結果，輸出最後的top100。
如果當計算的機器特别多，computer-R就會成為瓶頸，就需要分裂成多台機器，然後再彙總。
這種方案的優點就是：
1、算法實作簡單：隻需要用單機版的點點距離判斷+排序，就可以搞定；
2、前面的結果相對比較精确：因為距離都是非常精确的歐式距離，是以TopK的結果都是比較精确的
不足：
1、消耗機器嚴重：随着使用者量的增加，機器消耗就直線上升；
2、後面的結果相對不那麼精确：在每台機器做TopN以後，實際上就扔掉了其餘的資料，最後有可能某台機器上一個很優的結果，沒有進入到最後的歸并排序。
第二種方案：GeoHash
那我們有沒有辦法降低對機器的消耗，而且還能在全局做到相對準确的結果排序呢？
其實也是有辦法的。具體怎麼做呢？跟着老王一起往下看吧。
whatto do？
如果我們能将地球劃分成一個個很小的方形的格子，在同一個格子裡的人，是不是就很接近呢？再如果，我們給每個格子編一個代号，那擁有同一個代号的人，是不是就靠的很近呢？這有可能麼？那我們就來試試吧~
howto do？
1、把地球拉成平面：
先假設我們把地球從一個球體拉成一個平面（用幾何知識就可以求解相關的對應關系）。
2、按經度将地球切開
我們以經度0°為中軸，将地球切成兩半[-180°,0°),[0°，180°]，并對他們進行二進制編碼，左邊為0，右邊為1。
那所有經度坐标在左邊的，都得到了0這個編碼，而其他的則得到1這個編碼。比如，老王所在位置的經緯度值是(104.071398, 30.537445)，老王的經度104.071398∈[0°，180°]，是以編碼就是1。
好了，接下來我們就進行第二次切割，還是按照老規矩，我們把現有的兩個部分也分别切割成左右兩個部分，于是得到這樣的一個圖：
我們得到四個編碼：00 01 10 11，每個編碼的第一位是第一次切割時候得到的數字，00 01就是第一切割時在左邊，編碼為0；第二位就是第二次切割，在左邊為00，在右邊為01。同理得到10 11。比如，老王所在位置的經緯度值是(104.071398,30.537445)，老王的經度104.071398∈[90°，180°]，是以編碼就是11。
如此這樣重複N次，我們就可以将地球按經度切割成很多很多的小塊，如果切割的次數足夠多，那同一個經度值的人，都會在同一個小塊兒裡，對吧。那也會得到對應這個小塊兒的二進制編碼。比如老王的經度104.071398經過多次切割得到如下這個表格：
這樣，我們就可以得到104.071398的編碼是：11001010。随着切分的繼續，我們可以得到更長的編碼，這樣就可以對應更細緻的區間。
3、按緯度将地球切開
用同樣的方法，我們按照緯度也把地球切成這樣的方式，最終得到對應經緯度的編碼：
(104.071398, 30.537445) -> (11001010,10101011)
老王簡單寫了一個編碼的實作代碼：
有了經緯度的切割，地球就被我們劃分成了2n*2n個格子，比如當n等于8的時候，這個格子數就是65536。
4、統一編碼
為了友善記錄，我們把經度和次元的二進制格子編碼進行合并，按經度、緯度、經度、次元……這樣的順序，一位一位的進行放置：
(104.071398, 30.537445)
-> (11001010,10101011)
-> 1110010011001101
上面最後的編碼，奇數位的紅色是經度編碼，偶數位的黑色是緯度編碼。這樣表示起來還是太長了，我們怎麼樣縮短呢？也很簡單，我們可以用16進制、32進制、64進制這樣的進制來縮短編碼長度。這裡業界推薦的是32進制，也就是base32編碼。
這樣，每5個二進制（25=32）組成一個編碼字元，于是：
(104.071398, 30.537445)
-> (11001010, 10101011)
-> 1110010011 00110 1
-> wm6 (3個完整有效進制數)
5、劃分的精細度
有了這樣的編碼，那到底要劃分多少次，我們的資料才足夠精确呢？我們在維基百科上找到了這樣的一張對應表：
當有一個base32數字的時候，精細度大概是2500公裡，當有8個數字的時候，精細度大概是0.019km = 19米。也就是說，8個base32的數字 對應 8*5=40個二進制數，也就是經緯度分别劃20次，就可以達到19米的精細度。這對于我們平時使用已經足夠了。
6、如何查找
有了以上的準備工作，我們就可以給地圖上所有的人進行編碼了，然後将(user,code)這樣的key-value對放入到資料庫的user_loc_code表中。當請求某個人附近的人的時候，我隻要把這個人的code取出來，然後做一個sql：select * from user_loc_code where code=xxx就可以得到想要的答案了（不過記得要在code上建索引哦^_^）。這個算法的時間複雜度就完全取決于資料庫的索引結構（如果是Hash索引，則近似O(1)算法；如果是B-Tree索引，則近似O(lgn)算法）。是不是很簡單也很高效呢？
稍等！事情還沒完呢。如果這個小方形裡沒有其他人怎麼辦？産品經理說：我們還是需要給使用者傳回最近的人！
那其實也很簡單，我們隻要把編碼長度從1到8的編碼都記錄下來，我們就擁有了2500km-0.019km範圍差的所有值，那我們寫sql的時候，最多寫8個，就一定能找到我們想要的（一般産品經理會說：我們隻要20公裡範圍内的使用者，那sql最多最多就隻需要寫5個，對吧）。具體的表就可以這樣建：
(user, code1, code2, ..., code8)，記得給每個code加上索引哦~
7、話外音
上述的算法，實際上是一個近似算法，我們認為在同一方形格子裡的，就是距離最近的，可是實際上呢？
比如，A和C在同一格子裡，A和B在不同格子裡，但是明顯A和B的距離更近，但是卻被硬生生的分開了…… 那這種問題我們如何來解決呢？其實也是有辦法的。
如果産品要求不高，我們就不需要解決。如果産品确實要求精度比較高，我們可以取求解的格子的周圍其他八個格子的點，然後一起來算距離排序。這樣，我們就能求解到最精确的值。
====總結的分割線 ====
好了，以上的内容都看懂了嘛？老王其實就喜歡扯扯跟實際工作和生活有關系的一些算法和架構，如果對老王講的内容感興趣，就繼續在周日下午關注老王的微信(simplemain)吧~