vue3源码分析——手写diff算法

简介: 通过上面的测试用例,可以看到是分了7种情况来的,在本篇文章,不采用编写测试用例,有兴趣的可以自己去github上面查看,这里主要使用图文加上代码,帮助大家更快的理解vue3中的diff算法

引言


<<往期回顾>>


1.vue3源码分析——实现组件通信provide,inject

2.vue3源码分析——实现createRenderer,增加runtime-test

3.vue3源码分析——实现element属性更新,child更新


本期来实现,上一期中还差了children与children的对比😉😉😉 vue3更新流程中的children与children的对比,也就是diff算法,所有的源码请查看


正文


在children于children的对比中,vue3采用的是双端对比的方式,使用3个指针来进行移动对比,那肯定就会有许多的情况,且听我慢慢道来👍👍👍!


先看个结果


3e2cfe994a154bf1c1d819e2e6eab319.png


通过上面的测试用例,可以看到是分了7种情况来的,在本篇文章,不采用编写测试用例,有兴趣的可以自己去github上面查看,这里主要使用图文加上代码,帮助大家更快的理解vue3中的diff算法


锁定对比的范围


既然采用的是双端对比,那么肯定是需要3个指针的,请看下图:


c6d2983ec6f8cf6f5ff72ab4857209e4.png


总共有3个指针


  • i 代表的是起始指针默认是 0
  • e1 代表的是old children的末尾指针, 默认是 oldChildren.length -1
  • e2 代表的是new children的末尾指针, 默认是 newChildren.length -1


既然有了指针,那是否需要锁定范围呢!指针做对应的移动。移动的方式如下:


  • 如果oldChildren和newChildren左边的节点都一样,那么就需要i往右边移动,直到不同位置停止.
  • 如果oldChildren和newChildren右边的节点都一样,那么对应的e1和e2往左边移动,同样也是到不同位置停止。


根据上面的需求,我相信都能得出一个条件并且写出以下代码


export function patchKeyedChildren(oldChildren, newChildren){
    let i = 0;
    let e1 = oldChildren.length - 1;
    let e2 = newChildren.length - 1;
    // 当 i <= e1 && i<= e2的时候,需要左边移动
    while(i <= e1 && i <= e2){
      if(oldChildren[i] 等于 newChildren[i]){
        i++
      }else{
        break;
      }
    }
    // 同理,右边的指针往左边移动也是这样
      while(i <= e1 && i <= e2){
      if(oldChildren[e1] 等于 newChildren[e2]){
        el--;
        e2--;
      }else{
        break;
      }
    }
}


上面的代码是伪代码,主要是用于说明情况,双端对比,拿到不相同的部分,接下来根据不相同的部分来进行分情况讨论


分情况讨论


总共有7中情况,分别是:


1.老的比新的左边长,在新的左边创删除的节点

2.老的比新的右边长,在新的右边创删除的节点

3.老的比新大左边短,在新的左边创建新的节点

4.老的比新的右边短,在新的右边创建新的节点

5.老的比新的中间节点多,删除多余的节点

6.老的新的中间节点一样多,位置发生变化,需要移动位置

7.老的新的中间节点少,创建新的节点


老的左右边长


这里包含了老的左边长和右边长,都是需要删除对应边界的节点


老节点左边长


会发现,i不动, e1和 e2两个指针往左边移动


cc5c99a26dc2ba6d856d80f8bffc98c0.png


最终 i = 0, e1 = 1, e2 = -1,所以可以得出一个条件是 i > e2 && i <= e1


老节点右边长


可以发现,e1,e2不动,i往右边移动


6c440b3564f22e382e02137147d2b8f0.png


最终 i = 3, e1 = 3, e2 = 2,所以可以得出一个条件是 i > e2 && i <= e1


老的比新的两边长,就是说只要满足 i > e2 && i <= e1这个条件,那就需要执行删除操作


export function patchKeyedChildren(oldChildren, newChildren){
// ……省略上面的指针移动代码
  if (i >= e2 && i <= e1) {
     // 为啥需要while呢,因为可能两边出现多个多余的节点,需要循环删除
      while (i <= e1) {
       // 删除当前节点
        hostRemove(n1[i].el)
        i++
      }
    }
}


