发帖
翼度科技»论坛 › 编程开发 › JavaScript › 查看内容

Vue3快速diff算法的处理过程

放鹿青崖间

8

主题

8

帖子

24

积分

新手上路

Rank: 1

积分
24
显示全部楼层
一、为什么要使用diff算法

新旧vnode节点都有一组子节点的情况下，如果不使用diff算法处理则渲染器的做法是，将旧的子节点全部卸载，再挂载新的子节点，并没有考虑到节点的复用情况，比如下面的两组vnode
  1. const newVnode = {
  2.   type: 'div',
  3.   children: [
  4.     { type: 'p', children: '1' },
  5.     { type: 'p', children: '2' },
  6.     { type: 'p', children: '3' },
  7.   ]
  8. }

  10. const oldVnode = {
  11.   type: 'div',
  12.   children: [
  13.     { type: 'p', children: '4' },
  14.     { type: 'p', children: '5' },
  15.     { type: 'p', children: '6' }
  16.   ]
  17. }
复制代码
实际上并不需要去全部卸载然后挂载新的子节点，只需要替换子节点中
  1. p
复制代码
标签中的文本内容即可。 Vue使用diff算法的原因就是为了避免全量更新子节点，尽可能的去复用或者使用较少的操作去完成节点的更新。

二、如何复用子节点


1.判断是否可复用：

观察以下两个新旧节点：他们的类型相同都是
  1. p
复制代码
元素，并且其内容其实也没有变化，只是元素的顺序发生了变动，这种情况我们完全可以复用新旧节点：
  1. const newVnode = {
  2.   type: 'div',
  3.   children: [
  4.     { type: 'p', children: '1' },
  5.     { type: 'p', children: '2' },
  6.     { type: 'p', children: '3' },
  7.   ]
  8. }

  10. const oldVnode = {
  11.   type: 'div',
  12.   children: [
  13.     { type: 'p', children: '3' },
  14.     { type: 'p', children: '2' },
  15.     { type: 'p', children: '1' }
  16.   ]
  17. }
复制代码
为了能够识别出哪些子节点是我们可以复用的，可以给其加上key属性，当新旧节点的
  1. key
复制代码
值相同时，则证明他们是同一个子节点，可以复用。
  1. const newVnode = {
  2.   type: 'div',
  3.   children: [
  4.     { type: 'p', children: '1', key:1 },
  5.     { type: 'p', children: '2', key:2  },
  6.     { type: 'p', children: '3', key:3  },
  7.   ]
  8. }

  10. const oldVnode = {
  11.   type: 'div',
  12.   children: [
  13.     { type: 'p', children: '3', key:3 },
  14.     { type: 'p', children: '2', key:2  },
  15.     { type: 'p', children: '1', key:1  },
  16.   ]
  17. }
复制代码


2.对可复用节点的处理：

节点可复用并不意味着只需要简单的处理新旧子节点的顺序变化，子节点的内容可能也会发生变动，所以在移动之前需要打补丁确保内容更新：我们需要对前面处理子节点更新的
  1. patchChildren
复制代码
进行完善，主要处理其中新旧子节点都是多个的情况，此时我们才需要使用diff算法处理,其中再使用
  1. patch
复制代码
函数去更新可复用节点,具体的处理过程在下文中进行描述：
  1. function patchChildren(n1, n2, container) {
  2.     if (typeof n2.children === 'string') {
  3.      //省略代码
  4.     } else if (Array.isArray(n2.children)) {
  5.       //新子节点是一组节点
  6.       if (Array.isArray(n1.children)) {
  7.         //旧子节点也是一组节点，应用diff算法处理
  8.         //省略diff算法代码
  9.         //diff中会使用patch去更新可复用元素
  10.       } else if (typeof n1.children === 'string') {
  11.        //省略代码
  12.       }
  13.     }
  14.   }
复制代码
三、Vue3快速diff算法的处理过程


1.预处理:处理两组子节点中首尾节点可复用的情况

比如下面的情况：

有三个节点
  1. key
