code review 发现同事写的双层for循环，优化完耗时节省90%

墨蓝 2023-10-13 13:33 34阅读 0赞

在两份表里找相同id的数据，很多同学会写两个for循环嵌套。这个写法效率比较低，今天来看一个提高速度的优化案例。

本篇分析的技巧点其实是比较常见的，但是最近的几次的代码评审还是发现有不少兄弟没注意到。所以还是想拿出来说下。

是个什么场景呢？就是 for循环 里面还有 for循环， 然后做一些数据匹配、处理 这种场景。

我们结合实例代码来看看。场景示例：

比如我们现在拿到两个list 数据 ，一个是 User List 集合 ；另一个是 UserMemo List集合；

我们需要遍历 User List ，然后根据 userId 从 UserMemo List 里面取出 对应这个userId 的 content 值，做数据处理。

代码 User.java ：

@Data
    public class User {
        private Long userId;
        private String name;
    }

代码 UserMemo.java ：

@Data
    public class UserMemo {
        private Long userId;
        private String content;
    }

模拟数据集合 ：5W 条 user 数据 ， 3W条 userMemo数据

public static List<User> getUserTestList() {
            List<User> users = new ArrayList<>();
            for (int i = 1; i <= 50000; i++) {
                User user = new User();
                user.setName(UUID.randomUUID().toString());
                user.setUserId((long) i);
                users.add(user);
            }
            return users;
        }
     
        public static List<UserMemo> getUserMemoTestList() {
            List<UserMemo> userMemos = new ArrayList<>();
            for (int i = 30000; i >= 1; i--) {
                UserMemo userMemo = new UserMemo();
                userMemo.setContent(UUID.randomUUID().toString());
                userMemo.setUserId((long) i);
                userMemos.add(userMemo);
            }
            return userMemos;
        }

先看平时大家不注意的时候可能会这样去写代码处理 ：

![531f7c86db0f6f86d9d68df567e0569d.png][]

其实数据量小的话，其实没多大性能差别，不过我们还是需要知道一些技巧点。我们来看看 这时候的一个耗时情况 。

相当于迭代了 5W \* 3W 次 ，可以看到用时 是 26857毫秒 ：

![4a21693611f0c9f019f18d16016ba663.png][]

其实到这，插入个题外点，如果说每个userId 在 UserMemo List 里面 都是只有一条数据的场景。

for (User user : userTestList) {
        Long userId = user.getUserId();
        for (UserMemo userMemo : userMemoTestList) {
            if (userId.equals(userMemo.getUserId())) {
                String content = userMemo.getContent();
                System.out.println("模拟数据content 业务处理......"+content);
            }
        }
    }

单从这段代码有没有问题 ，有没有优化点。显然是有的， 因为当我们从内循环UserMemo List里面找到匹配数据的时候， 没有做其他操作了。

这样内for循环会继续下，直到跑完再进行下一轮整体循环。所以，仅针对这种情形，1对1的或者说我们只需要找到一个匹配项，处理完后我们 应该使用 break 。

我们来看看加上 break 的一个耗时情况 ：

![a1d43651d772045705863ebda7fc850a.png][]

耗时情况：可以看到 从 2W 多毫秒 变成了 1W 多毫秒， 这个break 加的很OK。

![6d625d4b64d70200940f888cc4f2aab2.png][]

回到我们刚才, 平时需要for 循环里面再 for 循环 这种方式，可以看到耗时是 2万6千多毫秒。

那如果场景更复杂一定， 是for 循环里面 for循环 多个或者， for循环里面还有一层for 循环 ，那这样代码耗时真的非常恐怖。

那么接下来这个技巧点是使用map 去优化 ：

![5f560e42027c2d1e7f6768645084784a.png][]

代码：

public static void main(String[] args) {
            List<User> userTestList = getUserTestList();
            List<UserMemo> userMemoTestList = getUserMemoTestList();
     
     
            StopWatch stopWatch = new StopWatch();
            stopWatch.start();
            //使用stream() 记得一定要判空 这里没列出来，大家自己注意
            Map<Long, String> contentMap =
                    userMemoTestList.stream().collect(Collectors.toMap(UserMemo::getUserId, UserMemo::getContent));
     
            for (User user : userTestList) {
                Long userId = user.getUserId();
                String content = contentMap.get(userId);
     
                if (StringUtils.hasLength(content)) {
                    System.out.println("模拟数据content 业务处理......" + content);
                }
     
            }
     
            stopWatch.stop();
            System.out.println("最终耗时" + stopWatch.getTotalTimeMillis());
     
     
        }

看看耗时:

![2cb9ee32bf48ad7018e8221bd1caf693.png][]

为什么效果这么显著？

这其实就是时间复杂度，for循环嵌套for循环，就好比 循环每一个 user ，拿出 userId 需要在里面的循环从 userMemo list集合里面 按顺序去开盲盒匹配,拿出第一个，看看userId ，拿出第二个，看看userId ，一直找匹配的。

而我们提前对 userMemo list集合 做一次 遍历，转存储在map里面 。

map的取值效率 在多数的情况下是能维持接近 O（1） 的 ， 毕竟数据结构摆着，数组加链表。

相当于拿到userId 想去开盲盒的时候， 根据userId 这个key hash完能直接找到数组里面的索引标记位， 如果底下没链表（有的话O(logN)），直接取出来就完事了。

![513aca89f01bb0978a90fbf0b1aeb961.png][]

按照目前以JDK8 的hash算法，起hash冲突的情况是非常非常少见了。

最恶劣的情况，只有当 全部key 都冲突， 全都分配到一个桶里面去都占用一个位置 ，这时候就是O（n），这种情景不需要去考虑。

[531f7c86db0f6f86d9d68df567e0569d.png]: https://img-blog.csdnimg.cn/img_convert/531f7c86db0f6f86d9d68df567e0569d.png
[4a21693611f0c9f019f18d16016ba663.png]: https://img-blog.csdnimg.cn/img_convert/4a21693611f0c9f019f18d16016ba663.png
[a1d43651d772045705863ebda7fc850a.png]: https://img-blog.csdnimg.cn/img_convert/a1d43651d772045705863ebda7fc850a.png
[6d625d4b64d70200940f888cc4f2aab2.png]: https://img-blog.csdnimg.cn/img_convert/6d625d4b64d70200940f888cc4f2aab2.png
[5f560e42027c2d1e7f6768645084784a.png]: https://img-blog.csdnimg.cn/img_convert/5f560e42027c2d1e7f6768645084784a.png
[2cb9ee32bf48ad7018e8221bd1caf693.png]: https://img-blog.csdnimg.cn/img_convert/2cb9ee32bf48ad7018e8221bd1caf693.png
[513aca89f01bb0978a90fbf0b1aeb961.png]: https://img-blog.csdnimg.cn/img_convert/513aca89f01bb0978a90fbf0b1aeb961.png