两个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思想在海量数据处理中有很多妙用。
下面贴上具体实现的代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
| 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;
public class RetainAllTest {
public static void main(String[] args) {
retainAllByGuava();
retainAllByBitSet();
retainAllByTwoPoint();
retainAllByStream();
retainAllByJDK();
}
private static void retainAllByJDK() {
List<Integer> txtList = getIntegerList("e:\\a.txt");
List<Integer> 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());
}
private static void retainAllByGuava() {
List<Integer> txtList = getIntegerList("e:\\a.txt");
List<Integer> txtList2 = getIntegerList("e:\\b.txt");
long begin = System.currentTimeMillis();
Set<Integer> list = new HashSet<>(txtList);
Set<Integer> list2 = new HashSet<>(txtList2);
Sets.SetView<Integer> intersection = Sets.intersection(list, list2);
long end = System.currentTimeMillis();
System.out.println("guava方法耗时:" + (end - begin));
System.out.println("交集的个数为:" + intersection.size());
}
private static void retainAllByStream() {
List<Integer> txtList = getIntegerList("e:\\a.txt");
List<Integer> 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);
}
private static void retainAllByTwoPoint() {
List<Integer> txtList = getIntegerList("e:\\a.txt");
List<Integer> 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);
}
private static void retainAllByBitSet() {
List<Integer> txtList = getIntegerList("e:\\a.txt");
List<Integer> 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());
}
private static List<Integer> getIntegerList(String filePath) {
InputStream inputStream = null;
InputStreamReader is = null;
BufferedReader br = null;
Set<Integer> 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);
}
}
|
最终的运行结果如下，只运行了一次，结果并不严谨，仅供参考：
1
2
3
4
5
6
7
8
9
10
| 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://www.cnblogs.com/coderzhw/p/12150677.html
