首页 » 漏洞 » List Merge的小算法

List Merge的小算法

 
文章目录

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

场景

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

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

解决方案

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

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

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的集合就好了。

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

再看这个去重的逻辑

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);             }         }     } } 

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

小结

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

原文链接:List Merge的小算法,转载请注明来源!

0