for 循环嵌套 for 循环,你需要懂的代码性能优化技巧!

发布一下 0 0

前言

本篇分析的技巧点其实是比较常见的,但是最近的几次的代码评审还是发现有不少兄弟没注意到。

所以还是想拿出来说下。

正文

是个什么场景呢?

就是 for循环 里面还有 for循环, 然后做一些数据匹配、处理 这种场景。

我们结合实例代码来看看。

场景示例:

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

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

代码 User.java :

import lombok.Data; @Datapublic class User {    private Long userId;    private String name;}

代码 UserMemo.java :

import lombok.Data; @Datapublic 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;}

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

for 循环嵌套 for 循环,你需要懂的代码性能优化技巧!

ps:其实数据量小的话,其实没多大性能差别,不过我们还是需要知道一些技巧点。

代码:

public static void main(String[] args) {    List<User> userTestList = getUserTestList();    List<UserMemo> userMemoTestList = getUserMemoTestList();    StopWatch stopWatch = new StopWatch();    stopWatch.start();    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);            }        }    }    stopWatch.stop();    System.out.println("最终耗时"+stopWatch.getTotalTimeMillis());}

我们来看看 这时候的一个耗时情况 :

相当于迭代了 5W * 3W

可以看到用时 是 26857毫秒

for 循环嵌套 for 循环,你需要懂的代码性能优化技巧!

其实到这,插入个题外点,如果说每个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 的一个耗时情况 :

for 循环嵌套 for 循环,你需要懂的代码性能优化技巧!

代码:

public static void main(String[] args) {    List<User> userTestList = getUserTestList();    List<UserMemo> userMemoTestList = getUserMemoTestList();    StopWatch stopWatch = new StopWatch();    stopWatch.start();    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);                break;            }        }    }    stopWatch.stop();    System.out.println("最终耗时"+stopWatch.getTotalTimeMillis());}

耗时情况:

可以看到 从 2W 多毫秒 变成了 1W 多毫秒, 这个break 加的很OK。

for 循环嵌套 for 循环,你需要懂的代码性能优化技巧!

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

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

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

for 循环嵌套 for 循环,你需要懂的代码性能优化技巧!

代码:

public static void main(String[] args) {    List<User> userTestList = getUserTestList();    List<UserMemo> userMemoTestList = getUserMemoTestList();    StopWatch stopWatch = new StopWatch();    stopWatch.start();    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());}

看看耗时:

for 循环嵌套 for 循环,你需要懂的代码性能优化技巧!

为什么 这么显著的效果 ?

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

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

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

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

for 循环嵌套 for 循环,你需要懂的代码性能优化技巧!

然后补充一个getNode的代码注释 :

    /**     * Implements Map.get and related methods.     * 这是个 Map.get 的实现 方法     * @param hash hash for key     * @param key the key     * @return the node, or null if none     *///    final 写死了 无法更改 返回 Node 传入查找的 hash 值 和 key键    final Node<K,V> getNode(int hash, Object key) {//        tab 还是 哈希表//        first 哈希表找的链表红黑树对应的 头结点//        e 代表当前节点//        k 代表当前的 key        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//        赋值 并过滤 哈希表 空的长度不够的 对应位置没存数据的 都直接 return null        if ((tab = table) != null && (n = tab.length) > 0 &&            (first = tab[(n - 1) & hash]) != null) {//            头结点就 找到了 hash相等值相等 或者 不空的 key 和当前节点 equals            if (first.hash == hash && // always check first node                ((k = first.key) == key || (key != null && key.equals(k))))                return first;//            头结点不匹配 没找到就 就用 next 找            if ((e = first.next) != null) {//                是不是红黑树 的                if (first instanceof TreeNode)                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);//                红黑树就直接 调用 红黑树内查找 //                不为空或者没找到就do while 循环                do {//                    当前节点 找到了 hash相等值相等 或者 不空的 key 和当前节点 equals                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        return e;                } while ((e = e.next) != null);            }        }        return null;    }

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

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

原文链接;https://mp.weixin.qq.com/s/Yo_k5B9j6nbK1_o3fn-6TA

版权声明:内容来源于互联网和用户投稿 如有侵权请联系删除

本文地址:http://0561fc.cn/204590.html