一、为什么要使用diff算法

新旧vnode节点都有一组子节点的情况下,如果不使用diff算法处理则渲染器的做法是,将旧的子节点全部卸载,再挂载新的子节点,并没有考虑到节点的复用情况,比如下面的两组vnode

const newVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' },
  ]
}

const oldVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '4' },
    { type: 'p', children: '5' },
    { type: 'p', children: '6' }
  ]
}

实际上并不需要去全部卸载然后挂载新的子节点,只需要替换子节点中p标签中的文本内容即可。 Vue使用diff算法的原因就是为了避免全量更新子节点,尽可能的去复用或者使用较少的操作去完成节点的更新

二、如何复用子节点

1.判断是否可复用:

观察以下两个新旧节点:他们的类型相同都是p元素,并且其内容其实也没有变化,只是元素的顺序发生了变动,这种情况我们完全可以复用新旧节点:

const newVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' },
  ]
}

const oldVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '3' },
    { type: 'p', children: '2' },
    { type: 'p', children: '1' }
  ]
}

为了能够识别出哪些子节点是我们可以复用的,可以给其加上key属性,当新旧节点的key值相同时,则证明他们是同一个子节点,可以复用。

const newVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '1', key:1 },
    { type: 'p', children: '2', key:2  },
    { type: 'p', children: '3', key:3  },
  ]
}

const oldVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '3', key:3 },
    { type: 'p', children: '2', key:2  },
    { type: 'p', children: '1', key:1  },
  ]
}

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

节点可复用并不意味着只需要简单的处理新旧子节点的顺序变化,子节点的内容可能也会发生变动,所以在移动之前需要打补丁确保内容更新:我们需要对前面处理子节点更新的patchChildren进行完善,主要处理其中新旧子节点都是多个的情况,此时我们才需要使用diff算法处理,其中再使用patch函数去更新可复用节点,具体的处理过程在下文中进行描述:

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {
     //省略代码
    } else if (Array.isArray(n2.children)) {
      //新子节点是一组节点
      if (Array.isArray(n1.children)) {
        //旧子节点也是一组节点,应用diff算法处理
        //省略diff算法代码
        //diff中会使用patch去更新可复用元素
      } else if (typeof n1.children === 'string') {
       //省略代码
      }
    }
  }

三、Vue3快速diff算法的处理过程

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

比如下面的情况:

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

处理前置节点:

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

处理后置节点:

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

我们使用一个patchKeyedChildren函数去实现上述过程:

  function patchKeyedChildren(n1, n2, container) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    //处理前置节点
    let j = 0
    let oldVNode = oldChildren[j]
    let newVNode = newChildren[j]
    
    while (oldVNode.key === newVNode.key) {
        patch(oldVNode, newVNode, container) 
        j++ 
        oldVNode = oldChildren[j] 
        newVNode = newChildren[j]
    }
    
    //处理后置节点
    //将新旧节点的索引指向最后一个子节点
    let oldEnd = oldChildren.length - 1 
    let newEnd = newChildren.length - 1
    
    oldVNode = oldChildren[oldEnd] 
    newVNode = newChildren[newEnd]
    
    while (oldVNode.key === newVNode.key) {
        patch(oldVNode, newVNode, container) 
        oldEnd-- 
        newEnd--
        oldVNode = oldChildren[oldEnd] 
        newVNode = newChildren[newEnd]
    }
       
  }

2、预处理之后的两种情况:需要删除节点、需要新增节点

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

  • 处理前置节点的时候获得的索引j
  • 处理后置节点得到的两个索引newEndoldEnd 利用以上索引可以做出判断:

需要新增节点的情况:oldEnd < j 以及 newEnd >= j:

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

在前文:
Vuejs 数据是如何渲染的?渲染器的简单实现

Vue 的渲染器是如何对节点进行挂载和更新的中实现的patchmountElement方法并不能指定位置去挂载节点,为了能够处理指定节点位置插入节点,我们需要为其增加一个参数anchor,传入锚点元素。