复制代码
值相同，可以复用，并且他们在子节点中的相对顺序也没有发生变化，
  1. p-1
复制代码
在最前面，
  1. p-2
复制代码
和
  1. p-3
复制代码
在最后面。所以他们并不需要移动，只需要处理中间的节点。

处理前置节点：

设置一个索引j从0开始使用while循环寻找相同的前置节点：如果是key相同的节点，调用patch函数打补丁更新其中的内容，直到使用同一个索引取到的新旧子节点key值不同


处理后置节点：

拿到新旧子节点最后一个元素的索引
  1. oldEnd
复制代码
和
  1. newEnd
复制代码
，使用while从两组节点尾部往上遍历，如果是key相同的节点则调用
  1. patch
复制代码
函数打补丁更新其中的内容，知道取不到相同key的节点为止。

我们使用一个
  1. patchKeyedChildren
复制代码
函数去实现上述过程：
  1.   function patchKeyedChildren(n1, n2, container) {
  2.     const oldChildren = n1.children
  3.     const newChildren = n2.children
  4.    
  5.     //处理前置节点
  6.     let j = 0
  7.     let oldVNode = oldChildren[j]
  8.     let newVNode = newChildren[j]
  9.    
  10.     while (oldVNode.key === newVNode.key) {
  11.         patch(oldVNode, newVNode, container)
  12.         j++
  13.         oldVNode = oldChildren[j]
  14.         newVNode = newChildren[j]
  15.     }
  16.    
  17.     //处理后置节点
  18.     //将新旧节点的索引指向最后一个子节点
  19.     let oldEnd = oldChildren.length - 1
  20.     let newEnd = newChildren.length - 1
  21.    
  22.     oldVNode = oldChildren[oldEnd]
  23.     newVNode = newChildren[newEnd]
  24.    
  25.     while (oldVNode.key === newVNode.key) {
  26.         patch(oldVNode, newVNode, container)
  27.         oldEnd--
  28.         newEnd--
  29.         oldVNode = oldChildren[oldEnd]
  30.         newVNode = newChildren[newEnd]
  31.     }
  32.       
  33.   }
复制代码
2、预处理之后的两种情况：需要删除节点、需要新增节点

如何判断存在需要删除或者新增的节点? 在预处理之后我们可以获得的信息有：

  • 处理前置节点的时候获得的索引
    1. j
    复制代码
  • 处理后置节点得到的两个索引
    1. newEnd
    复制代码
    、
    1. oldEnd
    复制代码
    利用以上索引可以做出判断：
需要新增节点的情况：oldEnd < j 以及 newEnd >= j：

需要删除节点的情况：oldEnd >= j 以及 newEnd < j：

