| Java大集合求交集的方法比较 | 您所在的位置：网站首页 › Java两个list取差集方法 › Java大集合求交集的方法比较 |
|
两个List集合求交集想必学过Java的都知道用系统自带的retainAll()方法，但是在数据量比较大时，这个方法效率并不高，利用空余时间研究了几种数据量较大时求两个集合交集的办法。本文主要研究了JDK自带方法求交集、Guava集合求交集、Java8的parallelStream并行流求交集、双指针方法求交集以及bitmap求交集的方法和效率。 JDK自带方法最常用的求交集方法，在小数据量的时候没什么问题，一旦两个集合的数据量达到几十万级别时，效率就严重偏低，底层实际上也是两个for循环加一个contains判断，只不过JDK做了一些相应优化，不是单纯O(n^2)的双重for循环，感兴趣的同学可以阅读相应源码。 Guava集合工具类Guava是谷歌出的一个工具类，里面包含了很多实用的方法，求交集的方法为Sets.intersection(list, list2)实际测试下来相当高效。 Java8并行流parallelStream()借用了Java7的Fork/Join框架，采用分治+多线程的思想来求交集 双指针法双指针法又称拉链法，就是先将两个集合排序，然后借用了二路归并排序的思想，利用两个指针分别在两个集合里面做标记，比较大小然后滑动，最后得到结果。 BitMap方法将数据存进两个bitMap中，然后进行与操作，得到最终结果，属于一种空间换时间的方法，BitMap思想在海量数据处理中有很多妙用。 下面贴上具体实现的代码: package com.test.spring.learn.retainall; import com.google.common.collect.Sets; import org.apache.commons.lang3.StringUtils; import java.io.*; import java.util.*; import java.util.stream.Stream; import static java.util.stream.Collectors.toList; /** * Created by GeekBoy on 2020/1/4. */ public class RetainAllTest { public static void main(String[] args) { retainAllByGuava(); retainAllByBitSet(); retainAllByTwoPoint(); retainAllByStream(); retainAllByJDK(); } /** * 用JDK方法求交集 */ private static void retainAllByJDK() { List txtList = getIntegerList("e:\\a.txt"); List txtList2 = getIntegerList("e:\\b.txt"); long begin = System.currentTimeMillis(); txtList.retainAll(txtList2); long end = System.currentTimeMillis(); System.out.println("JDK方法耗时:" + (end - begin)); System.out.println("交集的个数为:" + txtList.size()); } /** * 利用guava集合求交集 */ private static void retainAllByGuava() { List txtList = getIntegerList("e:\\a.txt"); List txtList2 = getIntegerList("e:\\b.txt"); long begin = System.currentTimeMillis(); Set list = new HashSet(txtList); Set list2 = new HashSet(txtList2); Sets.SetView intersection = Sets.intersection(list, list2); long end = System.currentTimeMillis(); System.out.println("guava方法耗时:" + (end - begin)); System.out.println("交集的个数为:" + intersection.size()); } /** * java8 stream流求交集，实质上底层是用的多线程fork/join框架 */ private static void retainAllByStream() { List txtList = getIntegerList("e:\\a.txt"); List txtList2 = getIntegerList("e:\\b.txt"); long begin = System.currentTimeMillis(); long count = txtList.parallelStream(). filter(item -> txtList2.contains(item)).count(); long end = System.currentTimeMillis(); System.out.println("stream流求交集方法耗时:" + (end - begin)); System.out.println("交集的个数为:" + count); } /** * 双指针法求两个list的交集 */ private static void retainAllByTwoPoint() { List txtList = getIntegerList("e:\\a.txt"); List txtList2 = getIntegerList("e:\\b.txt"); long begin = System.currentTimeMillis(); Collections.sort(txtList); Collections.sort(txtList2); int count = 0; int m = 0; int n = 0; int length = txtList.size() + txtList2.size(); for (int i = 0; i < length; i++) { if (m < txtList.size() && n < txtList2.size()) { if (txtList.get(m).equals(txtList2.get(n))) { count++; m++; n++; } else if (txtList.get(m).compareTo(txtList2.get(n)) > 0) { n++; } else { m++; } } else if (m < txtList.size()) { if (txtList.get(m).equals(txtList2.get(n - 1))) { count++; } m++; } else if (n < txtList2.size()) { if (txtList.get(m - 1).equals(txtList2.get(n))) { count++; } n++; } } long end = System.currentTimeMillis(); System.out.println("双指针方法耗时:" + (end - begin)); System.out.println("交集的个数为:" + count); } /** * 利用bitmap求两个list的交集 */ private static void retainAllByBitSet() { List txtList = getIntegerList("e:\\a.txt"); List txtList2 = getIntegerList("e:\\b.txt"); long begin = System.currentTimeMillis(); BitSet bitSet = new BitSet(Collections.max(txtList)); BitSet bitSet1 = new BitSet(Collections.max(txtList2)); for (int i = 0; i < txtList.size(); i++) { bitSet.set(txtList.get(i)); } for (int i = 0; i < txtList2.size(); i++) { bitSet1.set(txtList2.get(i)); } bitSet.and(bitSet1); long end = System.currentTimeMillis(); System.out.println("bitSet方法耗时:" + (end - begin)); System.out.println("交集的个数为:" + bitSet.cardinality()); } /** * 从文件读取两个list * * @param filePath * @return */ private static List getIntegerList(String filePath) { InputStream inputStream = null; InputStreamReader is = null; BufferedReader br = null; Set txtList = new HashSet(); try { File txtFile = new File(filePath); if (txtFile.exists()) { inputStream = new FileInputStream(txtFile); is = new InputStreamReader(inputStream, "UTF-8"); br = new BufferedReader(is); String str = null; while ((str = br.readLine()) != null) { if (StringUtils.isNotBlank(str)) { txtList.add(Integer.valueOf(str)); } } } } catch (Exception e) { e.printStackTrace(); } finally { try { if (inputStream != null) { inputStream.close(); } if (is != null) { is.close(); } if (br != null) { br.close(); } } catch (Exception e) { e.printStackTrace(); } } return new ArrayList(txtList); } }最终的运行结果如下，只运行了一次，结果并不严谨，仅供参考： guava方法耗时:33 交集的个数为:151695 bitSet方法耗时:25 交集的个数为:151695 双指针方法耗时:63 交集的个数为:151695 stream流求交集方法耗时:28240 交集的个数为:151695 JDK方法耗时:91838 交集的个数为:151695从上面的结果可以看出bieSet是最快的，guava的方法其次，JDK自带的最慢。平时使用如果数据量不是太大用guava的工具类即可，不得不说谷歌的算法还是相当厉害的。 参考链接https://blog.csdn.net/banpeng4018/article/details/101386744 镜像地址https://blog.codage.info/post/java-list-compare.html |
| CopyRight 2018-2019 实验室设备网 版权所有 |