【手写 Vue2.x 源码】第三十一篇 - diff算法-比对优化（下）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

一前言

上篇diff算法-比对优化上主要涉及以下几个点

  • 介绍了如何进行儿子节点比对
  • 新老儿子节点可能存在的3种情况及代码实现
  • 新老节点都有儿子时的 diff 方案介绍与处理逻辑分析

本篇diff算法-比对优化下

二比对优化

1前文回顾

上篇介绍了新老儿子节点可能存在的几种情况及处理方法

  • 情况 1老的有儿子新的没有儿子

    处理方法直接将多余的老 dom 元素删除即可

  • 情况 2老的没有儿子新的有儿子

    处理方法直接将新的儿子节点放入对应的老节点中即可

  • 情况 3新老都有儿子

    处理方法进行 diff 比对

针对情况 3 新老儿子节点的比对采用了头尾双指针的方法

image.png

优先对新老儿子的头头、尾尾、头尾、尾头节点进行比对若都没有命中再进行乱序比对

2节点比对的结束条件

直至新老节点一方遍历完成比对才结束

即“老的头指针和尾指针重合"或"新的头指针和尾指针重合”

image.png

此时就是循环中最后一次比对了D 节点比对完成后节点继续后移

与老节点比对完成后已经识别了可复用的节点继续将新增节点 E 添加到老儿子节点中

代码实现

// src/vdom/patch.js

/**
 * 新老都有儿子时做比对即 diff 算法核心逻辑
 * 备注采用头尾双指针的方式优化头头、尾尾、头尾、尾头的特殊情况
 * @param {*} el 
 * @param {*} oldChildren  老的儿子节点
 * @param {*} newChildren  新的儿子节点
 */
function updateChildren(el, oldChildren, newChildren) {
    
    // 声明头尾指针
    let oldStartIndex = 0;
    let oldStartVnode = oldChildren[0];
    let oldEndIndex = oldChildren.length - 1;
    let oldEndVnode = oldChildren[oldEndIndex];

    let newStartIndex = 0;
    let newStartVnode = newChildren[0];
    let newEndIndex = newChildren.length - 1;
    let newEndVnode = newChildren[newEndIndex];

    // 循环结束条件有一方遍历完了就结束即"老的头指针和尾指针重合"或"新的头指针和尾指针重合" 
    while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
        // 1优先做4种特殊情况比对头头、尾尾、头尾、尾头
        // 2如果没有命中采用乱序比对
        // 3比对完成后移动指针继续下一轮比对
    }

    // 比对完成后
    // 新的多插入新增节点删除多余节点
}

备注由于diff 算法采用了 while 循环处理所以复杂度为O(n)

3情况 1新儿子比老儿子多插入新增的

分为“从头部开始移动指针”和“从尾部部开始移动指针”两种情况

从头部开始移动指针

头头比对

第一次比配匹配后移动新老头指针
image.png

第二次匹配匹配后移动新老头指针

image.png

直至老节点的头尾指针重合此时D 节点是 while 最后一次做比对

image.png

比对完成后指针继续后移导致老节点的头指针越过尾指针此时 while 循环结束

while 循环结束时的指针状态如下

image.png

此时新节点的头指针指向的节点 E 为新增节点后面可能还有 F G H 等新增节点需要将它们 指从 newStartIndex 到 newEndIndex 所有节点添加到老节点儿子集合中

代码实现

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){ 
    // 头头比对
    if(isSameVnode(oldStartVnode, newStartVnode)){ 
        // isSameVnode只能判断标签和key一样但属性可能还有不同 
        // 所以需要patch方法递归更新新老虚拟节点的属性
        patch(oldStartVnode, newStartVnode); 
        // 更新新老头指针和新老头节点 
        oldStartVnode = oldStartVnode[++oldStartIndex]; 
        newStartVnode = newStartVnode[++newStartIndex]; 
    } 
}

// 1新的多插入新增的 
if(newStartIndex <= newEndIndex){ 
    // 新的开始指针和新的结束指针之间的节点 
    for(let i = newStartIndex; i <= newEndIndex; i++){ 
       // 获取对应的虚拟节点并生成真实节点添加到 dom 中 
       el.appendChild(createElm(newChildren[i])) 
    } 
}

测试效果

let render1 = compileToFunction(`<div>
    <li key="A">A</li>
    <li key="B">B</li>
    <li key="C">C</li>
    <li key="D">D</li>
</div>`);

let render2 = compileToFunction(`<div>
    <li key="A" style="color:red">A</li>
    <li key="B" style="color:blue">B</li>
    <li key="C" style="color:yellow">C</li>
    <li key="D" style="color:pink">D</li>
    <li key="E">E</li>
    <li key="F">F</li>
</div>`);

更新前

image.png

更新后

image.png

备注
将新儿子中新增的节点直接向后添加到老儿子集合中使用 appendChild 即可
但是如果新增的节点在头部就不能用 appendChild 了见下面尾尾比对分析

