1 Star 4 Fork 0

逐光 / fastMinDist

加入 Gitee
与超过 800 万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
贡献代码
同步代码
取消
提示: 由于 Git 不支持空文件夾,创建文件夹后会生成空的 .keep 文件
Loading...
README.md

fastMinDist

本包功能说明:

  • 数据库里有N个坐标皆为{(X1,Y1),,,,(Xn,Yn)},用户输入一个目标点(X,Y),则以最快速度 查询距离目标点最短的m个坐标。
  • 主要为解决目标点经纬度,与库内大量经纬度坐标对比m个最近点的查询效率问题。本包是针对大量坐标点的筛选,若数据库里坐标太少,则提速意义本身就不大。
  • 重要:若数据库内坐标数少于9000,则直接抛错,因为坐标数少于9000,提速意义太小。
  • 本包的实现策略是通过缩小筛选区域,来实现减少大量遍历量来实现检索提速。
  • 可缩小的筛选区域为原来0.1~无限小的区域,即遍历提速为10倍~无限倍
  • 收缩区域大小为可调参数,收缩大小与精准度挂钩,收缩的区域越大,则精准度越精准。
  • 经案例测试当收缩筛选区域最大为0.1时,也就是提升十倍筛选速时,精准为100%,仅存在理论上不精准的可能,实际上几乎不可能发生不精准。 所以开发者,最低调到0.1即可,为最稳定收缩范围。
    • 若无需绝对精准,可将参数继续向下调整,相应的精准度下降。例如,当筛选区缩减到0.02时,即五十倍速,则精准度经过测试大概在0.95左右,五十倍速也是本包的默认值。
    • 所谓"精准度"即相当于全遍历查找最近值的落点在筛选范围内,即使是不精准时也一定会有极近点落在筛选范围内,不会南辕北辙,只是不是真实最近点而已。

API说明

预运算部分即运算类的初始化

第一步,先初始化计算类:

//出事化运算类
PositionOperation operation= new PositionOperation();
//设置筛选区域收缩系数,当前即为全部坐标数量的0.2倍,即为筛选五倍速
operation.setSh(0.2);

第二步,塞入数据库里面所有坐标数据:

for (int i = 0; i < 9998; i++) {
Position position = new Position();
//分别塞入XY坐标,这里用随机数来模拟坐标信息
position.setX(random.nextInt(1000));
position.setY(random.nextInt(1000));
//塞入该坐标在数据库中对应的主键,这里是用下标来模拟主键,实际为数据库中对应的坐标主键
position.setUid(i);
//塞入计算类
operation.insertXY(position);
}

第三步,开始运算

//运算结束会返回Position集合
List<Position> positionList = operation.start();
 for (Position position : positionList) {
       //这个是集合中你输入时对应的坐标主键
       int uid = position.getUid();
       //这个是新生成的查询主键,将这个查询主键保存在数据库中对应的坐标的一个字段中
       int id = position.getId();
  }

第四步(可选),获取模型保存数据库

//获取运算参数留待下次 服务启动时注入,建议获取之后序列化为json字符串保存数据库
Parameter parameter = operation.getModel();
//下次服务启动,若库里没有新加入的坐标 则可直接从数据库中取出json,反序列化为实体参数类后直接注入,而无需重新运算
operation.insertModel(parameter);

以上为预运算部分结束,即数据准备,以保存数据库坐标对应查询id为结束,查询id为一个自增id。

当数据库中坐标更新时,既有增删改的行为,则需重新预运算一次,否则数据库中修改内容无法生效。

实际运算部分->当接收一个坐标点(X,Y)

返回一个数组,其结构为[starIndex,finishIndex],这里面的index即为之前保存的查询id的 筛选范围,第一个元素为开始查询主键,第二个为结束查询主键,其大小范围是库里坐标总数乘以sh,即收缩筛选范围

int[] region = operation.getRegion(x, y);

operation为服务器启动时,初始化且只初始化一次的单例的运算类。若不进行初始化,可直接进行步骤四,直接注入参数也等同于初始化。

注意:实际运算时,是直接调用服务启动时初始化的单例运算类operation,切不可每次运算时现NEW(这个操作本身就耗时)。

常见抛错

加载运算类坐标数少于9000,则运算不执行,开发者全遍历就好,筛选范围几乎没有提速意义。

"Too few samples: less than 99"

简介

进行极速经纬度最近点匹配 展开 收起
Java
Apache-2.0
取消

发行版

暂无发行版

贡献者

全部

近期动态

加载更多
不能加载更多了
1
https://gitee.com/ldp_dpsmax/fast-min-dist.git
git@gitee.com:ldp_dpsmax/fast-min-dist.git
ldp_dpsmax
fast-min-dist
fastMinDist
master

搜索帮助