1
wangxiaoaer 2019-12-16 11:08:10 +08:00 1
你:感觉服务器承受不住。
服务器:你是不是想太多了? 吃瓜群众:你丫先试试然后再去畅想可以吗? |
2
lhx2008 2019-12-16 11:09:55 +08:00 via Android 1
缓存,近似计算
|
3
hereIsChen OP |
4
stoneabc 2019-12-16 11:37:08 +08:00 1
模拟退火…?
|
5
lhx2008 2019-12-16 11:42:39 +08:00 via Android 1
@hereIsChen 如果你的输入数据是固定的,那就算一次把结果存起来。如果是部分固定的,那么就固定的和不固定的分开。如果是完全动态的,你这个应该算 TSP 问题,你可以找一些近似的算法,比如模拟退火
|
6
opengps 2019-12-16 11:45:37 +08:00 1
我虽然做了几年 LBS 服务,但不是正规军出身。我给你个我的野蛮办法:强制舍弃小数点精度法
做法就是,本来 6 位小数点,强制四舍五入为 4 位甚至更少来判断是否“相等”! |
8
hereIsChen OP @opengps 算的是距离,而不是位置是否相等,最后都会用到计算两点间经纬度的算法,不过舍弃精度应该可以节省一点
|
9
Akikiki 2019-12-16 11:50:35 +08:00 1
先把地图划分为多个格子,判断人员和服务地址属于哪个格子,然后判断最近的格子(格子之间的距离可以提前算好),然后再找?最好用六边形的格子。。。
瞎说的哈~ |
10
moyaka 2019-12-16 11:54:06 +08:00 via Android 1
Geohash 可,比较简单而且性能好。
|
11
wangxiaoaer 2019-12-16 11:58:43 +08:00
我真不明白你为什么不试一试?
两点之间计算球面距离都特么现成的公式,里面用到的就特么几个三角函数,这点计算量有啥抗不抗的住的????????? |
12
hereIsChen OP @wangxiaoaer 问题是多对多的优化,而不只是计算两点间的距离,光通过经纬度计算距离当然简单
|
13
opengps 2019-12-16 12:33:02 +08:00
@hereIsChen 舍弃精度得出的相等,就是实际需求中的“就近”了。计算距离回到这个范围内进行遍历即可。然后单独处理下没有被分配的服务的点,单独派工就好
|
14
opengps 2019-12-16 12:34:19 +08:00
@wangxiaoaer 传统做法是一个点搜周边多个点,然后排序取最近。一旦需求变成多对多,那么结算量是指数增加的,所以会变得不适用
|
15
aMR 2019-12-16 12:56:52 +08:00 1
分格子的思路是对的,进阶一下就是四叉树
|
16
Artemisr 2019-12-16 13:07:28 +08:00
redis 提供了实现
|
17
wangxiaoaer 2019-12-16 13:16:37 +08:00 1
多对多怎么了?按照最笨的办法就是 m x n 次距离计算,10000 x 10000 次计算,纯计算耗时 3 秒,但是没有排序。
如果你的 m n 量级不够大,这种方式完全不用担心。 如果 m n 量很大,Postgresl + PostGIS + 空间索引 + ( sql + ST_Distance ) 搞定。 |
18
rrfeng 2019-12-16 13:18:47 +08:00 via Android 1
geo 距离搜索现成的算法现成的实现…
没什么好讨论的。 |
19
wangxiaoaer 2019-12-16 13:37:45 +08:00
https://jsfiddle.net/gy54dbpn/1/
随手做的一个测试,不是很严谨,刚忘记贴了。 我始终只想表达一个意思,单纯的距离计算没有想象中的耗费资源,你应该结合你的实际数据量,哪怕是用最笨的办法先试一试,如果真的发现遇到瓶颈了,再考虑优化。 |
20
Tumblr 2019-12-16 13:45:59 +08:00
如果能飞起来,感觉就是个大圆弧( great circle )。。。
|
21
fightingZ 2019-12-16 14:10:51 +08:00
没理解错的话,这个问题不应该就是多源点寻找最短路径吗
|
22
NingAnMe 2019-12-16 17:55:38 +08:00
使用 KDtree。
1. 适合多维数据找最近。使用数量少的一组构建树,对数量多的一组查最近点。 2. 如果有一组数据不变,可以把数保存下来。 不会贴图,你自己查一下复杂度吧。 |
23
SKHuang 2019-12-16 18:05:14 +08:00
func GetDistance(lat1 float64, lng1 float64, lat2 float64, lng2 float64) float64 {
var ( radLat1 float64 radLat2 float64 a float64 b float64 s float64 ) radLat1 = GetRad(lat1) radLat2 = GetRad(lat2) a = radLat1 - radLat2 b = GetRad(lng1) - GetRad(lng2) s = 2 * earth_padius * math.Asin(math.Sqrt(math.Pow(math.Sin(a/2), 2)+math.Cos(radLat1)*math.Cos(radLat2)*math.Pow(math.Sin(b/2), 2))) return s } func GetRad(d float64) float64 { return d * math.Pi / 180.0 } |