从尾部开始移动指针

尾尾比对

image.png

指针向前移动当老节点的头尾指针重合即 while 循环的最后一次比对

image.png

比对完成指针向前移动后循环结束时的指针状态如下

image.png

while 比对完成后需要将剩余新节点添加到老儿子中的对应位置

image.png

问题如何向头部位置新增节点

问题如何将新增节点 E、F 放到 A 的前面

分析

  • 要加到 A 节点前不能继续使用 appendChild 向后追加节点
  • 前面的代码是指“从新的头指针到新的尾指针”这一区间的节点即for (let i = newStartIndex; i <= newEndIndex; i++) 所以是先处理 E 节点在处理 F 节点

先处理 E 节点将 E 节点方到 A 节点前的位置

image.png
再处理 F 节点将 F 节点插入到 A 节点与 E 节点之间的位置

image.png

当新增区域的头尾指针重合即为最后一次处理

方案

新增节点有可能追加到后面也有可能插入到前面

  • 头头比较时将新增节点添加到老儿子集合中即可使用 appendChild 追加
  • 尾尾比较时

如何确认该向前还是向后添加节点

要看 while 循环结束时newChildren[newEndIndex + 1]新儿子的尾指针是否有节点
image.png

  • 如果有节点说明是从尾向头进行比对的新增节需要点添加到老儿子集合前面使用insertBefore 插入指定位置
  • 如果无节点说明是从头向尾进行比对的新增节需要点追加到老儿子集合后面使用 appendChild 追加

代码实现

// 1新的多以新指针为参照插入新增
if (newStartIndex <= newEndIndex) {
  // 新的开始指针和新的结束指针之间的节点
  for (let i = newStartIndex; i <= newEndIndex; i++) {
    // 判断当前尾节点的下一个元素是否存在
    //  1如果存在则插入到下一个元素的前面
    //  2如果不存在下一个是 null 就是 appendChild
    // 取参考节点 anchor:决定新节点放到前边还是后边
    //  逻辑取去newChildren的尾部+1,判断是否为 null
    //  解释如果有值说明是向前移动的取出此虚拟元素的真实节点el将新节点添加到此真实节点前即可
    let anchor = newChildren[newEndIndex + 1] == null ? null : newChildren[newEndIndex + 1].el
    // 获取对应的虚拟节点并生成真实节点添加到 dom 中
    // el.appendChild(createElm(newChildren[i]))
    // 逻辑合并:将 appendChild 改为 insertBefore
    //  效果既有appendChild又有insertBefore的功能直接将参考节点放进来即可;
    //  解释对于insertBefore方法,如果anchor为null等同于appendChild;如果有值则是insertBefore;
    el.insertBefore(createElm(newChildren[i]),anchor)
  }
}

备注注意这里的 el.insertBefore 妙用当 insertBefore 方法的第二个参数为 null 时等同于 appendChild 方法

4情况 2老儿子比新儿子多删除多余

let render1 = compileToFunction(`<div>
    <li key="A" style="color:red">A</li>
    <li key="B" style="color:blue">B</li>
    <li key="C" style="color:yellow">C</li>
    <li key="D" style="color:pink">D</li>
</div>`);

let render2 = compileToFunction(`<div>
    <li key="A" style="color:red">A</li>
    <li key="B" style="color:blue">B</li>
    <li key="C" style="color:yellow">C</li>
</div>`);

image.png

老的比新的多在移动过程中就会出现新的已经到头了时老的还有

当移动结束时老的头指针会和尾指针重合新的头指针会越过新的尾指针

image.png

代码实现

将老儿子集合“从头指针到尾指针”区域的多余真实节点删除

// 2老儿子比新儿子多以旧指针为参照删除多余的真实节点
if(oldStartIndex <= oldEndIndex){
  for(let i = oldStartIndex; i <= oldEndIndex; i++){
    let child = oldChildren[i];
    el.removeChild(child.el);
  }
}

5情况 3反序情况

反序情况

image.png

这种情况下可以使用“旧的头指针”和“新的尾指针”进行比较即头尾比较

image.png

每次比较完成后“旧的头指针”向后移动“新的尾指针”向前移动

image.png

并且比较完成后直接将老节点 A 放到老节点最后去

更确切的说是插入到尾指针的下一个节点的前面移动前尾指针指向的 D 节点的下一个节点为 null

继续比较 B比较完成后移动指针
移动 B 插入到尾指针的下一个的前面这时尾指针 D 的下一个是上一次移动过来的 A

image.png

继续 C 和 C 比之后再移动指针
移动 C 插入到尾指针的下一个的前面这时尾指针 D 的下一个是上一次移动过来的 B

image.png

接下来比较 D此时会发现“旧的头指针”和“新的头指针”一样了都是 D

这时就比较完成了D 无需再移动结果就是 D C B A
整个反序过程共移动了3 次移动而不是重新创建

所以对于反序操作来说需要去比对头尾指针老的头和新的尾

