双重循环时间复杂度问题《性能优化篇》

需求

两个数组LA和LB，在理想情况下数组LA和LB的长度是相同的，也有LB长度大于LA的情况。现在需要遍历LA每次迭代的返回值是IA，在每次迭代的过程中需要遍历LB，迭代的结果是IB。此时时间复杂度是O(M*N)。在迭代IB的过程中需要通过两个异步函数获取到两个值，并对其进行操作，其中IB的值要插入到LA数组中此过程会影响到react渲染。

//未优化代码,当LA和LB长度在50左右的时候出现页面卡死现象 此时时间复杂度为O(M*N) = 50 * 50 = 2500
const [LA,setLA] = useState([])
LA.map((ia,idxa)=>{
    LB.map(ib=>{
        if(itemB.name){
            (async()=>{
             const value = await getValue(ib.name)
           	 const n_La  LA[idxa].value = value 
             setLA(n_La)//如果需要迭代2500次 就需要更新2500次LA数组，影响性能
            })()
        }
              (async()=>{
              const Range =  await getRange(ib.name)//getValue，与getRange是先后顺序，会导致时间损耗
              Range.color = 3
            })()
    })
})

整体思路

1. 需要降低时间复杂度，如果LA和LB数据量太大，比如长度均是100，需要迭代10000次。
2. Promise可以利用Promise.all方法并行执行，减少异步操作次数
3. 返回后的数组可以一次修改，而不是每次迭代的时候修改。

第一步：优化LB的数据结构，将数组转化为Map对象

// 预处理 LB 为 Map 结构，name应该是唯一主键
const lbMap = new Map(LB.map(ib => [ib.name, ib]));
//这里可以理解为将数组的查询条件先遍历出来形成一个索引，真正查询的时候只需要查询索引就行

第二步：并行执行异步函数

// 使用 Promise.all + map 替代双重循环
const processItems = async (LA, lbMap) => {
  const results = await Promise.all(
    LA.map(async (ia, index) => {
      const ib = lbMap.get(ia.key); // 根据实际关联字段匹配
      // 并行执行两个异步操作getvalue,getRange
      const [value, range] = await Promise.all([
        ib?.name && getvalue(ib.name), getRange(ib.name)
      ]);
      range.color = 3; // 修改 range 属性 对第二个异步进行操作
      return { index, value };//主要要返回的数组下标和值
    })
  );

  return results.filter(Boolean);//这里会将数组里值为null undefined ""，过滤掉
};
//此时时间复杂度为O(M+N)

第三步，根据第二步返回的数组下标和值对原数组进行修改

//这里推荐使用immerjs 进行不可变数据 优化性能
const [LA,setLA] = useState([])
const updates = processItems(LA,lbMap)
const n_listA = producer(LA,(draft)=>{
    return updates.forEach(({index,value})=>{draft[index].value = value})
})
setStat(n_listA)

当LA和LB长度均为50时

未修改前迭代的次数为2500次；异步执行操 < 5000次；状态修改导致可能重复渲染次数 < 2500次

优化后迭代次数为第一步50，第二步50，第三步50，为150次；异步操作50次，状态修改导致可能重复渲染次数1次

如果数据量特别大，还可以使用虚拟列表进行优化