二分算法
二分算法
本文通过二分算法解决实际业务问题，语言实现 Java。
业务需求
线索id（eventId）与最终线索 id（finalEventId）的 mapping 关系。
背景
有一张线索表，线索 id 为主键，当检测到线索 id 的信息有重复之后（例如同样的电话、邮箱等）会对线索 id 进行合并。然后生成一个新的线索。
# 线索6和7合并为8 ，然后线索8和9合并为10
10
├── 8
│ ├── 6
│ └── 7
└── 9
5
├── 4
│ └── 3
└── 1
# 最终要呈现的效果如下
eventId finalEventId
1 5
3 5
4 5
9 10
7 10
6 10
8 10数据表字段
# merge_result 里面记录的是 event_id ,被合并成了 新的 event_id， 如果 merge_result字段为空则表示event_id不是其他event_id合并而来的。
merge_result | event_id
-------------------------------------+----------
13405000,7297679 | 13405001
13017581,12782752,13405046,13017582 | 13405047
13405345,13012323 | 13405346
13405368,13012335 | 13405369
13405391,13012348 | 13405392
13405414,13012431 | 13405415
13017741,12782840,13405437,13017742 | 13405438
13405529,13012450 | 13405530
13405575,13012491 | 13405576
13405598,13091543 | 13405599
| 14730559处理方案
要获得finalEventId就需要一层层查询合并记录，一个eventId被合并之后，新的eventId还有可能被合并。因此我们需要进行递归查询。当我们将合并关系（merge_result）和（event_id）数据量为1亿条，合并前需要获得最终event_id 的记录为4千万条。4万千与1亿条数据进行递归查询就有点可怕了。因此采用二分算法进行查询。
数据准备
先在数据库中将数据展开，方便程序读处理。
select
event_id,from_event_id from table
lateral view explode(split(merge_result,',')) dual as from_event_id
-- 「业务背景」中的例子数据展开后如下:
event_id,from_event_id
10 8
8 6
8 7
10 9
5 4
4 3
5 1读取展开后的数据保存到列表
try (Stream<String> lines = Files.lines(Paths.get(file.getPath()))) {
resultList.addAll(lines
.map(line -> line.split("\001"))
.collect(Collectors.toList()));
}生成递归查找Event清单,这里一定要排序哦
List<Integer[]> eventList = resultList.stream()
.filter(i->i.length==2)
.map(i -> new Integer[]{Integer.parseInt(i[0]), Integer.parseInt(i[1])})
.sorted(Comparator.comparing(i -> i[1]))
.collect(Collectors.toList());生成需要匹配Event清单
List<Integer[]> result = querySet.parallelStream().map(i-> new Integer[]{i,findFinalEventId(i,eventList,i)}).collect(Collectors.toList());匹配结果
建立二分查找的函数
/**
* 二分查找
*
* @param num 被查询的列表
* @param queryEventId 查询的eventId
* @return 匹配到的finalEventid
*/
public static int binarySearch(List<Integer[]> num, int queryEventId) {
//开始位置
int start = 0;
//结束位置
int end = num.size() - 1;
while (start <= end) {
//中间索引元素
int middle = (start + end) / 2;
if (num.get(middle)[1] > queryEventId) {
end = middle - 1;
} else if (num.get(middle)[1] < queryEventId) {
start = middle + 1;
} else {
return num.get(middle)[0];
}
}
return -1;
}建立递归查找函数,递归的过程中通过二分算法获取数据。
/**
* @param queryEventId 需要查询的 eventId
* @param fullEventList 所有 eventId 清单
* @param finalEventId 最终 eventId
* @return 最终 eventId
*/
private static Integer findFinalEventId(Integer queryEventId, List<Integer[]> fullEventList, Integer finalEventId) {
Integer nextQueryEventId = null;
int tmpFinalEventId = binarySearch(fullEventList, queryEventId);
if (tmpFinalEventId != -1) {
finalEventId = tmpFinalEventId;
nextQueryEventId = finalEventId;
}
if (nextQueryEventId != null) {
finalEventId=findFinalEventId(nextQueryEventId, fullEventList, finalEventId);
}
return finalEventId;
}通过并行的 stream 对每个 eventid 进行递归查找
List<Integer[]> result = querySet.parallelStream().map(i-> new Integer[]{i,findFinalEventId(i,eventList,i)}).collect(Collectors.toList());