js 递归优化——尝试为特定情况下的递归算法做次数减法

本文主要是介绍js 递归优化——尝试为特定情况下的递归算法做次数减法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

特定情况在这里指，单条数据在整个算法中仅需做一次处理

前言

在项目中遇到如下需求，将一条内部有依赖关系的扁平结构数据，转换为树形结构数据，其中属性 pid 对应其父节点的属性 id，属性 children 存放子节点，顶层（一级）pid 为 0

常规递归解决

首先想到了如下解决方法

  function flatToTree(list, id) { // 数据树形化
    // 参数 list 表示原始扁平结构数据
    // 参数 id 用来标识顶层 pid
    const result = []

    list.forEach(item => {
      if (item.pid === id) {
        const children = flatToTree(list, item.id)
        if (children.length) item.children = children // 规避无子节点的数据携带不必要的 children 空数组
        result.push(item)
      }
    })

    return result
  }

递归次数优化

后面觉察到每条数据在遍历中被匹配时，后面的遍历过程中其实已经无需此条数据的参与了，于是想了想做了如下改进

  function flatToTree(list, id) { // 数据树形化
    // 参数 list 表示原始扁平结构数据
    // 参数 id 用来标识顶层 pid
    const result = []

    for (let i = 0; i < list.length; i++) {
      if (list[i].pid === id) {
        const temp = { ...list[i] } // 临时变量接收匹配到的数据
        list.splice(i, 1) // 在原数组中删除此条数据
        i-- // 遍历回跳
        const children = flatToTree(list, temp.id)
        if (children.length) temp.children = children  // 规避无子节点的数据携带不必要的 children 空数组
        result.push(temp)
      }
    }

    return result
  }

递归次数优化的深度测试

由于上面的树形结构数据需求至多到二级，且数量并不多，所以为了深入考察优化的可靠性，做了如下测试

测试结果

先看测试结果吧（ 原始数据 10,000 条 ）

• 第一次

• 第二次

• 第三次

测试代码

    // 测试数据树形化的递归次数优化

    // -------------------------------------- 定义相关函数 --------------------------------------

    // ---------- 获取随机数
    function getRandomInt(min, max) {
      return Math.floor(Math.random() * (max - min + 1)) + min
    }

    // ---------- 生成原始数据
    function getData(intNum = 20, top = 5) {
      // 参数 intNum 表示生成数据的长度
      // 参数 top 表示顶层(一级)的数量
      const data = []
      for (let i = 1; i <= intNum; i++) {
        let item = {
          id: i,
          pid: getRandomInt(1, i - 1) // 规避id与pid相等的情况
        }
        if (i < top) { item.pid = 0 }
        data.push(item)
      }
      return data
    }

    // ---------- 数据树形化
    function flatToTree(list, id, complete = true, num) {
      // 参数 id 用来标识顶层 pid
      // 参数 complete 表示选择的递归方法
      // 参数 num 表示计数
      const result = []

      if (complete) { // 完整递归
        list.forEach(item => {
          num[0]++ // 计数
          if (item.pid === id) {
            const children = flatToTree(list, item.id, true, num)
            if (children.length) item.children = children  // 规避无子节点的数据携带不必要的 children 空数组
            result.push(item)
          }
        })
      }
      else { // 递归次数优化
        for (let i = 0; i < list.length; i++) {
          num[0]++ // 计数
          if (list[i].pid === id) {
            const temp = { ...list[i] }
            list.splice(i, 1)
            i--
            const children = flatToTree(list, temp.id, false, num)
            if (children.length) temp.children = children
            result.push(temp)
          }
        }
      }

      return result
    }

    // ---------- 深度提取数组中的对象，平级罗列，检验树形化后的数据是否完整
    function resolveObjectFromArray(arr, res) {
      arr.forEach(item => {
        if (item.children) {
          res.push({ id: item.id, pid: item.pid })
          resolveObjectFromArray(item.children, res)
        } else {
          res.push(item)
        }
      })
    }

    // ---------- 测试生成
    function multiTest(complete = true) {
      // 参数 complete，true of false 完整递归 or 减法递归
      let num = [0] // 递归计数器
      // const data = [...resourceData]
      // 减小影响结果的可能性，生成新的地址存放数据
      const data = []
      resourceData.forEach(item => {
        data.push({ ...item })
      })


      const timeBefore = +new Date()
      const res = flatToTree(data, 0, complete, num) // 数据树形化
      const timeAfter = +new Date()
      console.log('时间消耗：', (timeAfter - timeBefore) / 1000); // 打印时间差，秒
      console.log('树形结构数据：', res);
      console.log('次数：', num); // 打印计数器

      let flatRes = [] // 存放检验结果
      resolveObjectFromArray(res, flatRes) // 检验数据完整性
      console.log('树形结构还原：', flatRes);

    }

    // --------------------------------------测试开始 --------------------------------------

    const resourceData = getData(10_000, 5) // 生成原始数据，这里按 10,000 条数据了来进行测试
    console.log('resourceData == ', resourceData);

    // 测试开始
    console.log('---------------------------------------- 完整递归 ------------------------------------------------')
    multiTest() // 完整递归
    console.log('---------------------------------------- 递归优化 ------------------------------------------------')
    multiTest(false) // 递归优化

这篇关于js 递归优化——尝试为特定情况下的递归算法做次数减法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！