还在用双层for循环吗？太慢了
2024-09-08 13:28:42
前情提要
我们在开发中经常碰到这样的场景，查出两个 list 集合数据，需要根据他们相同的某个属性为连接点，进行聚合。但是平时我们使用的时候关注过性能吗？下面让我们一起来看看它的表现如何。
来个例子
我们现在有两个 List集合，需要根据他们相同的 personId 进行聚合处理，我们很容易想到的写法是这样的：
private static void test1(List<Person> list1, List<Person> list2) {
for (Person before:list1){
for (Person after:list2){
if(before.getPersonId().equals(after.getPersonId())){
//TODO 业务逻辑
break;
}
}
}
}
这样的代码是我们开发中最常用的一种方式，数据少的话没问题。如果数据量大的会很慢，接下来我做一个实验。看看在 1w 和 10w 的数据量下他的性能如何？
测试代码如下：
public static void main(String[] args) {
List<Person> list1= new ArrayList<>();
List<Person> list2= new ArrayList<>();
for (int i = 0; i < 10_0000; i++) {
list1.add(Person.builder().personId(Long.valueOf(i+"")).build());
list2.add(Person.builder().personId(Long.valueOf(i+"")).build());
}
long start = System.currentTimeMillis();
test1(list1, list2);
System.out.println("for循环耗时："+(System.currentTimeMillis()-start));
1w 耗时：343
10w 耗时：64285
仅仅 10w 的数据竟然达到了 64 秒多，可以看出它的性能是多么差了吧。
那怎么优化呢？我们可以把第二个 list 转为 map 的方式来做，示例如下：
代码如下：
private static void test2(List<Person> list1, List<Person> list2) {
Map<Long, Person> baseMap =
list2.stream().collect(Collectors.toMap(Person::getPersonId, Function.identity()));
for (Person before:list1){
Person after = baseMap.get(before.getPersonId());
}
}
接下来我们再进行下性能测试。
1w 耗时：88
10w 耗时：95
可以看出速度快了上百倍不止，如果还有小伙伴用第一种方式的话就赶紧优化了吧。
思考
我们想想第一种为什么会慢呢？
在第二个循环里他需要从 0 开始遍历所有的元素来进行比对，数据量越大，它需要遍历的数就越多，所以很慢。
所以如果我们业务上两个集合的大小和顺序一致（即能知道应该第二个循环能匹配上的元素在第几个)，那么就能避免掉大量的循环。
示例如下：
我们直接在第二层循环的时候，将下标先指定为和第一层循环的一致，如果他们俩属性相同，立马跳出；进行第二次循环。
private static void test3(List<Person> list1, List<Person> list2) {
for (int i=0;i<list1.size();i++){
int jj = 0;
for (int j = i; j < list2.size(); j++) {
if (jj == list2.size()) {
break;
}
if(list1.get(i).getPersonId().equals(list2.get(j).getPersonId())){
// 编写具体的逻辑
break;
}
if (j == list2.size() - 1) j = -1;
jj += 1;
}
}
}
性能测试如下：
1w 耗时：2
10w 耗时：13
我们发现又更加快了。
下面是总体的测试数据：
| 数据量 | 双层 for 循环 | 循环+map | 改良版 for 循环 |
|---|---|---|---|
| 100 条数据 | 1 毫秒 | 70 毫秒 | <1 毫秒 |
| 1000 条数据 | 16 毫秒 | 91 毫秒 | 1 毫秒 |
| 5000 条数据 | 66 毫秒 | 66 毫秒 | 3 毫秒 |
| 1w 条数据 | 208 毫秒 | 64 毫秒 | 4 毫秒 |
| 10w 条数据 | 62887 毫秒 | 84 毫秒 | 17 毫秒 |
| 100w 条数据 | 很久 | 155 毫秒 | 24毫秒 |
总结：如果数据量小于 5000，推荐就用双层 for 循环，如果大于 5000，则使用循环+map 的方式。
如果两个集合顺序一致，则可以用改良版的 for 循环
最新文章
- Usage: AddDimensionedImage imageFile outputFile eclipse 运行程序出错
- 获取oracle 里的表名与字段
- Project Euler problem 61
- Java-设计模式-单例模式-饿汉模式、懒汉模式
- iOS 调试 之 打印
- Scrum Meeting Alpha - 6
- Java 8时间和日期API 20例
- python学习日记（面向对象——继承）
- go 源码学习之---Tail 源码分析
- PHP（表单元素）
- 201621123075作业07-Java GUI编程
- 启动mysqld报 mysql the server quit without updating pid file
- url传输编码
- express-session 产生的警告问题
- smbpasswd 和 pdbedit 的区别
- Html5与Css3知识点拾遗（二）
- js 之 this call apply
- Linux下端口被占用确认
- 【BZOJ】【3931】【CQOI2015】网络吞吐量
- Java按钮控件数组实现计算器界面