# fastMinDist

**Repository Path**: ldp_dpsmax/fast-min-dist

## Basic Information

- **Project Name**: fastMinDist
- **Description**: 进行极速经纬度最近点匹配
- **Primary Language**: Unknown
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 9
- **Forks**: 5
- **Created**: 2021-06-04
- **Last Updated**: 2024-10-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 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"