function patch(n1, n2, container, anchor) {
   //...省略代码
  if (typeof type === 'string') {
    if (!n1) {
        //在此处传入锚点以支持新节点按位置插入
      mountElement(n2, container, anchor)
    } else {
      patchElement(n1, n2)
    }
  } else if (type === Text) {
    //...省略代码
}

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

const renderer = createRenderer({
    //...省略代码
    insert(el, parent, anchor = null) {
        //根据锚点元素插入节点
        parent.insertBefore(el, anchor)
    }
})

接下来我们需要完善patchKeyedChildren去处理上述两种情况:
需要新增节点时:

function patchKeyedChildren(n1, n2, container) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    //需要插入新节点
    if (j > oldEnd && j <= newEnd){
         //取得锚点索引
         const anchorIndex = newEnd + 1
         //取得锚点元素
         const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
         //调用patch挂载新节点
         while (j <= newEnd) { 
             patch(null, newChildren[j++], container, anchor) 
         }
    }
       
  }

代码如上,我们首先使用newEnd+1获取锚点索引,并且使用newChildren[anchorIndex].el去获取到锚点元素,其中还做了一个判断如果newEnd是尾部节点那不需要提供锚点元素直接处理即可。

需要删除节点时:

function patchKeyedChildren(n1, n2, container) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    //需要插入新节点
    if (j > oldEnd && j <= newEnd){
        //...省略新增节点逻辑
         
    }else if (j > newEnd && j <= oldEnd) { 
       //卸载节点
        while (j <= oldEnd) { 
            unmount(oldChildren[j++]) 
        } 
    }
       
  }

如上所示,当j<=oldEnd时循环使用umount卸载对应的节点即可。

在实际过程中,很少会有像上述简单的预处理即可完成大部分工作的情况,这个时候就需要进行进一步的判断: 比如以下情况:

在经过预处理之后,只有首尾两个节点被正确更新了,仍然会有多数节点没有被更新。

预处理之后后续需要做的是:

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

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

1.构建source数组

source数组需要去存储新的子节点对应的旧子节点的位置索引,然后去计算一个最长递增子序列,通过最长递增子序列去完成DOM的移动操作

初始化source数组:

function patchKeyedChildren(n1, n2, container) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    //需要插入新节点
    if (j > oldEnd && j <= newEnd){
        //...省略新增节点逻辑
         
    }else if (j > newEnd && j <= oldEnd) { 
       //卸载节点
        while (j <= oldEnd) { 
            unmount(oldChildren[j++]) 
        } 
        //预处理完毕后
    } else{
        //初始化source数组
        const count = newEnd - j + 1
        const source = new Array(count)
        source.fill(-1)
    }
       
  }

source数组的长度等于预处理之后剩余节点的长度也就是newEnd - j + 1,我们使用fill将数组中的元素填充为-1初始化其中的值

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

如上key为p-3的新子节点在旧子节点中的索引为2,所以source数组的第一项需要被填充为2keyp-4的新子节点在旧子节点为3,所以source数组的第二项的值为3,以此类推。 在这个过程中需要嵌套两个for循环去遍历新旧子节类似下面的过程:

for (let i = oldStart; i <= oldEnd; i++) { 
    const oldVNode = oldChildren[i] 
    // 遍历新的一组子节点 
    for (let k = newStart; k <= newEnd; k++) { 
        const newVNode = newChildren[k] 
        // 找到拥有相同 key 值的可复用节点 
        if (oldVNode.key === newVNode.key) { 
            // 调用 patch 进行更新 
            patch(oldVNode, newVNode, container) 
            // 最后填充 source 数组 
            source[k - newStart] = i 
        } 
    } 
}

以上做法时间复杂度为O(n^2),在子节点数量增加时会存在性能问题。 优化的办法是先遍历新的一组子节点,根据子节点的位置和key生成一张索引表,然后再遍历旧的一组子节点,利用节点的key在索引表中找到对应的新子节点的位置,以此填充source数组。

