专业IM即时通讯软件开发,值得信赖!

【转】【附近的人】实现原理

即时通讯软件开发 云聊IM 1064℃

想必大家都用过微信的“附近的人”这个功能,可以看到你周围都有谁,然后加个好友啥的。而我们出去吃饭,经常拿出大众点评,看看附近有哪些好吃的。更有,我们现在经常用uber或者滴滴打车,你发出一个路线请求,就有附近的司机来抢单。或者,当你用百词斩背单词的时候,可以找个附近的人PK单词量(哈哈哈,看到内置广告了吧~)

我们今天不讨论这个功能在产品上的意义,而是讨论讨论在技术上,他是怎么样来实现的。

好了,正式开始今天的话题吧~

关于经纬度

说到附近的人,第一个要谈到的就是经纬度。想必大家在初中(或者是高中)的地理课本里早就学过了。我们把地球分成横竖交错的一些格子,每个点都可以用横竖坐标来表示。横线表示纬度(范围在[-90°, +90°]),竖线表示经度(范围在[-180°, +180°])。比如老王所在的位置,就可以在地图上用经纬度来表示:

如何获取经纬度

既然每个人所在位置都可以用经纬度来表示,那我们如何获取呢?我们现在智能手机基本都可以通过GPS或者基站进行定位,只要app调用系统的定位函数,就可以轻易拿到这样的数据(当然,需要用户的确认)。当客户端拿到这样的数据以后,就可以将位置信息上传服务器,由服务器来判定附近有哪些人。

如何查找

好了,该切入关键点了。当服务器收到很多用户的位置信息以后,怎么来判断你周围有哪些人呢?我们先想一个最简单的实现。当平面上只有两个点(分别代表两个人)的时候,我们怎么计算出他们之间的距离呢?

如果把地球看成一个球体,我们比较容易就用立体几何的知识去计算出他们之间的距离。但是这个过程会比较复杂。如果我们相距的两点不是特别远(相对地球半径而言),我们就可以把他们近似看成平面上的两点,用最简单的欧式距离公式d(A,B) = sqrt((x1-x2)^2 + (y1-y2)^2),便可以得到A和B之间的距离,对吧。

然而,地球是个球体。所以,并不能按照直线距离计算。网上找到的公式如下:

  1. Lng1表示A点纬度和经度,Lat2 Lng2 表示B点纬度和经度
  2. a = Lat1 – Lat2为两点纬度之差 b = Lng1 -Lng2 为两点经度之差
  3. 6378.137为地球半径,单位为公里
  4. 计算出来的结果单位为公里

由大牛改装过的代码是这样的:

Mysql排序公式:

select * from sb_user_geo order by ACOS(SIN(('.$city_lat.' * 3.1415) / 180 ) *SIN((lat * 3.1415) / 180 ) +COS(('.$city_lat.' * 3.1415) / 180 ) * COS((lat * 3.1415) / 180 ) *COS(('.$city_lng.' * 3.1415) / 180 - (lng * 3.1415) / 180 ) ) * 6380  asc  limit 30

PHP计算两点之间的距离:

/**
     *求两个已知经纬度之间的距离,单位为千米
     *@param lng1,lng2 经度
     *@param lat1,lat2 纬度
     *@return float 距离,单位千米
     **/
    private function _distance($lng1,$lat1,$lng2,$lat2)//根据经纬度计算距离
    {
        //将角度转为弧度
        $radLat1=deg2rad($lat1);
        $radLat2=deg2rad($lat2);
        $radLng1=deg2rad($lng1);
        $radLng2=deg2rad($lng2);
        $a=$radLat1-$radLat2;//两纬度之差,纬度<90
        $b=$radLng1-$radLng2;//两经度之差纬度<180
        $s=2*asin(sqrt(pow(sin($a/2),2)+cos($radLat1)*cos($radLat2)*pow(sin($b/2),2)))*6378.137;
        return $s;
    }

好了,当我们的用户不是太多的时候,我们就可以采用遍历的方法,依次计算出其他所有的点同我的距离d1 d2 ... dk,然后按照距离从小到大排序,得到我们想要的结果,对吧?

看起来一切都很美妙,我们来算算时间复杂度。遍历所有的点,计算距离,是一个O(n)复杂度的算法,然后排序做Top,基本上是一个O(n * lgn)的复杂度。所以,总的看来,是一个O(n * lgn)复杂度的算法。当然,在计算和排序的过程中我们可以做优化。当在几千个点的时候,我们的服务器都可以轻松应对,如果我们的点变多了呢?比如,几万、几十万……

第一种方案:分布式计算

很显然涉及到大量运算的时候,我们可以将这些运算拆分到多个服务器来进行,这样就可以提高我们并行计算的速度和效率。那当我们有几万、十几万用户的时候,我们就可以将这些用户分布到不同的机器上,让每个机器都计算一部分,然后每个机器给出自己机器的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的距离更近,但是却被硬生生的分开了…… 那这种问题我们如何来解决呢?其实也是有办法的。

如果产品要求不高,我们就不需要解决。如果产品确实要求精度比较高,我们可以取求解的格子的周围其他八个格子的点,然后一起来算距离排序。这样,我们就能求解到最精确的值。

原文地址:http://blog.csdn.net/zgwangbo/article/details/52014446

版权声明:部分文章、图片等内容为用户发布或互联网整理而来,仅供学习参考。如有侵犯您的版权,请联系我们,将立刻删除。
喜欢 (0)
仿微信聊天软件开发
点击这里给我发消息