每次比对完成后头指针向后移尾指针向左移

代码部分添加“头尾比较”逻辑

while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
  if (isSameVnode(oldStartVnode, newStartVnode)) {
    patch(oldStartVnode, newStartVnode);
    oldStartVnode = oldChildren[++oldStartIndex];
    newStartVnode = newChildren[++newStartIndex];
  }else if(isSameVnode(oldEndVnode, newEndVnode)){
    patch(oldEndVnode, newEndVnode);
    oldEndVnode = oldChildren[--oldEndIndex];
    newEndVnode = newChildren[--newEndIndex];
    // 头尾比较老的头节点和新的尾节点做对比
  }else if(isSameVnode(oldStartVnode, newEndVnode)){
    // patch方法只会duff比较并更新属性但元素的位置不会变化
    patch(oldStartVnode, newEndVnode);// diff:包括递归比儿子
    // 移动节点将当前的节点插入到最后一个节点的下一个节点的前面去
    el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling);
    // 移动指针
    oldStartVnode = oldChildren[++oldStartIndex];
    newEndVnode = newChildren[--newEndIndex];
  }
}

注意

要先插入节点再移动指针
insertBefore是有移动效果的会把原来的节点移走这时 dom 的移动性
appendChild、insertBefore操作 dom 都有移动性都会吧原来的 dom 移走

测试效果

更新前

image.png

更新后

image.png

同理尾头比对的情况

while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (isSameVnode(oldStartVnode, newStartVnode)) {
      patch(oldStartVnode, newStartVnode);
      oldStartVnode = oldChildren[++oldStartIndex];
      newStartVnode = newChildren[++newStartIndex];
    }else if(isSameVnode(oldEndVnode, newEndVnode)){
      patch(oldEndVnode, newEndVnode);
      oldEndVnode = oldChildren[--oldEndIndex];
      newEndVnode = newChildren[--newEndIndex];
    }else if(isSameVnode(oldStartVnode, newEndVnode)){
      patch(oldStartVnode, newEndVnode);
      el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling);
      oldStartVnode = oldChildren[++oldStartIndex];
      newEndVnode = newChildren[--newEndIndex];
    // 尾头比较
    }else if(isSameVnode(oldEndVnode, newStartVnode)){
      patch(oldEndVnode, newStartVnode);  // patch方法只会更新属性元素的位置不会变化
      // 移动节点:将老的尾节点移动到老的头节点前面去
      el.insertBefore(oldEndVnode.el, oldStartVnode.el);// 将尾部插入到头部
      // 移动指针
      oldEndVnode = oldChildren[--oldEndIndex];
      newStartVnode = newChildren[++newStartIndex];
    }
}

测试效果

let render1 = compileToFunction(`<div>
    <li key="E">E</li>
    <li key="A">A</li>
    <li key="B">B</li>
    <li key="C">C</li>
    <li key="D">D</li>
</div>`);

let render2 = compileToFunction(`<div>
    <li key="D" style="color:pink">D</li>
    <li key="C" style="color:yellow">C</li>
    <li key="B" style="color:blue">B</li>
    <li key="A" style="color:red">A</li>
</div>`);

更新前

image.png

更新后

image.png

三结尾

本篇diff算法-比对优化下主要涉及以下几个点

  • 介绍了儿子节点比较的流程
  • 介绍并实现了头头、尾尾、头尾、尾头4种特殊情况比对

下篇diff算法-乱序比对

维护日志

20210805

  • 添加了“从尾部开始移动指针”的图示
  • 添加了“问题如何向头部位置新增节点”
  • 修改了部分有问题的图示
  • 修改了几处语义表达不够准确的地方
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: vue
返回列表

上一篇：圆满落幕！56 人参加，龙蜥社区技术委员会、运营委员会会议顺利完成

下一篇：一篇博客教会你写序列化工具

“【手写 Vue2.x 源码】第三十一篇 - diff算法-比对优化（下）” 的相关文章

VUE之Element-ui文件上传详解_elementui上传文件1年前 (2023-02-02)
开箱即用，这些 Vue3 后台管理系统模板绝对让你爽歪歪！1年前 (2023-02-02)
Vue3商店后台管理系统设计文稿篇（一）1年前 (2023-02-02)
Vue--》setup、ref、reactive函数使用讲解1年前 (2023-02-02)
Vue2-Vue开发环境搭建1年前 (2023-02-02)
204：vue+openlayers 学习Attribution各种API，示例展示自定义版权信息1年前 (2023-02-02)
[VueJsDev] 目录列表1年前 (2023-02-02)
vue-element-admin前端搭建学习笔记1年前 (2023-02-02)
【Vue中使用Echarts】在Vue中优雅的使用Echarts——图表轮播图、Echarts图表组件封装、节流函数优化图表性能1年前 (2023-02-02)
Vue中动态展示数据的字典项1年前 (2023-02-02)

阿里云国际版