const oldStart = j
const newStart = j
const keyIndex = {}
for(let i = newStart; i <= newEnd; i++) {
    keyIndex[newChildren[i].key] = i
}
for(let i = oldStart; i <= oldEnd; i++) {
  oldVNode = oldChildren[i]
  const k = keyIndex[oldVNode.key]
  if (typeof k !== 'undefined') {
    newVNode = newChildren[k]
    patch(oldVNode, newVNode, container)
    source[k - newStart] = i
  } else {
    unmount(oldVNode)
  }
}

优化后的代码如上所示:
首先将预处理之后的j值作为遍历新旧节点开始时的索引,定义一个对象keyIndex作为索引表,遍历预处理之后剩余的一组新子节点,将新子节点newChildren[i]的key值与其位置索引放入索引表中。 遍历旧子节点,在遍历时,我们可以通过当前节点的keykeyIndex索引表中获取从而拿到当前遍历的旧子节点的oldChildren[i]对应的新节点的位置keyIndex[oldVNode.key],如果位置存在,说明节点可复用,使用patch打补丁,并且使用当前旧节点的索引i对source数组进行填充。

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

需要添加标识有:

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

const oldStart = j
const newStart = j
let moved = false
let pos = 0
const keyIndex = {}
for(let i = newStart; i <= newEnd; i++) {
    keyIndex[newChildren[i].key] = i
}
let patched = 0
for(let i = oldStart; i <= oldEnd; i++) {
    oldVNode = oldChildren[i]
    if (patched < count) {
      const k = keyIndex[oldVNode.key]
      if (typeof k !== 'undefined') {
        newVNode = newChildren[k]
        patch(oldVNode, newVNode, container)
        patched++
        source[k - newStart] = i
        // 判断是否需要移动
        if (k < pos) {
          moved = true
        } else {
          pos = k
        }
      } else {
        // 没找到
        unmount(oldVNode)
      }
    } else {
      unmount(oldVNode)
    }
}

4.处理节点的移动:

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

1.最长递增子序列:

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

如上最长递增子序列对应的旧节点为key为p-3p-4,对应在新子节点的位置为01

最长递增子序列的意义:通过最长递增子序列得到的索引可以提示我们哪些元素的相对位置,在子节点更新后并未发生变化,我们可以保留这些节点的相对位置,然后去处理和移动其他位置。如上p-3和p-4的相对位置在更新之后并未发生变化,即新节点中的索引为01的元素不需要移动。这里我们省略求最长递增子序列的方法,直接将其当作函数lis处理source数组的结果

const seq = lis(source)

2.根据最长递增子序列移动节点:

创建两个索引辅助移动:

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

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

  • source[i] === -1: 节点不存在,需要挂载新节点
  • i!==seq[s]:节点需要移动,
  • i===seq[s]:节点无需移动,将s递减并再次进行比较

完善patchKeyedChildren去处理这几种情况:

function patchKeyedChildren(n1, n2, container) {
  //省略预处理和构造source数组代码
  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 的节点是全新的节点,应该将其挂载
       
      } else if (i !== seq[j]) {
      
        // 说明该节点需要移动
      } else {
        // 当 i === seq[j] 时,说明该位置的节点不需要移动
        // 并让 s 指向下一个位置
        s--
      }
    }
  }
}
}

节点不存在情况具体处理

if (source[i] === -1) {
    // 该节点在新的一组子节点中的真实位置索引
    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)
}

代码如上所示:当新子节点是新节点时直接获取,该节点的位置,即索引,并且加一获得锚点用于挂载元素,如果元素本身就是最后一个元素 nextPos < newChildren.length,则无需锚点。 此时p-7处理完成,继续向上处理p-2

节点需要移动的情况

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)
}

逻辑和节点不存在的情况类似,只是移动节点通过insert函数去完成。此时处理的结果如下

节点不需要移动的情况 对于p-3p-4来说,source[i] !== -1,并且i === seq[s],即节点无需移动只需更新s的值即可

  s--

依此类推直到循环结束,子节点全部更新完毕,该过程完整代码如下:

  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--
      }
    }
  }
}

总结:

  • 使用 diff 算法的原因

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

    • 节点复用是通过比较节点的 key类型来实现的。相同的 key类型表明两个节点可以被视为同一个,从而复用以减少 DOM 操作。
  • Vue 3 diff算法的过程

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

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

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

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部