老的左右边短


这里包含了,老节点的左边和右边比新的节点是更短的,需要创建新的节点


老的比新的左边短


i不动,e1,e2往左边移动


c3491af7cd738310a7e0afdbdc13e837.png


最终 i = 0, e1 = -1, e2 = 0,所以可以得出一个条件是 i > e1 && i <= e2


老的比新的右边短


e1,e2不动,i往右边移动


6bb47646e81a3263e3a459ab0ac37f26.png


最终 i = 3, e1 = 2, e2 = 3,所以可以得出一个条件是 i > e1 && i <= e2


老的比新的两边短,就是说只要满足 i > e1 && i <= e2这个条件,那就需要执行新增节点的操作


export function patchKeyedChildren(oldChildren, newChildren){
// ……省略上面的代码
else  if (i > e1 && i <= e2) {
      //     a b   i = 0 e1 = -1 e2 = 0
      // d c a b  需要找到a的位置
      const nextPos = e2 + 1;
      const anchor = nextPos < l2 ? n2[nextPos].el : null
     // 同理,需要循环增加节点
      while (i <= e2) {
       // 插入节点
       patch(null, n2[i], container, parentComponent, anchor)
        i++
      }
    }
}


看到这里,恭喜你👍👍👍,vue3 diff的双端对比就已经结束了,接下来锁定了一个中间范围,来判断中间范围的内容,删除,移动位置,新增


中间节点老的比新的多


1ebb456dc39c95747955dfde5bb77d6e.png


通过上面代码的执行,最终 i = 2, e1 =2, e2 = 2,但是这个不可以作为条件哦!思路需要转个弯🦮🦮🦮


通过i 和 e1可以锁定,老节点中间部分,i 和 e2可以锁定新节点的范围; 遍历老的节点,判断老的节点在新节点中是否存在,可以使用双重for循环,但是比较费时间,可以把新节点的内容给缓存起来,那么可以通过空间来换取时间


