javascript list转tree，怎么优化

Question

export function list2Tree(data, parentId, children = "children", depth = 0) {
  let res = [];
  Array.isArray(data) &&
    data.forEach(item => {
      if (item.parentId === parentId) {
        let itemChildren = list2Tree(data, item.id, children, depth + 1);
        if (itemChildren.length) item[children] = itemChildren;
        res.push({
          ...item,
          depth
        });
      }
    });
  return res;
}

6000条数据时候需要 6350.08ms 多，有没有什么办法从算法层面优化一下的

Answer 1

以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：

// 原始 list 如下

let list =[
    {id:1,name:'部门A',parentId:0},
    {id:2,name:'部门B',parentId:0},
    {id:3,name:'部门C',parentId:1},
    {id:4,name:'部门D',parentId:1},
    {id:5,name:'部门E',parentId:2},
    {id:6,name:'部门F',parentId:3},
    {id:7,name:'部门G',parentId:2},
    {id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);

// 转换后的结果如下

let result = [
    {
      id: 1,
      name: '部门A',
      parentId: 0,
      children: [
        {
          id: 3,
          name: '部门C',
          parentId: 1,
          children: [
            {
              id: 6,
              name: '部门F',
              parentId: 3
            }, {
              id: 16,
              name: '部门L',
              parentId: 3
            }
          ]
        },
        {
          id: 4,
          name: '部门D',
          parentId: 1,
          children: [
            {
              id: 8,
              name: '部门H',
              parentId: 4
            }
          ]
        }
      ]
    },
  ···
];

转换方法如下：

function convert(list) {
    const res = []
    const map = list.reduce((res, v) => (res[v.id] = v, res), {})
    for (const item of list) {
        if (item.parentId === 0) {
            res.push(item)
            continue
        }
        if (item.parentId in map) {
            const parent = map[item.parentId]
            parent.children = parent.children || []
            parent.children.push(item)
        }
    }
    return res
}

Answer 2

这里用递归确实效率会有问题; 而且，你的代码对像不复用，很浪费
可以换个思路，两个循环解决树的问题。再加上遍历一次树算deep;

function array2Tree(arr) {
  let map = new Map();
  let _temp = arr.map((item) => {
    _item = { ...item };
    map.set(item.id, _item);
    return _item;
  });
  for (let i = 0; i < _temp.length; ) {
    let item = _temp[i];
    let { id, parentId } = item;
    let parent;
    if (parentId && (parent = map.get(parentId))) {
      parent.children ? parent.children.push(item) : (parent.children = [item]);
      _temp.splice(i, 1);
      continue;
    }
    i++;
  }
  function setDeep(arr, deep = 0) {
    arr.map((item) => {
      if (item.deep === undefined) {
        item.deep = deep;
        item.children && setDeep(item.children, deep + 1);
      }
    });
  }
  setDeep(_temp);
  return _temp;
}

function getArr(max) {
  let arr = [];
  for (let i = 0; i < max; i++) {
    arr.push({
      id: `id_${i}`,
      parentId:
        Math.random() > 0.1 ? "id_" + ((Math.random() * max) >> 0) : undefined,
    });
  }
  //   return arr;
  return arr.sort(() => (Math.random() > 0.5 ? 1 : -1));
}

var arr = getArr(5000);
// console.log(arr);
console.time("list2Tree");
var _arr = list2Tree(arr);
console.timeEnd("list2Tree");
console.log(_arr);

console.time("array2Tree");
var __arr = array2Tree(arr);
console.timeEnd("array2Tree");
console.log(__arr);

Answer 3

这样更快哟~

function toMap(arr) {
  const result = arr.reduce((acc, current) => {
    acc[current.id] = current
    return acc
  }, {})
  return result
}

function formatListToTree(arr) {
  const map = toMap(arr)
  return arr.reduce((acc, current) => {
    const { id, parentId } = current
    if (map[parentId]) {
      map[parentId].children = map[parentId].children || []
      map[parentId].children.push(current)
    } else {
      acc.push(current)
    }

    return acc
  }, [])
}

Answer 4

先看结果

6,000 条

make tree by list2tree: 318.529ms
make tree by makeTree: 7.566ms

60,000 条

make tree by list2tree: 17.498s
make tree by makeTree: 106.406ms

再看代码

• generate 用来生成数据
• list2tree 是题主的，用的递归
• makeTree 是我写的 ，用的 HashMap 缓存节点

function generate(count = 6000) {
    return Array.from(Array(count), (_, i) => ({
        id: i + 1,
        parentId: Math.floor(Math.random() * (i + 1))
    }));
}

export function list2Tree(data, parentId, children = "children", depth = 0) {
    let res = [];
    Array.isArray(data) &&
        data.forEach(item => {
            if (item.parentId === parentId) {
                let itemChildren = list2Tree(data, item.id, children, depth + 1);
                if (itemChildren.length) item[children] = itemChildren;
                res.push({
                    ...item,
                    depth
                });
            }
        });
    return res;
}

function makeTree(data, children = "children") {
    const root = { depth: -1, [children]: [] };
    const nodeMap = {};
    data.forEach(it => {
        const { id, parentId } = it;
        const parent = nodeMap[parentId] ?? root;
        const node = { ...it, depth: parent.depth + 1 };
        parent.children ??= [];
        parent.children.push(node);
        nodeMap[id] = node;
    });
    return root;
}

const data = generate(60000);

console.time("make tree by list2tree");
list2Tree(data, 0);
console.timeEnd("make tree by list2tree");

console.time("make tree by makeTree");
makeTree(data);
console.timeEnd("make tree by makeTree");

// console.log(JSON.stringify(tree1, null, 2));
// console.log(JSON.stringify(tree2, null, 2));

再补充一下

6000 个节点一次性渲染出来……要不考虑一下动态加载（动态渲染），展开一层渲染一层

---

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入。

Answer 5

你的代码里最大的问题在于，每次都是循环全部数据，并在其中，找到指定pid的数据
这样循环的次数会非常非常多，所以代码的时间消耗会很大
比较好的方式，可以通过两次循环搞定
第一次循环的目的是构建主键和数据的映射
第二次根据pid，在映射中查找数据，找到则为子节点，未找到或pid为null/""，则为根节点

/**
 * 树形数据生成配置
 * */
interface GenerateTreeOption {
  /**
   * 返回对象中的父节点属性key，locales,null,"" 则不设置父节点属性
   * */
  parentNodeKey?: string;
  /**
   * 数组转map对象，生成树节点时，可同时，将列表数据放入map中
   * */
  mapCache?: any;
  /**
   * 对象id属性key 默认为 id
   * */
  idKey?: string;
  /**
   * 对象父节点id属性key，默认为 parent
   * */
  parentKey?: string;
  /**
   * 子节点属性key，默认为 children
   * */
  childrenKey?: string;
  /**
   * 结果写入对象
   * */
  result?: any[];
  /**
   * 遍历时，每个对象调用，设置对象使用
   * */
  loop?: (item: any) => void;
}

/**
   * 生成树型数据
   * @param data 列表数据
   * @param config 生成配置
   * */
  function generateTree (data: any[], config?: GenerateTreeOption): any[] {
    const parentNodeKey = config ? config.parentNodeKey : null
    const result = config ? config.result || [] : []
    const mapCache = config ? config.mapCache || {} : {}
    const idKey = config ? config.idKey || 'id' : 'id'
    const parentKey = config ? config.parentKey || 'parent' : 'parent'
    const childrenKey = config ? config.childrenKey || 'children' : 'children'
    const itemLoop = config ? config.loop || (() => undefined) : () => undefined

    data.forEach((item) => {
      mapCache[item[idKey]] = item
    })
    data.forEach((item) => {
      itemLoop(item)
      const cacheParentKey = item[parentKey]
      if (cacheParentKey) {
        if (mapCache[cacheParentKey]) {
          if (!mapCache[cacheParentKey][childrenKey]) {
            mapCache[cacheParentKey][childrenKey] = []
          }
          mapCache[cacheParentKey][childrenKey].push(item)
          if (parentNodeKey) {
            item[parentNodeKey] = mapCache[cacheParentKey]
          }
        } else { // 如果当前节点的父节点id未找到指定对象，则当前对象作为根节点的自己节点
          result.push(item)
        }
      } else {
        result.push(item)
      }
    })
    return result
  }