List Merge的小算法

今天说一个算法小甜点,因为对于算法知之甚少,所以完全是自己揣摩出来的一则,写出来只是个记录,如有更学术派的解法欢迎评论。

场景

我们系统有一个去重的需求,但是查重的维度是多方面的,举个例子,若干个用户用了用一个手机号,那么我们就认为他们是同一个人,用手机号码这个条件可以查出一组这样的人。同理用Email也是。

但是存在一个问题就是用手机号查出了5组人,用Email查出了3组人,最后我们可以认为重复的人是8吗?其实是不行的,因为有可能某几个人的手机号和Email都是一样的,那么在两次查询后都会将这些人纳入到统计中。所以最后统计出的结果应该是<=各次查询结果之和的。

解决方案

首先是数据结构,每次查询出来的结构是一个List,那么List里面其实又是一组重复的人。

为了方便理解,我们可以定义一个最小化结构为Group,

1
2
3
4
5
public class Group {

private List<Long> duplications = new ArrayList<>();

}

里面的duplicates代表原始记录ID列表,举例说就是ID=13和ID=15的两条记录都是用的同一个手机号,那么duplications就是{13,15}。

每通过一个条件查询可以得到一个List的返回,很好理解,这个List的size就是说明有多少人用了相同的手机号。那么用Email查询的话结果就是代表多少人用了相同的Email。

假设ID=13的这条记录,它已经在用手机号查询的结果中被GroupA收录,如果它又在Email查询的结果中被GroupF收录的话,说明了什么问题?说明其实GroupA和GroupF应该取个合集,他们都是代表了同一个人。有点类似消消乐的意思。我们最后其实不管是通过什么条件查出来的,只要是一个Group的集合就好了。

1
2
3
4
5
6
7
8
// 先定义一个篮子
List<Group> duplicateBucket = new ArrayList<>();
for (// 若干条件) {
List<Group> duplicates = queryProvider.queryDuplications();
duplicateBucket.addAll(duplicates);
}
// 对这个篮子做一次去重
DeduplicationUtils.intersection(duplicateBucket);

再看这个去重的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void intersection(List<Grouop> duplicates) {
for (int i = duplicates.size() - 2; i >= 0; i--) {
for (int j = duplicates.size() - 1; j > i; j--) {
Set<Long> setA = duplicates.get(i).toSet();
Set<Long> setB = duplicates.get(j).toSet();
Set intersection = Sets.intersection(setA, setB);
if (intersection.size() > 0) {
// 找出差集做合并
List<Long> differences = new ArrayList<>();
for (Long id : duplicates.get(j).getDuplications()) {
if (intersection.contains(id)) {
continue;
}
differences.add(id);
}
duplicates.get(i).addAllDuplications(differences);
duplicates.remove(j);
}
}
}
}

这里是关键,实际上就是双层遍历做对比,发现重复条目就做消消乐,让后者融合进前者的集合中去。

小结

这样就基本解决了去重的问题,但是效率一般,毕竟有双重循环在。如有更好的办法欢迎留言。