在前文:
Vuejs 数据是如何渲染的？渲染器的简单实现
Vue 的渲染器是如何对节点进行挂载和更新的中实现的patch和mountElement方法并不能指定位置去挂载节点，为了能够处理指定节点位置插入节点，我们需要为其增加一个参数anchor，传入锚点元素。
  1. function patch(n1, n2, container, anchor) {
  2.    //...省略代码
  3.   if (typeof type === 'string') {
  4.     if (!n1) {
  5.         //在此处传入锚点以支持新节点按位置插入
  6.       mountElement(n2, container, anchor)
  7.     } else {
  8.       patchElement(n1, n2)
  9.     }
  10.   } else if (type === Text) {
  11.     //...省略代码
  12. }

  14. function mountElement(vnode, container, anchor) {
  15.     //省略代码
  16.     //给insert方法传递锚点元素
  17.     insert(el, container, anchor)
  18. }

  20. const renderer = createRenderer({
  21.     //...省略代码
  22.     insert(el, parent, anchor = null) {
  23.         //根据锚点元素插入节点
  24.         parent.insertBefore(el, anchor)
  25.     }
  26. })
复制代码
接下来我们需要完善patchKeyedChildren去处理上述两种情况：
需要新增节点时：
  1. function patchKeyedChildren(n1, n2, container) {
  2.     const oldChildren = n1.children
  3.     const newChildren = n2.children
  4.    
  5.     //需要插入新节点
  6.     if (j > oldEnd && j <= newEnd){
  7.          //取得锚点索引
  8.          const anchorIndex = newEnd + 1
  9.          //取得锚点元素
  10.          const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
  11.          //调用patch挂载新节点
  12.          while (j <= newEnd) {
  13.              patch(null, newChildren[j++], container, anchor)
  14.          }
  15.     }
  16.       
  17.   }
复制代码
代码如上，我们首先使用
  1. newEnd+1
复制代码
获取锚点索引，并且使用
  1. newChildren[anchorIndex].el
复制代码
去获取到锚点元素，其中还做了一个判断如果
  1. newEnd
复制代码
是尾部节点那不需要提供锚点元素直接处理即可。
需要删除节点时:
  1. function patchKeyedChildren(n1, n2, container) {
  2.     const oldChildren = n1.children
  3.     const newChildren = n2.children
  4.    
  5.     //需要插入新节点
  6.     if (j > oldEnd && j <= newEnd){
  7.         //...省略新增节点逻辑
  8.          
  9.     }else if (j > newEnd && j <= oldEnd) {
  10.        //卸载节点
  11.         while (j <= oldEnd) {
  12.             unmount(oldChildren[j++])
  13.         }
  14.     }
  15.       
  16.   }
复制代码
如上所示，当
  1. j<=oldEnd
复制代码
时循环使用
  1. umount
复制代码
卸载对应的节点即可。
在实际过程中，很少会有像上述简单的预处理即可完成大部分工作的情况，这个时候就需要进行进一步的判断： 比如以下情况：

在经过预处理之后，只有首尾两个节点被正确更新了，仍然会有多数节点没有被更新。
预处理之后后续需要做的是:

  • 判断节点是否需要移动，移动节点；
  • 如果有需要添加或者移除的节点进行处理；

3.判断节点是否需要移动：


1.构建source数组

source数组需要去存储新的子节点对应的旧子节点的位置索引，然后去计算一个最长递增子序列，通过最长递增子序列去完成DOM的移动操作
初始化source数组:
  1. function patchKeyedChildren(n1, n2, container) {
  2.     const oldChildren = n1.children
  3.     const newChildren = n2.children
  4.    
  5.     //需要插入新节点
  6.     if (j > oldEnd && j <= newEnd){
  7.         //...省略新增节点逻辑
  8.          
  9.     }else if (j > newEnd && j <= oldEnd) {
  10.        //卸载节点
  11.         while (j <= oldEnd) {
  12.             unmount(oldChildren[j++])
  13.         }
  14.         //预处理完毕后
  15.     } else{
  16.         //初始化source数组
  17.         const count = newEnd - j + 1
  18.         const source = new Array(count)
  19.         source.fill(-1)
  20.     }
  21.       
  22.   }
复制代码
source数组的长度等于预处理之后剩余节点的长度也就是
  1. newEnd - j + 1
复制代码
,我们使用fill将数组中的元素填充为
  1. -1
复制代码
初始化其中的值

填充source数组: 使用新子节点在旧子节点中的索引去填充source数组

如上key为
  1. p-3
复制代码
的新子节点在旧子节点中的索引为
  1. 2
复制代码
，所以source数组的第一项需要被填充为
  1. 2
复制代码
，
  1. key
复制代码
为
  1. p-4
复制代码
的新子节点在旧子节点为
  1. 3
复制代码
，所以source数组的第二项的值为
  1. 3
复制代码
，以此类推。 在这个过程中需要嵌套两个for循环去遍历新旧子节类似下面的过程：
  1. for (let i = oldStart; i <= oldEnd; i++) {
  2.     const oldVNode = oldChildren[i]
  3.     // 遍历新的一组子节点
  4.     for (let k = newStart; k <= newEnd; k++) {
  5.         const newVNode = newChildren[k]
  6.         // 找到拥有相同 key 值的可复用节点
  7.         if (oldVNode.key === newVNode.key) {
  8.             // 调用 patch 进行更新
  9.             patch(oldVNode, newVNode, container)
  10.             // 最后填充 source 数组
  11.             source[k - newStart] = i
  12.         }
  13.     }
  14. }
复制代码
以上做法时间复杂度为
  1. O(n^2)
复制代码
,在子节点数量增加时会存在性能问题。 优化的办法是先遍历新的一组子节点，根据子节点的位置和key生成一张索引表，然后再遍历旧的一组子节点，利用节点的key在索引表中找到对应的新子节点的位置，以此填充source数组。
  1. const oldStart = j
  2. const newStart = j
  3. const keyIndex = {}
  4. for(let i = newStart; i <= newEnd; i++) {
  5.     keyIndex[newChildren[i].key] = i
  6. }
  7. for(let i = oldStart; i <= oldEnd; i++) {
  8.   oldVNode = oldChildren[i]
  9.   const k = keyIndex[oldVNode.key]
  10.   if (typeof k !== 'undefined') {
  11.     newVNode = newChildren[k]
  12.     patch(oldVNode, newVNode, container)
  13.     source[k - newStart] = i
  14.   } else {
  15.     unmount(oldVNode)
  16.   }
  17. }
复制代码
优化后的代码如上所示:
首先将预处理之后的
  1. j
复制代码
值作为遍历新旧节点开始时的索引，定义一个对象
  1. keyIndex
复制代码
作为索引表，遍历预处理之后剩余的一组新子节点，将新子节点
  1. newChildren[i]
复制代码
的key值与其位置索引放入索引表中。 遍历旧子节点，在遍历时，我们可以通过当前节点的
  1. key
复制代码
去
  1. keyIndex
复制代码
索引表中获取从而拿到当前遍历的旧子节点的
  1. oldChildren[i]
复制代码
对应的新节点的位置
  1. keyIndex[oldVNode.key]
复制代码
,如果位置存在，说明节点可复用，使用
  1. patch
复制代码
打补丁，并且使用当前旧节点的索引
  1. i
复制代码
对source数组进行填充。

2.标识是否需要移动节点

需要添加标识有:

  • 是否需要移动
    1. moved
    复制代码
    : 用于标识是否有需要移动的节点，
  • 当前新子节点的位置
    1. pos
    复制代码
    : 用于记录遍历旧子节点中遇到的最大的索引值
    1. k
    复制代码
    ，如果此次遍历的
    1. k
    复制代码
    值大于上一次的，说明相对位置正确无需移动,
  • 已经更新过的节点数量
    1. patched
    复制代码
    ：当
    1. patched
    复制代码
    大于source数组的长度即
    1. newEnd - j + 1
    复制代码
    时说明所有可复用节点已经处理完毕，还有一些旧子节点需要执行卸载操作， 代码如下，我们在每一次更新节点内容后递增
    1. patched++
    复制代码
    记录处理数量，并对
    1. moved
    复制代码
    和
    1. pos
    复制代码
    的值进行处理。
  1. const count = newEnd - j + 1  // 新的一组子节点中剩余未处理节点的数量
  2. const source = new Array(count)
  3. source.fill(-1)

  5. const oldStart = j
  6. const newStart = j
  7. let moved = false
  8. let pos = 0
  9. const keyIndex = {}
  10. for(let i = newStart; i <= newEnd; i++) {
  11.     keyIndex[newChildren[i].key] = i
  12. }
  13. let patched = 0
  14. for(let i = oldStart; i <= oldEnd; i++) {
  15.     oldVNode = oldChildren[i]
  16.     if (patched < count) {
  17.       const k = keyIndex[oldVNode.key]
  18.       if (typeof k !== 'undefined') {
  19.         newVNode = newChildren[k]
  20.         patch(oldVNode, newVNode, container)
  21.         patched++
  22.         source[k - newStart] = i
  23.         // 判断是否需要移动
  24.         if (k < pos) {
  25.           moved = true
  26.         } else {
  27.           pos = k
  28.         }
  29.       } else {
  30.         // 没找到
  31.         unmount(oldVNode)
  32.       }
  33.     } else {
  34.       unmount(oldVNode)
  35.     }
  36. }
复制代码
4.处理节点的移动：

先前我们使用
  1. moved
复制代码
去标记了是否有至少一个子节点需要移动，当moved为
  1. true
复制代码
时，我们需要配合source数组中的最长递增子序列去移动节点，否则直接不用再去使用diff。

1.最长递增子序列：

什么是最长递增子序列 递增子序列就是在一个序列中，从左到右依次找出更大的值所构成的序列，在一个序列中可能存在多个递增子序列，最长递增子序列就是其中长度最长的那个。 例如 在上面的例子中我们得到的source数组为
  1. [2, 3, 1, -1]
复制代码
,则其最长递增子序列为
  1. [2,3]
复制代码
，我们通过处理得到了对应的旧子节点的索引
  1. [0, 1]
复制代码
,即最长递增子序列对应的新子节点的索引。

如上最长递增子序列对应的旧节点为key为
  1. p-3
复制代码
、
  1. p-4
复制代码
，对应在新子节点的位置为
  1. 0
复制代码
，
  1. 1
复制代码
。
最长递增子序列的意义：通过最长递增子序列得到的索引可以提示我们哪些元素的相对位置，在子节点更新后并未发生变化，我们可以保留这些节点的相对位置，然后去处理和移动其他位置。如上p-3和p-4的相对位置在更新之后并未发生变化，即新节点中的索引为
  1. 0
复制代码
和
  1. 1
复制代码
的元素不需要移动。这里我们省略求最长递增子序列的方法，直接将其当作函数
  1. lis
复制代码
处理
  1. source数组
复制代码
的结果
  1. const seq = lis(source)
复制代码
2.根据最长递增子序列移动节点：

创建两个索引辅助移动:

  • 索引 i 指向新的一组子节点中的最后一个节点。
  • 索引 s 指向最长递增子序列中的最后一个元素。

我们需要去判断以下的情况:

    1. source[i] === -1
    复制代码
    : 节点不存在，需要挂载新节点
    1. i!==seq[s]
    复制代码
    ：节点需要移动，
    1. i===seq[s]
    复制代码
    ：节点无需移动，将s递减并再次进行比较
完善
  1. patchKeyedChildren
复制代码
去处理这几种情况:
  1. function patchKeyedChildren(n1, n2, container) {
  2.   //省略预处理和构造source数组代码
  3.   if (moved) {
  4.     const seq = lis(source)
  5.     // s 指向最长递增子序列的最后一个值
  6.     let s = seq.length - 1
  7.     let i = count - 1
  8.     for (i; i >= 0; i--) {
  9.       if (source[i] === -1) {
  10.         // 说明索引为 i 的节点是全新的节点，应该将其挂载
  11.       
  12.       } else if (i !== seq[j]) {
  13.       
  14.         // 说明该节点需要移动
  15.       } else {
  16.         // 当 i === seq[j] 时，说明该位置的节点不需要移动
  17.         // 并让 s 指向下一个位置
  18.         s--
  19.       }
  20.     }
  21.   }
  22. }
  23. }