export function patchKeyedChildren(oldChildren, newChildren){
// ……省略上面的代码
else{
    // 中间对比
      const s1 = i;
      const s2 = i;
      // a b c d   i = 2 e1 = 2 e2 = 1
      // a b d
      // 条件  删除c
      // 判断旧节点是否在新节点里面,在的话保留,不在则删除
      const newIndexToOldIndexMap = new Map()
        // 把新节点的key装入map
      for (let j = s2; j <= e2; j++) {
        newIndexToOldIndexMap.set(newChildren[j].key, j)
      }
      // 然后遍历老的节点,判断是否在新的节点里面
       for (let i = s1; i <= e1; i++) {
        let newIndex;
        if (n1[i].key !== null) {
          newIndex = newIndexToOldIndexMap.get(n1[i].key)
        } else {
          // key 不存在,需要遍历新节点,看能不能找到这个节点
          for (let j = s2; j <= e2; j++) {
            if (isSameVNode(oldChildren[i], newChildren[j])) {
              newIndex = j
              break;
            }
          }
        }
        if (newIndex === undefined) {
          // 删除节点
          hostRemove(n1[i].el)
       }
  }
}


通过上面可以发现,如果在中间对比的时候不写key,将会再来一次for循环,那就比较费性能了!!!


中间对比,节点都存在,需要移动节点


75e94a2c244c4a9652c844eb5aafb849.png


通过上面代码的执行,最终 i = 2, e1 =4, e2 = 4, 在上面的图中,会发现新老节点中只有E的节点移动了,其他的节点都不动,那么怎么找出 [C,D,E]和[E,C,D]中的最长连续的节点呢?


遇到这个,肯定需要使用 最长递增子序列的算法啦,通过这个可以得出最长节点的连续范围.


但是最长递增子序列中需要一个数组,这个数组需要记录老节点与新节点的位置关系


9efcdfbe0d076c09a11198736f3aee4b.png

\


通过上图,可以看到,先定义一个数组,长度是对比之后的长度,然后默认赋值为0,然后遍历老节点,用老节点的i来表示数组的结果,newIndex表示数据的下标,这样就能展示出新老节点的映射关系了


接下来实现一下这部分的功能,由于这一部分的内容与整体有关,我把整个diff的逻辑都放出来,全部已经写好注释了😉😉😉


 function patchKeyChildren(n1, n2, container, parentComponent, anchor) {
    // 采用双端对比法
    const l2 = n2.length
    const l1 = n1.length
    let i = 0;
    let e1 = l1 - 1;
    let e2 = l2 - 1;
    const isSameVNode = (vnode1, vnode2) => {
      return vnode1.type === vnode2.type && vnode1.key === vnode2.key
    }
    // 获取左侧的位置
    while (i <= e1 && i <= e2) {
      if (isSameVNode(n1[i], n2[i])) {
        // 对比对应的子节点
        patch(n1[i], n2[i], container, parentComponent, anchor)
      } else {
        break;
      }
      i++
    }
    // 获取右侧是位置
    while (i <= e1 && i <= e2) {
      if (isSameVNode(n1[e1], n2[e2])) {
        patch(n1[e1], n2[e2], container, parentComponent, anchor)
      } else {
        break;
      }
      e1--;
      e2--;
    }
    // 新的比老的短,删除老的
    if (i >= e2 && i <= e1) {
      while (i <= e1) {
        hostRemove(n1[i].el)
        i++
      }
    }
    // 新的比老的长,挂载新的
    else if (i > e1 && i <= e2) {
      // 往左侧添加 
      //    a b   i = 0 e1 = -1 e2 = 0
      // d c a b  需要找到a的位置
      const nextPos = e2 + 1;
      const anchor = nextPos < l2 ? n2[nextPos].el : null
      while (i <= e2) {
        patch(null, n2[i], container, parentComponent, anchor)
        i++
      }
    }
    else {
      // 中间对比
      const s1 = i;
      const s2 = i;
      // a b c d   i = 2 e1 = 2 e2 = 1
      // a b d
      // 条件  删除c
      // 判断旧节点是否在新节点里面,在的话保留,不在则删除
      const newIndexToOldIndexMap = new Map()
      // 增加一个优化点,如果旧节点的数量和新节点的数量已经一致,那么其余旧节点直接删除
      const toBePatched = e2 - s1 + 1;
      let patched = 0;
      // 将老节点和新节点做映射 b c d --> c d b
      const oldIndexToNewIndexMap = new Array(toBePatched).fill(0)
      // 判断是否需要移动节点,不需要移动则不需要调用获取最长递增子序列
      let moved = false;
      let maxIndexSoFar = 0;
      // 把新节点的key装入map
      for (let j = s2; j <= e2; j++) {
        newIndexToOldIndexMap.set(n2[j].key, j)
      }
      for (let i = s1; i <= e1; i++) {
        // 新节点已经满足前面对比的老节点,需要删除其余的老节点
        if (patched >= toBePatched) {
          hostRemove(n1[i].el)
          continue;
        }
        let newIndex;
        if (n1[i].key !== null) {
          newIndex = newIndexToOldIndexMap.get(n1[i].key)
        } else {
          // key 不存在,需要遍历新节点,看能不能找到这个节点
          for (let j = s2; j <= e2; j++) {
            if (isSameVNode(n1[i], n2[j])) {
              newIndex = j
              break;
            }
          }
        }
        if (newIndex === undefined) {
          // 删除节点
          hostRemove(n1[i].el)
        } else {
          // 更新映射关系
          oldIndexToNewIndexMap[newIndex - s1] = i + 1
          // 判断是否需要移动节点
          if (newIndex > maxIndexSoFar) {
            maxIndexSoFar = newIndex;
          } else {
            moved = true
          }
          // 存在的话,进行下一次的patch
          patch(n1[i], n2[newIndex], container, parentComponent, anchor)
          patched++
        }
      }
      // 获取最长递增序列  获取的是最长递增子序列的索引下标数组
      const longestIncreasingSubsequence = moved ? getLongestIncreasingSubsequence(oldIndexToNewIndexMap) : []
      // 遍历,判断当前的下标是否存在于最长递增序列中,存在则不需要移动,不存在需要移动
      // 使用游标j
      let j = longestIncreasingSubsequence.length - 1;
      for (let i = toBePatched - 1; i >= 0; i--) {
        // 计算下一个节点
        const curIndex = i + s2;
        const anchor = curIndex + 1 < l2 ? n2[curIndex + 1].el : null;
        if (oldIndexToNewIndexMap[i] === 0) {
          // 新增节点
          patch(null, n2[i + s2], container, parentComponent, anchor)
        }
        else if (moved) {
          if (j < 0 || i !== longestIncreasingSubsequence[j]) {
            // 移动节点
            hostInsert(n2[curIndex].el, container, anchor)
          } else {
            // 命中目标节点,不需要移动
            j--;
          }
        }
      }
    }
  }


中间节点新增


对于这个功能,如果看懂了上面代码的话,是非常简单的,只需要判断oldIndexToNewIndexMap[i]是否为0,为0则代表,老节点中没有,新节点有,需要新增节点哦!


总结


本期主要实现了vue3的diff算法,主要分为7个部分:


1.老的比新的左边长,在新的左边创删除的节点

2.老的比新的右边长,在新的右边创删除的节点

3.老的比新大左边短,在新的左边创建新的节点

4.老的比新的右边短,在新的右边创建新的节点

5.老的比新的中间节点多,删除多余的节点

6.老的新的中间节点一样多,位置发生变化,需要移动位置

7.老的新的中间节点少,创建新的节点


只有在中间节点一样多的时候,才会使用最长递增子序列,来判断哪些是需要移动的,只能说vue3的设计太厉害和灵活了,加油!!!

相关文章
|
1月前
|
算法 前端开发 JavaScript
React的diff算法原理
React的diff算法原理
53 0
|
3天前
|
JavaScript 算法 开发者
vue diff算法介绍
vue diff算法介绍
15 2
|
1天前
|
JavaScript 前端开发 算法
React中的DOM diff算法是如何工作的
React的DOM diff算法通过对比新旧虚拟DOM树找到最小更新策略,提高组件更新效率。它生成并比较虚拟DOM,按类型、属性和&quot;key&quot;逐节点检查。不同类型节点直接替换,属性不同则更新属性,相同则递归比较子节点。确定DOM操作后批量执行,减少对真实DOM的访问,优化性能。然而,在复杂场景下可能有性能问题,可借助shouldComponentUpdate、memo或PureComponent等进行优化。
|
11天前
|
JavaScript 算法 前端开发
基于抽象语法树+diff算法实现Markdown编译器
基于抽象语法树+diff算法实现Markdown编译器
|
16天前
|
JavaScript 算法 对象存储
Vue是如何diff算法的
【4月更文挑战第24天】Vue 的 diff 算法核心是对比新旧虚拟 DOM 树,通过比较节点类型、属性及子节点,采用双指针策略和 key 判断,实现高效更新。当节点类型或属性变化时,Vue 更新或替换节点。子节点比较则尝试最小化 DOM 操作,通过 key 优化列表变更。算法递归处理组件和子节点,最终生成补丁对象来更新真实 DOM,提升性能。开发中,合理使用 key 和优化状态变化可进一步提升性能。
|
18小时前
|
算法 Serverless
m基于遗传优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
MATLAB 2022a仿真实现了遗传优化的归一化最小和(NMS)译码算法,应用于低密度奇偶校验(LDPC)码。结果显示了遗传优化的迭代过程和误码率对比。遗传算法通过选择、交叉和变异操作寻找最佳归一化因子,以提升NMS译码性能。核心程序包括迭代优化、目标函数计算及性能绘图。最终,展示了SNR与误码率的关系,并保存了关键数据。
10 1
|
1天前
|
算法 调度
考虑需求响应的微网优化调度模型【粒子群算法】【matlab】
考虑需求响应的微网优化调度模型【粒子群算法】【matlab】
|
2天前
|
运维 算法
基于改进遗传算法的配电网故障定位(matlab代码)
基于改进遗传算法的配电网故障定位(matlab代码)
|
2天前
|
算法 调度
基于多目标粒子群算法冷热电联供综合能源系统运行优化(matlab代码)
基于多目标粒子群算法冷热电联供综合能源系统运行优化(matlab代码)
|
2天前
|
算法
【免费】基于ADMM算法的多微网电能交互分布式运行策略(matlab代码)
【免费】基于ADMM算法的多微网电能交互分布式运行策略(matlab代码)