java - 树结构递归如何优化？

Question

翻到祖师爷代码，发现树结构的数据是后端通过递归去生成的，效率非常低，请问有什么方法可以优化吗？

public List<Map> createGroupTreeNode() {
    List<Map> childrenList = new ArrayList<Map>();
    getChildList(0L,childrenList);
    List<Map> treeList = new ArrayList<Map>();
    Map map = new HashMap();
    map.put("id", 0);
    map.put("text","根节点");
    map.put("isleaf", "0");
    map.put("icon", "fa fa-folder");
    Map subMap = new HashMap();
    subMap.put("opened", true);
    subMap.put("selected", true);
    map.put("state", subMap);
    map.put("children", childrenList);
    treeList.add(map);
    return treeList;  
}

public List<Map> getChildList(Long id,List<Map> childrenList){
    List<BaseGroup> childList = baseMapper.childListByParentId(id);
    if(childList != null && childList.size() > 0){
        List<Map> tempMap = new ArrayList<Map>();
        for(int i = 0; i < childList.size(); i++){
            List<Map> mylist = getChildList(childList.get(i).getId(),childrenList);
            Map map = new HashMap();
            if(mylist == null){
                map.put("id", childList.get(i).getId());
                map.put("text", childList.get(i).getNumber() + " - " + childList.get(i).getName());
                map.put("isleaf", "1");
                map.put("icon", "fa fa-folder");
                Map subMap = new HashMap();
                subMap.put("opened", false);
                map.put("state", subMap);
                tempMap.add(map);
            }else{
                map.put("id", childList.get(i).getId());
                map.put("text", childList.get(i).getNumber() + " - " + childList.get(i).getName());
                map.put("isleaf", "0");
                map.put("icon", "fa fa-folder");
                map.put("children", mylist);
                Map subMap = new HashMap();
                subMap.put("opened", false);
                map.put("state", subMap);
                tempMap.add(map);
            }
            if(id == 0){
                childrenList.add(map);
            }
        }
        return tempMap;
    }
    return null;
}

Answer 1

没看出哪里效率低
只是觉得这人应该去写php

Answer 2

如果 baseMapper 是数据库查询的话的确性能会很差，但跟递归没关系。
可以一次性查询出数据库记录，在内存中递归组合。如果数据库记录较多，可以加path字段辅助查询收缩范围。

Answer 3

树状结构正确的处理方式是：使用缓存。

详细来说，初次使用的时候，用各种方法将树状结构生成出来，存为JSON格式的字符串。

后续直接读取这个JSON在前端渲染。

有人会说，如果数据更新了，那么这个缓存的就不能反映真实状况了。

所以，我们会先识别出影响树状结构源数据的所有入口，然后在入口触发这个JSON的更新。这样，就可以让JSON的更新不在每次访问的时候触发，可以减少频繁刷新导致的性能崩溃。

Answer 4

getChildList 的 childrenList 看起来是个输出参数，这里只有在 id == 0L 的时候会把元素加到 childrenList 中去。所以这个输入参数只在 id == 0L 的时候会使用。既然 getChildList 会把找到的列表返回出去，那完全不需要这个输出参数，在 createGroupTreeNode 里直接使用它的返回值就好。

public List<Map> createGroupTreeNode() {
    List<Map> childrenList = getChildList(0L);
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 不用初始化并作为输入参数传入，直接使用返回值就行
    // ....
}

public List<Map> getChildList(Long id) {
//                                   ^^^ 去掉 childrenList 参数
    
    // ...
    // if(id == 0){
    //     childrenList.add(map);
    // }
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 不需要了
}

总体来说，关于递归，就只有这一点问题。

然后在里面，for 循环中的循环变量 i 只有一个作用，就是 childList.get(i)，频繁的去使用 childList.get(i) 肯定不如缓存一个变量效率高，所以可以改为

for (int i = 0; i < childList.size(); i++) {
    BaseGroup it = childList.get(i);
    // 下面都用 it 代替 childList.get(i)
}

或者直接用增强 for 循环

 for (BaseGroup it : childList) {
     // ...
 }

另外在 for 循环中的 if 分支，比较一下发现只有一丁点区别，就是在处理 isleaf 和 children 的时候，所以可以把其他 .put 都提取出来，只处理有差异的部分

Map map = new HashMap();
map.put("id", it.getId());
// ...

List<Map> mylist = getChildList(it.getId());
// ^^^ 这句话后移到使用它的地方，不需要提前去取
//                 ^^^^^^^^^^^^^^^^^^^^^^^^ 没要第二个参数了，前面说过
if (mylist == null) {
    map.put("isleaf", "1");
}
else {
    map.put("isleaf", "0");
    map.put("children", mylist);
}