# 二分算法

本文通过二分算法解决实际业务问题,语言实现 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

数据表字段

# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 处理方案

要获得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
1
2
3
4
5
6
7
8
9
10
11
12
13
14

读取展开后的数据保存到列表

try (Stream<String> lines = Files.lines(Paths.get(file.getPath()))) {
    resultList.addAll(lines
            .map(line -> line.split("\001"))
            .collect(Collectors.toList()));
}
1
2
3
4
5

生成递归查找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());
1
2
3
4
5

生成需要匹配Event清单

List<Integer[]> result = querySet.parallelStream().map(i-> new Integer[]{i,findFinalEventId(i,eventList,i)}).collect(Collectors.toList());
1

# 匹配结果

建立二分查找的函数

    /**
     * 二分查找
     *
     * @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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

建立递归查找函数,递归的过程中通过二分算法获取数据。

    /**
     * @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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

通过并行的 stream 对每个 eventid 进行递归查找

List<Integer[]> result = querySet.parallelStream().map(i-> new Integer[]{i,findFinalEventId(i,eventList,i)}).collect(Collectors.toList());
1

源码:get_final_event_id (opens new window)

更新时间: 3/8/2022, 4:08:23 PM