复制代码
节点不存在情况具体处理
  1. if (source[i] === -1) {
  2.     // 该节点在新的一组子节点中的真实位置索引
  3.     const pos = i + newStart
  4.     const newVNode = newChildren[pos]
  5.     // 该节点下一个节点的位置索引
  6.     const nextPos = pos + 1
  7.     // 锚点
  8.     const anchor = nextPos < newChildren.length
  9.       ? newChildren[nextPos].el
  10.       : null
  11.     patch(null, newVNode, container, anchor)
  12. }
复制代码
代码如上所示：当新子节点是新节点时直接获取，该节点的位置，即索引，并且加一获得锚点用于挂载元素，如果元素本身就是最后一个元素
  1.  nextPos < newChildren.length
复制代码
，则无需锚点。 此时
  1. p-7
复制代码
处理完成，继续向上处理
  1. p-2
复制代码

节点需要移动的情况
  1. if (i !== seq[s]) {    // 该节点在新的一组子节点中的真实位置索引    const pos = i + newStart    const newVNode = newChildren[pos]    // 该节点下一个节点的位置索引    const nextPos = pos + 1    // 锚点    const anchor = nextPos < newChildren.length      ? newChildren[nextPos].el      : null    patch(null, newVNode, container, anchor)}
复制代码
逻辑和节点不存在的情况类似，只是移动节点通过
  1. insert
复制代码
函数去完成。此时处理的结果如下

节点不需要移动的情况 对于
  1. p-3
复制代码
和
  1. p-4
复制代码
来说，
  1. source[i] !== -1
复制代码
,并且
  1. i === seq[s]
复制代码
，即节点无需移动只需更新
  1. s
复制代码
的值即可
  1.   s--
复制代码
依此类推直到循环结束，子节点全部更新完毕，该过程完整代码如下：
  1.   if (moved) {    const seq = lis(source)    // s 指向最长递增子序列的最后一个值    let s = seq.length - 1    let i = count - 1    for (i; i >= 0; i--) {      if (source[i] === -1) {        // 说明索引为 i 的节点是全新的节点，应该将其挂载        // 该节点在新 children 中的真实位置索引        const pos = i + newStart        const newVNode = newChildren[pos]        // 该节点下一个节点的位置索引        const nextPos = pos + 1        // 锚点        const anchor = nextPos < newChildren.length          ? newChildren[nextPos].el          : null        // 挂载        patch(null, newVNode, container, anchor)      } else if (i !== seq[j]) {        // 说明该节点需要移动        // 该节点在新的一组子节点中的真实位置索引        const pos = i + newStart        const newVNode = newChildren[pos]        // 该节点下一个节点的位置索引        const nextPos = pos + 1        // 锚点        const anchor = nextPos < newChildren.length          ? newChildren[nextPos].el          : null        // 移动        insert(newVNode.el, container, anchor)      } else {        // 当 i === seq[j] 时，说明该位置的节点不需要移动        // 并让 s 指向下一个位置        s--      }    }  }}
复制代码
总结：


  • 使用
    1. diff
    复制代码
    算法的原因    ：

    • 传统的 DOM 更新方法会在有新旧子节点时卸载旧节点并挂载新节点，这种方法没有考虑到节点的复用可能性。
      1. diff
      复制代码
      算法通过比较新旧节点的差异来复用节点，从而优化性能。

  • 节点复用依据:key：

    • 节点复用是通过比较节点的
      1. key
      复制代码
      和
      1. 类型
      复制代码
      来实现的。相同的
      1. key
      复制代码
      和
      1. 类型
      复制代码
      表明两个节点可以被视为同一个，从而复用以减少 DOM 操作。

  • Vue 3 diff算法的过程：

    • 预处理阶段：处理首尾节点，找出新旧两种子节点中首尾可复用的节点并更新。
    • 处理理想情况下新增和删除节点：若通过预处理有一组节点已经更新完毕，证明新的一组子节点只需新增或删除部分节点即可完成更新。
    • 构造source数组：通过遍历新旧两组子节点，构造一个source数组,去存储新的子节点对应的旧子节点的位置索引，并在此过程中判断是否需要使用diff算法处理移动。
    • 节点位置移动：根据最长递增子序列判断具体的某个节点是否需要新增或者移动，在需要时移动节点以匹配新的子节点顺序。

  • diff算法带来的效率提升：

    • 算法避免了全量的 DOM 更新，通过巧妙的方法判断哪些节点需要更新、移动或重新挂载，从而降低了全量更新的成本和时间。

以上就是Vue3快速diff算法的处理过程的详细内容，更多关于Vue3快速diff算法的资料请关注脚本之家其它相关文章！

来源:https://www.jb51.net/javascript/321003qlr.htm
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x

上一篇: 一文详解Vue中渲染器的简单实现

下一篇: jQuery正则表达式验证表单代码演示

发表于 2024-5-27 15:12:17

举报 回复 使用道具

返回列表 发新帖

Archiver|手机版|小黑屋|翼度科技

Copyright © 2001-2020, Tencent Cloud.　Powered by Discuz! X3.4