精华内容
下载资源
问答
  • 本篇博客介绍了几种能够找出List集合中不同元素方法, 并通过性能对比和源码分析方式来介绍几种方式区别, 希望大家遇到类似需求能够选择合适方法,少走弯路
    近期,花了一段时间开发生产环境中的自动补数工具,来替代我完成繁琐无趣的人肉运维工作.
    
    这款补数工具有这样一个小的需求点:
    快速的找出两个相似度非常高的List集合里的不同元素.
    (每个集合大约有200W个元素,并且随着业务的扩展集合的数据量会越来越大,两个集合之间可能只有几个元素不同)
    期间,踩了一点小坑,把入坑到脱坑的过程分享给大家,希望大家遇到类似的需求时能选取合适的方法,少走弯路
    

    本篇博客相关代码已经上传到github,需要的请自行下载:

    项目github链接

    本篇博客涉及代码的github链接

    本篇博客要点如下:

    测试数据集准备

    笨比操作一 ---- 使用Java自带的api比较不同

    笨比操作二 ---- 使用List集合双层遍历比较不同

    人类方法 ---- 借助Map集合找出不同

    全量代码分享

    一点思考

    一.测试数据集准备

    测试数据为A集合: 1千, 1万, 10万,1百万, 1千万的数据量.
    B集合比A集合多十条数据.
    测试数据使用空字符串 + 自然数的方式.

    造数方法如下:

     	/**
         * 制造任意个元素的的List集合
         * @param size List集合的size
         * @return List<String>
         */
        private static List<String> dataList(int size) {
            List<String> dataList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                dataList.add("" + i);
            }
            return dataList;
        }
    

    我们采用以下方法打印出两个集合不同的元素,
    以此来确保我介绍到的每种方法都可以正确找到两个集合中的不同元素

        /**
         * 遍历集合,打印出每个元素
         * @param list List集合
         */
        private static void traverse(List<String> list) {
            for (String str : list) {
                System.out.print(str + " ");
            }
            System.out.println();
        }
    

    二.使用Java自带的api比较不同

    这是我最初使用的办法,原因,代码量少,不用动脑.
    核心代码只有以下四行:

    		/*
    			通过下面的四行代码,
    			我们得到了以下三个集合
    			ListA : 集合A与集合B不同的元素
    			ListB : 集合B与集合A不同的元素
    			ListABak : 集合A与集合B相同的元素
    			乍一看是不是非常高效快捷?
    			别急,请看后面的性能验证
    		*/
    		List<String> listABak = new ArrayList<>(listA); // 复制A集合作为备份
     		listB.removeAll(listA); // B集合与A集合的不同元素
            listABak.removeAll(listB); // A集合与B集合的相同元素
            listA.removeAll(listABak); // A集合与B集合的不同元素
    

    数量级为1000条数据性能如下(对比耗时单位全部为毫秒,后续不再赘述) ,还算正常
    在这里插入图片描述

    数量级为10000条数据性能如下,也还可以接受
    在这里插入图片描述

    数量级为100000条数据性能如下,这里就已经比较慢了

    在这里插入图片描述
    数据量100W,1000W的性能结果,我就不再贴出来了
    因为,100W的数据量,我跑了一下午没跑出来!!!
    按照这个效率,1000W估计能跑到年底~

    为什么在数据量增大的时候,这种方法性能下降的这么明显?
    我们不妨来看一下removeAll的源码:

    public boolean removeAll(Collection<?> c) {
            Objects.requireNonNull(c);
            boolean modified = false;
            Iterator<?> it = iterator();
            while (it.hasNext()) {
                if (c.contains(it.next())) {
                    it.remove();
                    modified = true;
                }
            }
            return modified;
        }
    

    通过源码我们可以看到,该方法是使用迭代器对集合进行遍历
    第一层迭代需要执行 listA.size()次,里面调用了contains方法来确定集合B是否含有该元素,
    再看contains方法的源码

    public boolean contains(Object o) {
            return indexOf(o) >= 0;
        }
    

    继续追踪:indexOf源码:

     public int indexOf(Object o) {
            if (o == null) {
                for (int i = 0; i < size; i++)
                    if (elementData[i]==null)
                        return i;
            } else {
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }
    

    可以看到,indexOf方法里又进行了一层遍历.
    平均每次遍历要进行listB.size() / 2次计算,
    假设集合A的元素个数为m,集合B的元素个数为n
    我们可以得到结论,运算次数为 m *(n/2)
    对于100W数据量来说,假设你的计算机每秒能够执行1千万次运算,
    也需要27.8个小时才能对比出来…
    所以大数据量时千万不要滥用该方法!!

    三. 笨比操作二 ---- 使用双层遍历比较不同

    	/*
    	该方法实际上就是将removeAll的实现逻辑用自己的方式写出来
    	所以执行效率,运行结果和上一种方法没什么区别,这里只贴代码出来,不再赘述
    	*/
        private static void stupidMethod2(List<String> listA, List<String> listB) {
            System.out.println("数量级为 " + listA.size() + "集合的不同元素为");
            List<String> differList = new ArrayList<>();
            long startTime = System.currentTimeMillis();
            for (String str : listB) {
                if (!listA.contains(str)) {
                    differList.add(str);
                }
            }
            traverse(differList);
            long endTime = System.currentTimeMillis();
            System.out.println("使用双层遍历方法 对比耗时: " + (endTime - startTime));
        }
    

    四.人类方法 ---- 借助Map集合找出不同

    该方法的总体思路为:
    以List集合里的元素作为Map的key,
    元素出现的次数作为Map的Value,
    那么两个List集合的不同元素为Map集合中value值为1,所对应的键.
    把所有value值为1的键找出来,我们就得到了两个List集合不同的元素
    代码如下:

    /**
         * 借助Map来获取listA、listB的不同元素集合
         *
         * @param listA 集合A
         * @param listB 集合B
         * @return list<String>
         */
        public static List<String> getDifferListByMap(List<String> listA, List<String> listB) {
            System.out.println("数量级为 " + listA.size() + "集合的不同元素为");
            List<String> differList = new ArrayList<>();
            Map<String, Integer> map = new HashMap<>();
            long beginTime = System.currentTimeMillis();
            for (String strA : listA) {
                map.put(strA, 1);
            }
            for (String strB : listB) {
                Integer value = map.get(strB);
                if (value != null) {
                    map.put(strB, ++value);
                    continue;
                }
                map.put(strB, 1);
            }
    
            for (Map.Entry<String, Integer> entry : map.entrySet()) {
                if (entry.getValue() == 1) { //获取不同元素集合
                    differList.add(entry.getKey());
                }
            }
            traverse(differList);
            long endTime = System.currentTimeMillis();
            System.out.println("使用map方式遍历, 对比耗时: " + (endTime - beginTime));
            return differList;
        }
    

    程序运行情况如下:

    集合元素个数为1000时:

    在这里插入图片描述

    集合元素个数为10000时,这里已经比上面的方法快不少了

    在这里插入图片描述

    集合元素个数为100000时,性能的提升显而易见

    在这里插入图片描述

    集合元素个数为1百万时,依然很快!

    在这里插入图片描述
    集合元素为1千万时,也只需要15S就能对比出结果

    在这里插入图片描述
    我们可以看到,使用map集合的方式寻找不同元素,时间增长基本上是线性的
    它的时间复杂度为O(m)
    而上面的remove方式和双层循环遍历的时间复杂度为O(m * n)
    所以,选用这种方式带来的性能收益随着集合元素的增长而增长

    全量代码分享

    以上实例中涉及到的全量代码如下:

    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    /**
     * @author xmr
     * @date 2020/3/5 8:18
     * @description
     */
    public class ListTest {
        public static void main(String[] args) {
            List<String> listA = dataList(10000000);
            List<String> listB = dataList(10000000 + 10);
            // stupidMethod(listA, listB);
            // stupidMethod2(listA, listB);
            getDifferListByMap(listA, listB);
        }
    
        private static void stupidMethod2(List<String> listA, List<String> listB) {
            System.out.println("数量级为 " + listA.size() + "集合的不同元素为");
            List<String> differList = new ArrayList<>();
            long startTime = System.currentTimeMillis();
            for (String str : listB) {
                if (!listA.contains(str)) {
                    differList.add(str);
                }
            }
            traverse(differList);
            long endTime = System.currentTimeMillis();
            System.out.println("使用双层遍历方法 对比耗时: " + (endTime - startTime));
        }
    
        /**
         * 遍历集合,打印出每个元素
         *
         * @param list List集合
         */
        private static void traverse(List<String> list) {
            for (String str : list) {
                System.out.print(str + " ");
            }
            System.out.println();
        }
    
        private static void stupidMethod(List<String> listA, List<String> listB) {
            System.out.println("数量级为 " + listA.size() + "集合的不同元素为");
            List<String> listABak = new ArrayList<>(listA); // 复制A集合作为备份
            long startTime = System.currentTimeMillis();
            listB.removeAll(listA); // B集合与A集合的不同元素
            traverse(listB);
            long endTime = System.currentTimeMillis();
            System.out.println("直接调用java api 方法 对比耗时: " + (endTime - startTime));
    //        listABak.removeAll(listB); // A集合与B集合的相同元素
    //        listA.removeAll(listABak); // A集合与B集合的不同元素
        }
    
        /**
         * 制造任意个元素的的List集合
         *
         * @param size List集合的size
         * @return List<String>
         */
        private static List<String> dataList(int size) {
            List<String> dataList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                dataList.add("" + i);
            }
            return dataList;
        }
    
    
        /**
         * 借助Map来获取listA、listB的不同元素集合
         *
         * @param listA 集合A
         * @param listB 集合B
         * @return list<String>
         */
        public static List<String> getDifferListByMap(List<String> listA, List<String> listB) {
            System.out.println("数量级为 " + listA.size() + "集合的不同元素为");
            List<String> differList = new ArrayList<>();
            Map<String, Integer> map = new HashMap<>();
            long beginTime = System.currentTimeMillis();
            for (String strA : listA) {
                map.put(strA, 1);
            }
            for (String strB : listB) {
                Integer value = map.get(strB);
                if (value != null) {
                    map.put(strB, ++value);
                    continue;
                }
                map.put(strB, 1);
            }
    
            for (Map.Entry<String, Integer> entry : map.entrySet()) {
                if (entry.getValue() == 1) { //获取不同元素集合
                    differList.add(entry.getKey());
                }
            }
            traverse(differList);
            long endTime = System.currentTimeMillis();
            System.out.println("使用map方式遍历, 对比耗时: " + (endTime - beginTime));
            return differList;
        }
    
    }
    
    

    一点思考

    如今,越来越多的公司在面试的时候考察程序员的数据结构与算法
    曾经,我也一度觉得面试造火箭,工作拧螺丝.. 认为通过这种方式选拔人才有失偏颇
    但实际上, 算法与数据结构,计算机基本知识这些基础性的东西,最能体现出功底和成长空间.
    功能是个人百度一下都能实现.
    但是实现的优雅,高效却是一门学问.
    在复杂的生产环境中,可能一行糟糕的代码实现给用户带来的是灾难级别的体验.
    因此,我们应该多问问自己代码这样写合不合适?
    对自己写的代码心存敬畏,对自己严格要求
    
    展开全文
  • 今天凯哥交给我一个任务,在报警模版中对比新旧两个数据,找出其中不同的部分,之前是把不同的数据转string做了对比,并没有对list中的对象做判断,修改完之后记录一下。list做对比,如果 list 里面的数据是乱序的,...

    今天凯哥交给我一个任务,在报警模版中对比新旧两个数据,找出其中不同的部分,之前是把不同的数据转string做了对比,并没有对list中的对象做判断,修改完之后记录一下。

    list做对比,如果 list 里面的数据是乱序的,需要对list排序。使用 Collections.sort()就可以了。但是list里面的对象不继承于comparable接口的话,要自己处理一下。方法就是实现接口,重写comparTo,我比较懒,就直接使用lambada的stream转string了。

    准备工作做完,接下来就要开始对比了,我的第一个版本就是使用list.removeIf( lambada... ),用另一个list做判断是否包含,并remove,最后合并。相当简单粗暴。上代码。

    ArrayList lst1 = new ArrayList<>(Arrays.asList("a","b","e"));

    ArrayList lst2 = new ArrayList<>(Arrays.asList("b","e","a"));

    Collections.sort(lst1);

    Collections.sort(lst2);

    if (lst1.equals(lst2)){

    }else{

    lst1.removeAll(lst2);

    lst1.addAll(lst2);

    System.out.println(Arrays.toString(lst1.toArray()));

    }

    后来要对list中的数据单独抽出来,只拿出不一样的数据,我只好改进了一下,因我的数据是有序的,所以跳过sort这一步,有新增/删除/修改,所以多一个map,对两个list的序号数据对比记录下来,然后再提取两个map的数据,根据key对应就可以啦。上代码。

    List changeField = new ArrayList<>();

    List finalLst1 = new ArrayList<>();

    List finalLst2 = new ArrayList<>();

    lst1.forEach(o -> finalLst1.add(Utils.objectToJson(o)));

    lst2.forEach(o -> finalLst2.add(Utils.objectToJson(o)));

    HashMap map1= new HashMap<>();

    HashMap map2= new HashMap<>();

    int minSize = finalLst1.size()

    for (int i = 0; i < minSize; i++) {

    if (!finalLst1.get(i).equals(finalLst2.get(i))){

    if (!finalLst2.contains(finalLst1.get(i))){

    map1.put(i,finalLst1.get(i));

    map2.put(i,finalLst2.get(i));

    }

    }

    }

    if (finalLst1.size()>finalLst2.size()){

    for (int i = minSize; i

    map1.put(i,finalLst1.get(i));

    }

    }else if (finalLst2.size()>finalLst1.size()){

    for (int i = minSize; i

    map2.put(i,finalLst2.get(i));

    }

    }

    for (Integer i : map1.keySet()) {

    if (map2.containsKey(i)){

    try {

    Map info1 = Utils.jsonToObject(map1.get(i),Map.class);

    Map info2 = Utils.jsonToObject(map2.get(i),Map.class);

    for (String s : info1.keySet()) {

    if (!info1.get(s).equals(info2.get(s))){

    changeField.add(new Change(field.getName()+"."+s, Utils.objectToJson(info1.get(s)),Utils.objectToJson(info2.get(s))));

    }

    }

    } catch (JsonSyntaxException e) { }

    }else{

    changeField.add(new Change(field.getName(), map1.get(i),"null"));

    }

    }

    for (Integer i : map2.keySet()) {

    if (!map1.containsKey(i)){

    changeField.add(new Change(field.getName(),"null",map2.get(i)));

    }

    }

    ==================chang类的声明 ======================

    private static class Change {

    String field;

    String before;

    String after;

    public Change(String field, String before, String after) {

    this.field = field;

    this.before = before;

    this.after = after;

    }

    @Override

    public String toString() {

    return "Change{" +

    "field='" + field + '\'' +

    ", before='" + before + '\'' +

    ", after='" + after + '\'' +

    '}';

    }

    }

    打完收工

    写博客也不费时间嘛,十来分钟搞定第一篇!加油啊⛽️!

    展开全文
  • 项目背景 刚好项目要快速对比两张表的不同数据,但是提供的是id的列表(list),另外在数据库中,所以这里想出...1、list1中有97277条数据,list2中有37894条数据,两个list进行对比找出不同的数据共60000条左右,用...

    项目背景

    刚好项目要快速对比两张表的不同数据,但是提供的是id的列表(list),另外在数据库中,所以这里想出了一个办法,先从数据库中找出有的数据in(sql)出来先,然后用代码匹对,因为这里要查出提供的id列表哪些是多余的数据,所以代码返回多余id的list

    结果:

    1、list1中有97277条数据,list2中有37894条数据,两个list进行对比找出不同的数据共60000条左右,用时:0.051秒

    2、list1中有97277条数据,list2中有97067条数据,两个list进行对比找出不同的数据共288条,用时:0.06秒

    下面的方法是对比两个list相互不同的数据

    也可以删除红色字的代码做成list1比list2多出多少数据

    public static List<String> getDiffrent(List<String> list1, List<String> list2){           
               Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size());
               List<String> diff = new ArrayList<String>();
               List<String> maxList = list1;
               List<String> minList = list2;
               if(list2.size()>list1.size()){
                   maxList = list2;
                   minList = list1;
               }
               
               for (String string : maxList){
                  map.put(string, 1);                    
               }
               
               for (String string : minList){
                   Integer cc = map.get(string);                    
                   if(cc!=null){
                       map.put(string, ++cc);
                       continue;                    
                   }           
                   map.put(string, 1);                    
               }
               
               for(Map.Entry<String, Integer> entry:map.entrySet()){                    
                   if(entry.getValue()==1)                    
                   {                    
                       diff.add(entry.getKey());                    
                   }                    
               }                               
               return diff;                    
        }

     

    有人回复说不行,我再补充main方法,(受不了不给测试方法就说不行的人)

    	public static void main(String[] args) {
    		
    		List<String> list1 =new ArrayList<String>();
    		for(int i=1;i<10;i++) {
    			list1.add(i+"");
    			
    		}
    		
    		List<String> list2 =new ArrayList<String>();
    		for(int i=5;i<10;i++) {
    			list2.add(i+"");		
    		}
    		List<String> list3 =getDiffrent(list1,list2);
    		List<String> list4 =getDiffrent(list2,list1);
    		
    		System.out.println(list1);
    		System.out.println(list2);
    		System.out.println("不同的值:"+list3);
    		System.out.println("不同的值:"+list4);
    		
    	}

    结果如图

     

    展开全文
  • 1、list1中有97277条数据,list2中有37894条数据,两个list进行对比找出不同的数据共60000条左右,用时:0.051秒 2、list1中有97277条数据,list2中有97067条数据,两个list进行对比找出不同的数据共288条,用时:...

    效率非常不错

    测试结果:

    1、list1中有97277条数据,list2中有37894条数据,两个list进行对比找出不同的数据共60000条左右,用时:0.051秒

    2、list1中有97277条数据,list2中有97067条数据,两个list进行对比找出不同的数据共288条,用时:0.06秒

    下面的方法是对比两个list相互不同的数据

    也可以删除红色字的代码做成list1比list2多出多少数据

    public static List<String> getDiffrent4(List<String> list1, List<String> list2) 
        {           
               Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size());
               List<String> diff = new ArrayList<String>();
               List<String> maxList = list1;
               List<String> minList = list2;
               if(list2.size()>list1.size())
               {
                   maxList = list2;
                   minList = list1;
               }
               
               for (String string : maxList) 
               {
                  map.put(string, 1);                    
               }
               
               for (String string : minList) 
               {
                   Integer cc = map.get(string);                    
                   if(cc!=null)                    
                   {
                       map.put(string, ++cc);
                       continue;                    
                   }           
                   map.put(string, 1);                    
               }
               
               for(Map.Entry<String, Integer> entry:map.entrySet())                    
               {                    
                   if(entry.getValue()==1)                    
                   {                    
                       diff.add(entry.getKey());                    
                   }                    
               }                               
               return diff;                    
        }

     

    展开全文
  • 项目背景刚好项目要快速对比两张表的不同数据,但是提供的是id的列表...所以代码返回多余id的list结果:1、list1中有97277条数据,list2中有37894条数据,两个list进行对比找出不同的数据共60000条左右,用时:0.05...
  • 今天凯哥交给我一个任务,在报警模版中对比新旧两个数据,找出其中不同的部分,之前是把不同的数据转string做了对比,并没有对list中的对象做判断,修改完之后记录一下。list做对比,如果 list 里面的数据是乱序的,...
  • 原先搞出来是 弄了两个List集合进行匹配代码就不贴了,说一下思路把 List list1=new ArrayList();//新数据 List list2=new ArrayList();//数据库数据 GongGl //公共类 如果list1>list2则说明有新数据,然后拿着...
  • 今天来比较一下两个list,然后分别找出相同元素和不同元素集合。先上一个简单示例:(注:因为测试数据量比较小,用ArrayList,如果涉及到百万数据的插入移除操作话,用LinkedList)[java] view plain copy&...
  • 在修改模块的时候 一条数据下有很多子数据,在进行修改的时候子数据也修改了(可能子...这时候就需要找出这批数据中 需要新增的,删除的,修改的数据 进行相应的操作。 public static void main(String[] args){ J.
  • 两个不同集合交集、并集及差集

    千次阅读 2019-05-17 15:46:45
    业务场景:现在给出这么一个需求,两个系统,旧系统与新系统同一个月中的数据,比对两个list找出不重复的数据,然后在进行校验。emmm......其实说通俗点,就是求两个集合的差集。 最初想法:循坏集合,判断另一个...
  • 1. 概述 查找相同数据类型的对象集合...在本篇文章中,我们将了解如何找出两个列表之间的差异。我们将尝试几种不同的方法,包括普通的Java(有和没有Streams),以及使用第三方库,如Guava和Apache Commons Collecti.
  •  JAVA平台提供了两个类:String和StringBuffer,它们可以储存和操作字符串,即包含多个字符字符数据。这个String类提供了数值不可改变字符串。而这个StringBuffer类提供字符串进行修改。当你知道字符数据要...
  • java面试考题

    2015-01-30 22:55:08
    抽象包括两个方面,一是过程抽象,二是数据抽象。 2)、封装(一个类包括多个属性及方法):是把过程和数据包围起来,对数据的访问只能通过已定义界面。即现实世界可被描绘成一系列完全自治、封装对象,这些对象通过...
  • java 面试题 总结

    2009-09-16 08:45:34
    JAVA平台提供了两个类:String和StringBuffer,它们可以储存和操作字符串,即包含多个字符字符数据。这个String类提供了数值不可改变字符串。而这个StringBuffer类提供字符串进行修改。当你知道字符数据要改变...
  • jsr80 java 访问 usb

    2015-02-14 08:52:01
    两个项目也都开始试图向其他操作系统上 Java 应用程序提供对 USB 设备访问,尽管它们都还没有开发可以使用包(参阅 参考资料 中有关本文中讨论两个项目及其他项目资料)。 在本文中,将对 jUSB 和 JSR...
  • JAVA面试题最全集

    2010-03-13 13:09:10
    找出下列代码可能存在错误,并说明原因: 二、JSP&Servlet技术 1.描述JSP和Servlet区别、共同点、各自应用范围 2.在Web开发中需要处理HTML标记时,应做什么样处理,要筛选那些字符(< > & “”) 3.在...
  • JAVA 正则表达式

    热门讨论 2010-01-15 11:16:37
    条件限制为 java 后除换行外任意两个字符 加入特定限制条件「[]」 [a-z] 条件限制在小写 a to z 范围中一个字符 [A-Z] 条件限制在大写 A to Z 范围中一个字符 [a-zA-Z] 条件限制在小写 a to z 或大写 A to Z ...

空空如也

空空如也

1 2 3 4
收藏数 71
精华内容 28
关键字:

java找出两个list不同的数据

java 订阅