
本文共 13392 字,大约阅读时间需要 44 分钟。
前言
前段时间,由于业务需求,需要把后端返回的扁平化的数组结构,转换成树形结构,以适应于前端多级菜单栏的渲染,一开始查阅了一些资料,但发现并不是自己想要的答案。为了得到自己最想要的结果,特地花了时间对该问题进行了一些探究性尝试,并对探究过程和结果进行记录。希望能给遇到相同问题的人提供一些参考。
原始的数据结构如下:
// id为当前菜单的唯一标识// parentId 为上级父类菜单标识// name为菜单名// 后端返回的数据级数具有不确定性,即可能有1/2/3/4级等,data集合的个数具有不确定性,即可能有10个、8个等。let dataJSONArray = [ { id: 1, parentId: 0, name: "菜单1" }, { id: 2, parentId: 0, name: "菜单2" }, { id: 3, parentId: 0, name: "菜单3" }, { id: 4, parentId: 1, name: "菜单4" }, { id: 5, parentId: 1, name: "菜单5" }, { id: 6, parentId: 2, name: "菜单6" }, { id: 7, parentId: 4, name: "菜单7" }, { id: 8, parentId: 7, name: "菜单8" }, { id: 9, parentId: 8, name: "菜单9" }, { id: 10, parentId: 9, name: "菜单10" }, { id: 11, parentId: 10, name: "菜单11" }, { id: 12, parentId: 11, name: "菜单12" }, { id: 13, parentId: 12, name: "菜单13" }, { id: 14, parentId: 13, name: "菜单14" }, // 此处省略后面的内容了,可能还有多个........];
目标数据结构如下:
let result = [ { id: 1, name: "菜单1", parentId: 0, chilren: [ { id: 4, name: "菜单4", parentId: 1, chilren: [ { id: 7, name: "菜单7", parentId: 0, chilren: [], }, ], }, { id: 5, name: "菜单5", parentId: 0, chilren: [], }, ], }, { id: 2, name: "菜单2", parentId: 0, chilren: [ { id: 6, name: "菜单6", parentId: 0, chilren: [], }, ], }, //此处省略后面的内容........];
初步分析
初步分析思路是:使用递归算法,即遍历dataJSONArray数组,取出每一个对象,获取其id,然后再遍历整个dataJSONArray,取出每个对象的parentId,如果id==parentId就是它的children了,将该对象push进children,循环往复,直至每个对象都正确找到它的孩子节点,如下是具体代码分析。
递归算法
- 递归代码算法
function transToTree1(data) { //定义tree数组 const treeList = []; for (let i = 0, len = data.length; i < len; i++) { //找出有父类的对象 if (!data[i].parentId) { //查询其父类,并拼接对象 const item = queryChildren(data[i], data); // tree数组接收封装后的对象 treeList.push(item); } } return treeList;}function queryChildren(parent, data) { //定义子类children数组 const children = []; //遍历原数组 for (let i = 0, len = data.length; i < len; i++) { //如果它的父类id === parent的id,递归继续查询 if (data[i].parentId === parent.id) { const item = queryChildren(data[i], data); //children数组接收封装后的对象 children.push(item); } } parent.children = children; return parent;}
递归算法测试
let dataJSONArray = [ { id: 1, parentId: 0, name: "菜单1" }, { id: 2, parentId: 0, name: "菜单2" }, { id: 3, parentId: 0, name: "菜单3" }, { id: 4, parentId: 1, name: "菜单4" }, { id: 5, parentId: 1, name: "菜单5" }, { id: 6, parentId: 2, name: "菜单6" }, { id: 7, parentId: 4, name: "菜单7" }, { id: 8, parentId: 7, name: "菜单8" }, { id: 9, parentId: 8, name: "菜单9" }, { id: 10, parentId: 9, name: "菜单10" }, { id: 11, parentId: 10, name: "菜单11" }, { id: 12, parentId: 11, name: "菜单12" }, { id: 13, parentId: 12, name: "菜单13" }, { id: 14, parentId: 13, name: "菜单14" },];let result = transToTree1(dataJSONArray);console.log(result);console.log(JSON.stringify(result, null, 2));//可以从下图中看到已经得到了想要的结果//输出结果[ { id: 1, parentId: 0, name: "菜单1", children: [ { id: 4, parentId: 1, name: "菜单4", children: [ { id: 7, parentId: 4, name: "菜单7", children: [ { id: 8, parentId: 7, name: "菜单8", children: [ { id: 9, parentId: 8, name: "菜单9", children: [ { id: 10, parentId: 9, name: "菜单10", children: [ { id: 11, parentId: 10, name: "菜单11", children: [ { id: 12, parentId: 11, name: "菜单12", children: [ { id: 13, parentId: 12, name: "菜单13", children: [ { id: 14, parentId: 13, name: "菜单14", children: [], }, ], }, ], }, ], }, ], }, ], }, ], }, ], }, ], }, { id: 5, parentId: 1, name: "菜单5", children: [], }, ], }, { id: 2, parentId: 0, name: "菜单2", children: [ { id: 6, parentId: 2, name: "菜单6", children: [], }, ], }, { id: 3, parentId: 0, name: "菜单3", children: [], },];
思考:从代码实现中,可以看到,使用了递归算法,可能会存在多次调用queryChildren(data[i], data)的情况,也就意味着,当调用的过多的函数,到达了临界值,可能导致调用堆栈无法容纳这些调用的返回地址,就出现的堆栈溢出的极端情况。
堆栈溢出模拟
// 随机写一个多层次多数据的原始数据let dataJSONArray = [];for (let i = 0; i < 100000; i++) { let map = { }; map.id = i + 1; map.name = "菜单" + i + 1; map.parentId = i; dataJSONArray.push(map); console.log("=======i======" + i);}let result = transToTree1(dataJSONArray);// 可以看到,在该测试情况下,出现了堆栈溢出的极端情况,虽然这种源数据结构几乎不存在,但是这里为了说明存在堆栈溢出的情形特地模拟出来。
另外还有一种情形也会出现堆栈溢出
// 如果源数据出现类似下面的情形,即id==parentId,会出现无限死循环。所以,如果源数据存在这种情况,需要在代码里做一个特殊的判断处理。{ "id": 0, "parentId": 0, "name": "菜单1"}
二次循环算法
实现思路:第一次循环,源数据dataJSONArray,转换成一个map,dataJSONArray每个对象的id作为map的id,使其能通过 id 快速查询。第二次循环,遍历源数据dataJSONArray,通过parentId与第一次循环的map进行匹对,数据封装。
function transToTree2(data) { const treeList = []; const record = { }; const length = data.length; //第一次循环转成map for (let i = 0; i < length; i++) { const item = data[i]; // 重置 children item.children = []; record[item.id] = item; } // 二次循环 for (let i = 0; i < length; i++) { const item = data[i]; //通过id进行比较 if (item.parentId) { if (record[item.parentId]) { record[item.parentId].children.push(item); } } else { //没有父节点的就直接push进数组 treeList.push(item); } } return treeList;}//输出结果://与递归算法一致,递归算法没有children时没有children,这里展示
二次循环算法相较于递归算法的实现,避免了堆栈溢出的问题,复杂度得到了一定程度的降低,至于算法效率有没有得到了提高暂时无法确定,后面会有测试比较。
虽然避免了堆栈溢出的问题,但也增加了时间复杂度,遍历的次数是data.length*2(有点多),能不能只循环一次就能解决问题呢?经过一番折腾,成功地将二次循环减少为一次循环。
一次循环算法
一次循环算法的主要思路是:使用对象变量的特性,利用 map 结构直接指向 children数组,在循环中初始化的同时还能快速查找插入相应的 children 里。
function transToTree3(data, options = { }) { //定义map属性 const { key = "id", childKey = "children", parentKey = "parentId" } = options; const treeList = []; const record = { }; //遍历数组 for (let i = 0, len = data.length; i < len; i++) { const item = data[i]; const id = item[key]; //不存在是跳过 if (!id) { continue; } if (record[id]) { item[childKey] = record[id]; } else { item[childKey] = record[id] = []; } if (item[parentKey]) { const parentId = item[parentKey]; if (!record[parentId]) { record[parentId] = []; } record[parentId].push(item); } else { treeList.push(item); } } return treeList;}
基于filter的低代码实现
虽然实现了一次循环算法,但是总感觉代码太多了,于是查找了下资料,发现确实是有人可以低代码就可以实现了,下面是其中的一种基于filter的低代码实现。
function transToTree4(data) { // 对源数据深度克隆,避免对源数据产生影响 let cloneData = JSON.parse(JSON.stringify(data)); // 循环所有项,并添加children属性 return cloneData.filter((father) => { // 返回每一项的子级数组 let branchArr = cloneData.filter((child) => father.id == child.parentId); //给父级添加一个children属性,并赋值 branchArr.length > 0 ? (father.children = branchArr) : ""; //返回第一层 return father.parentId == 0; });}
各种算法性能比拼
经过一番的努力,已经成功掌握了四种扁平化数据转换成树形结构的算法了,但是从科学严谨的角度上来说,并不是低代码的算法就一定好,二次循环的就一定比一次循环的要好。所以,我决定采用控制变量法的方式,对这四种算法进行一个性能的比较并得出结果。
- 步骤
1、设置测试源数据:
//通过nums控制源数据的个数//通过map.parentId = Math.floor(Math.random() * nums);控制每个菜单的上级,随机let nums = 10000;for (let i = 0; i < nums; i++) { let map = { }; map.id = i + 1; map.name = "菜单" + i + 1; //设置每个菜单的父类菜单 map.parentId = Math.floor(Math.random() * nums); dataJSONArray.push(map);}
2、设置测试样例数据,nums设置为100,1000,2000,3000,5000,10000,50000。每次测试10次,取平均值。
3、统计每组测试数据的结果数据,进行比较分析。
-
实验
部分实验截图
算法 | 100 | 1000 | 2000 | 3000 | 5000 | 10000 | 50000 |
---|---|---|---|---|---|---|---|
递归 | 0ms | 0.2ms | 0.2ms | 1.8ms | 3.6ms | 10ms | 10.6ms |
二次循环 | 0.2ms | 0.8ms | 1.8ms | 2.4ms | 7.6ms | 10.6ms | 38.2ms |
一次循环 | 0.2ms | 1.2ms | 3.8ms | 4.2ms | 6.8ms | 9.2ms | 33.8ms |
filter | 0.8ms | 18.6ms | 52.4ms | 93.2ms | 280ms | 681.2ms | 16402.2ms |
结论
- 实验结果表明:在上述四种算法中,虽然递归算法存在堆栈溢出问题,但是在几组不同测试源数据下,它的耗时都是最少的,执行效率是最高的,网上说的它的效率低下的说法,我表示有所保留和怀疑。
- filter算法虽然代码量少,简单,但是耗时在几种算法里是最大的。
- 二次循环算法与一次循环算法,整体耗时差异不大,数据量少时,二次循环耗时少,但是当数据量上升到一定程度,一次循环性能还比二次循环稍好一点点。
- 在数据量少的情况下,这几种算法的耗时差异不大,但是,当数据量大于2000左右时,filter算法的耗时显著增加,甚至当数据量大于5w时,其他算法的耗时都不超过1s,而filter算法已经超过了10s。
- 至于采用哪种算法好,需要根据项目的具体情况来进行选择。
总结
通过本次自己较为深入的研究和实践,得到了很大的收获。主要有以下几点:
- 遇到问题,需要进行科学严谨的分析,采用合适的方法论来进行验证和探索。
- 纸上得来终觉浅,绝知此事要躬行,实践出真知,很多结论,需要自己去实践才能得出结果,而不是人云亦云。
通过记录这一篇简单的研究博客,记录下自己技术研究的成长之路,并持之以恒,不断成长。也希望能给遇到类似问题的朋友提供一些帮助和参考,与大家共勉。
附全部代码:
let dataJSONArray = [];let nums = 100;for (let i = 0; i < nums; i++) { let map = { }; map.id = i + 1; map.name = "菜单" + i + 1; //设置每个菜单的父类菜单 map.parentId = Math.floor(Math.random() * nums); dataJSONArray.push(map);}let avg1 = 0;let avg2 = 0;let avg3 = 0;let avg4 = 0;for (let i = 0; i < 5; i++) { let startTime = new Date().getTime(); let result1 = transToTree1(dataJSONArray); let endTime1 = new Date().getTime(); console.log("nums:", nums, ",递归算法耗时(ms):", endTime1 - startTime); avg1 += endTime1 - startTime;}console.log("10次递归算法耗时均值(ms)", avg1 / 5);for (let i = 0; i < 10; i++) { let endTime1 = new Date().getTime(); let result2 = transToTree2(dataJSONArray); let endTime2 = new Date().getTime(); console.log("nums:", nums, ",二次循环算法耗时(ms):", endTime2 - endTime1); avg2 += endTime2 - endTime1;}console.log("10次二次循环算法耗时均值(ms)", avg2 / 5);for (let i = 0; i < 10; i++) { let endTime2 = new Date().getTime(); let result3 = transToTree3(dataJSONArray); let endTime3 = new Date().getTime(); console.log("nums:", nums, ",一次循环算法耗时(ms):", endTime3 - endTime2); avg3 += endTime3 - endTime2;}console.log("10次一次循环算法耗时均值(ms)", avg3 / 5);for (let i = 0; i < 10; i++) { let endTime3 = new Date().getTime(); let result4 = transToTree4(dataJSONArray); let endTime4 = new Date().getTime(); console.log("nums:", nums, ",filter算法耗时(ms):", endTime4 - endTime3); avg4 += endTime4 - endTime3;}console.log("10次filter算法耗时均值(ms)", avg4 / 5);function transToTree1(data) { //定义tree数组 const treeList = []; for (let i = 0, len = data.length; i < len; i++) { //找出有父类的对象 if (!data[i].parentId) { //查询其父类,并拼接对象 const item = queryChildren(data[i], data); // tree数组接收封装后的对象 treeList.push(item); } } return treeList;}function queryChildren(parent, data) { //定义子类children数组 const children = []; //遍历原数组 for (let i = 0; i < data.length; i++) { //如果它的父类id === parent的id,递归继续查询 if (data[i].parentId === parent.id) { const item = queryChildren(data[i], data); //children数组接收封装后的对象 children.push(item); } } parent.children = children; return parent;}function transToTree2(data) { const treeList = []; const record = { }; const length = data.length; //第一次循环转成map for (let i = 0; i < length; i++) { const item = data[i]; // 重置 children item.children = []; record[item.id] = item; } // 二次循环 for (let i = 0; i < length; i++) { const item = data[i]; //通过id进行比较 if (item.parentId) { if (record[item.parentId]) { record[item.parentId].children.push(item); } } else { //没有父节点直接push进数组 treeList.push(item); } } return treeList;}function transToTree3(data, options = { }) { //定义map属性 const { key = "id", childKey = "children", parentKey = "parentId" } = options; const treeList = []; const record = { }; //遍历数组 for (let i = 0, len = data.length; i < len; i++) { const item = data[i]; const id = item[key]; //不存在是跳过 if (!id) { continue; } if (record[id]) { item[childKey] = record[id]; } else { item[childKey] = record[id] = []; } if (item[parentKey]) { const parentId = item[parentKey]; if (!record[parentId]) { record[parentId] = []; } record[parentId].push(item); } else { treeList.push(item); } } return treeList;}function transToTree4(data) { // 对源数据深度克隆,避免对源数据产生影响 let cloneData = data; // 循环所有项,并添加children属性 return cloneData.filter((father) => { // 返回每一项的子级数组 let branchArr = cloneData.filter((child) => father.id == child.parentId); //给父级添加一个children属性,并赋值 branchArr.length > 0 ? (father.children = branchArr) : ""; //返回第一层 return father.parentId == 0; });}
转载地址:https://blog.csdn.net/vipshop_fin_dev/article/details/116448606 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关于作者
