一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 654|回复: 4
收起左侧

有人想探讨下uber的dispatch算法吗?

[复制链接] |试试Instant~ |关注本帖
ekco 发表于 2015-1-31 11:48:47 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@uber - 网上海投 - 其他 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近在准备uber的面试,想到他家最给劲的应该是实时的dispatch算法吧。这个应该不是开源的idea,毕竟是靠这个赚钱的,欢迎大家讨论说说自己的想法。

用户打开app后如何显示周围available的车,还有如何快速实时更新车的位置和availibility?

1. 每次打开app的时候会有一个雷达闪烁的画面,应该是在向server发送用户的geo data并request周围可用的uber,假设需要知道离用户5mile之内的所有uber的话,每辆uber车的geo信息应该如何存储才能快速的找到这5mile之内的车呢?

我的想法是把城市划分成多个block做成hashtable,每个block对应一个pool来存储目前在这个block中的所有车辆,每辆车记住上一个时间点的blockID,当车子移动需要update的时候计算当前的blockID如果与之前的不同,就把这辆车的carID从上一个block的pool中删除,并加入到新的block的pool中。这样用户login的时候,根据用户的geo信息计算其所对应的block,然后读取该block的pool。这样用户找到available车子的时间复杂度就是O(1),每辆车子update的复杂度也是O(1)。
-google 1point3acres
2. 当一辆车从变换availability的时候,会从地图上实时出现/消失,位置也会实时更新,这个应该是服务器push到用户终端的,要实现实习性,server和用户之间应该是通过websockets链接的,http的request/response无法满足要求。

3. 在uber的app上任意移动pin,即使从东海岸移动到西海岸,uber的app也能在很短时间内找到available的车子,地点换了,应该是要重新request server的吧,这个为啥能这么快?

欢迎大家讨论!. from: 1point3acres.com/bbs
yangzorror 发表于 2015-1-31 14:27:56 | 显示全部楼层
楼主说的有道理,我觉得一个主要的问题就是如何快速查询附近的司机,并给相应的司机发送消息。可以把问题抽象成,在二维坐标上有很多点(driver的位置),然后给一个乘客的位置,要求返回附近的driver。我觉得楼主的solution很有道理,不过我想补充的一点就是block之间要有overlap,因为如果乘客在block的边缘的话搜出的附近的driver就不准了。
回复 支持 反对

使用道具 举报

 楼主| ekco 发表于 2015-1-31 23:21:22 | 显示全部楼层
yangzorror 发表于 2015-1-31 01:27
楼主说的有道理,我觉得一个主要的问题就是如何快速查询附近的司机,并给相应的司机发送消息。可以把问题抽 ...

对,我也想到block边缘的情况了。还有一种情况就是,在另一个或几个block中有车离用户比他所在的block中的车一样近或者更近,一种解决办法就是你说的overlap,这样一辆车可能对应多个block。另一种不overlap但是就是读用户周围几个block的车辆,两张办法都可行,时间复杂度还是O(1)
回复 支持 反对

使用道具 举报

everending 发表于 2015-2-1 05:04:27 | 显示全部楼层
我不是太懂,就随便说说,欢迎指出错误~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

当block的车信息发生变化(比如有的车availibility变化,或者这个车进入另外一个block,或者有新车进入这个block)的时候,就在server端提前计算下这个block的等待时间。

这样的话,当用户端这边检测到pin state变化后,就向server请求,迅速拿到结果。

当然这个pre calculate可能不准,不过之后会不断更新,所以sloppy一点也无所谓。
回复 支持 反对

使用道具 举报

puncsky 发表于 2015-5-27 02:45:22 | 显示全部楼层
应该是用geohash http://en.wikipedia.org/wiki/Geohash. 1point 3acres 璁哄潧
MongoDB 2D index 有这个功能
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 21:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表