• 中文
    • English
  • 注册
  • 查看作者
  • Java高效找出两个大数据量List集合中的不同元素

    本文将带你了解如何快速的找出两个相似度非常高的List集合里的不同元素。主要通过Java API、List集合双层遍历比较不同、借助Map集合查找三种方式,以及他们之间的执行效率情况,话不多说,开搞!集合初始化方法:

    测试数据为集合A: 1千, 1万, 10万,1百万, 1千万的数据量.

    • 集合B比集合A多初始化六条数据,集合A添加一条特有的数据。

    • 测试数据使用空字符串 + 自然数的方式。

    JavaAPI过滤(不推荐)

    1千数据量

    耗时:22毫秒

    Java高效找出两个大数据量List集合中的不同元素

    1万数据量

    耗时:613毫秒

    Java高效找出两个大数据量List集合中的不同元素

    10万数据量

    Java高效找出两个大数据量List集合中的不同元素

    可以看出来十万数据量级别已经比较慢了,需要77秒

    100万数据量

    emmm估计挺慢,不继续验证了。😂😂😂

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

    Java高效找出两个大数据量List集合中的不同元素

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

    Java高效找出两个大数据量List集合中的不同元素

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

    Java高效找出两个大数据量List集合中的不同元素

    List集合双层遍历比较不同(不推荐)

    该方法实际上就是将removeAll的实现逻辑用自己的方式写出来,所以执行效率,运行结果和上一种方法没什么区别,这里只贴代码出来,不再赘述。

    🎨以上两个方法中我都做了m*n次循环,其实完全没有必要循环这么多次,我们的需求是找出两个List中的不同元素,那么我可以这样考虑:用一个map存放lsit的所有元素,其中的key为lsit1的各个元素,value为该元素出现的次数,接着把list2的所有元素也放到map里,如果已经存在则value加1,最后我们只要取出map里value为1的元素即可,这样我们只需循环m+n次,大大减少了循环的次数。

    借助Map集合查找(推荐✅)

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

    1千数据量

    耗时:7毫秒

    Java高效找出两个大数据量List集合中的不同元素

    1万数据量

    耗时:42毫秒

    Java高效找出两个大数据量List集合中的不同元素

    10万数据量

    耗时:130毫秒

    Java高效找出两个大数据量List集合中的不同元素

    100万数据量

    耗时:283毫秒

    Java高效找出两个大数据量List集合中的不同元素

    1000万数据量

    耗时:6.6秒

    Java高效找出两个大数据量List集合中的不同元素

    可以看出来这种方法相当高效,千万级数据比对也才用了6.6秒。使用map集合的方式寻找不同元素,时间增长基本上是线性的,它的时间复杂度为O(m)。而上面的remove方式和双层循环遍历的时间复杂度为O(m * n)。所以,选用这种方式带来的性能收益随着集合元素的增长而增长。

    优化

    上述通过map集合的方式效率很高,有没有可以优化的点呢?

    1. 两个集合如果数量差距较大时,可以把小的在后面添加,这样会减少循环里的判断,性能又有了一定的提升。

    2. 创建map集合的时候直接指定大小,防止再散列。

    优化后代码如下:

    找出相同元素

    同样找出相同元素可以使用如下代码:

  • 0
  • 0
  • 0
  • 49
  • 请登录之后再进行评论

    登录
  • 任务
  • 实时动态
  • 发布
  • 单栏布局 侧栏位置: