vuejs 设计与实现 - 快速diff算法

这篇具有很好参考价值的文章主要介绍了vuejs 设计与实现 - 快速diff算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Vue.js 2 所采用的双端 Diff 算法。既然快速 Diff 算法如此高效,我们有必要了解它的思路。接下来,我们就着重讨论快速 Diff 算法的实现原理。

相同的前置元素和后置元素

快速 Diff 算法借鉴了纯文本 Diff 算法中预处理的步骤。

案例:

旧的一组子节点:p-1、p-2、p-3。
新的一组子节点:p-1、p-4、p-2、p-3。

通过观察可以发现,两组子节点具有相同的前置节点 p-1,以及相同的后置节点 p-2 和 p-3,如图 下图 所示:
对于相同的前置节点和后置节点,由于它们在新旧两组子节点中的相对位置不变,所以我们无须移动它们,但仍然需要在它们之间打补丁。
vuejs 设计与实现 - 快速diff算法,vue.js,算法,前端

处理前置节点

对于前置节点,我们可以建立索引 j,其初始值为 0,用来指向两组子节点的开头,如图 下图所示:
vuejs 设计与实现 - 快速diff算法,vue.js,算法,前端

然后开启一个 while 循环,让索引 j 递增,直到遇到不相同的节点为止,如下面 patchKeyedChildren 函数的代码所示:

 function patchKeyedChildren(n1, n2, container) {
   const newChildren = n2.children
   const oldChildren = n1.children

   // 处理相同的前置节点
   // 索引 j 指向新旧两组子节点的开头
   let j = 0
   let oldVNode = oldChildren[j]
   let newVNode = newChildren[j]

   // while 循环向后遍历,直到遇到拥有不同 key 值的节点为止
   while(oldVNode.key === newVNode.key) {
       // 调用 patch 函数进行更新
       patch(oldVNode, newVNode, container)
       // 更新索引 j,让其递增
       j++
       oldVNode = oldChildren[j]
       newVNode = newChildren[j]
   }
   
}

在上面这段代码中,我们使用 while 循环查找所有相同的前置节点,并调用 patch 函数进行打补丁,直到遇到 key 值不同的节点为
止。这样,我们就完成了对前置节点的更新。在这一步更新操作过后,新旧两组子节点的状态如图 下图 所示:
vuejs 设计与实现 - 快速diff算法,vue.js,算法,前端

处理后置节点:

这里需要注意的是,当 while 循环终止时,索引 j 的值为 1。接下来,我们需要处理相同的后置节点。由于新旧两组子节点的数量可
能不同,所以我们需要两个索引 newEnd 和 oldEnd,分别指向新旧两组子节点中的最后一个节点,如图 下图 所示:
vuejs 设计与实现 - 快速diff算法,vue.js,算法,前端
然后,再开启一个 while 循环,并从后向前遍历这两组子节点,直到遇到 key 值不同的节点为止,如下面的代码所示:

function patchKeyedChildren(n1, n2, container) {
            const newChildren = n2.children
            const oldChildren = n1.children

            // 处理相同的前置节点
            // 索引 j 指向新旧两组子节点的开头
            let j = 0
            let oldVNode = oldChildren[j]
            let newVNode = newChildren[j]

            // while 循环向后遍历,直到遇到拥有不同 key 值的节点为止
            while(oldVNode.key === newVNode.key) {
                // 调用 patch 函数进行更新
                patch(oldVNode, newVNode, container)
                // 更新索引 j,让其递增
                j++
                oldVNode = oldChildren[j]
                newVNode = newChildren[j]
            }

 +           // 处理后置节点:
            // 索引 oldEnd 指向旧的一组子节点的最后一个节点
 +           let oldEnd = oldChildren.length - 1
            
            // 索引 newEnd 指向新的一组子节点的最后一个节点
 +           let newEnd = newChildren.length - 1

 +           oldVNode = oldChildren[oldEnd]
 +           newVNode = newChildren[newEnd]

            // while 循环从后向前遍历,直到遇到拥有不同 key 值的节点为止
 +           while(oldVNode.key === newVNode.key) {

                // 调用 patch 函数进行更新
 +               patch(oldVNode, newVNode, container)

                // 递减 oldEnd 和 nextEnd
  +              oldEnd --
  +              newEnd--
  +              oldVNode = oldChildren[oldEnd]
  +              newVNode = newChildren[newEnd]
            }
        }

与处理相同的前置节点一样,在 while 循环内,需要调用 patch函数进行打补丁,然后递减两个索引 oldEnd、newEnd 的值。在这一步更新操作过后,新旧两组子节点的状态如图 下图 所示:
vuejs 设计与实现 - 快速diff算法,vue.js,算法,前端

新增:

观察上图:当相同的前置节点和后置节点被处理完毕后,旧的一组子节点已经全部被处理了,而在新的一组子节点中,还遗留了一个未被处理的节点 p-4。其实不难发现,节点 p-4 是一个新增节点。那么,如何用程序得出“节点 p-4 是新增节点”这个结论呢?这需要我们观察三个索引 j、newEnd 和 oldEnd 之间的关系。

  • 条件一: oldEnd < j成立:说明在预处理过程中,所有旧子节点都处理完毕了。
  • 条件二:newEnd >= j成立:说明在预处理过后,在新的一组子 节点中,仍然有未被处理的节点,而这些遗留的节点将被视作新增节点。
    如果条件一和条件二同时成立,说明在新的一组子节点中,存在遗留节点,且这些节点都是新增节点。因此我们需要将它们挂载到正确的位置,如下图 所示:
    vuejs 设计与实现 - 快速diff算法,vue.js,算法,前端
    在新的一组子节点中,索引值处于 j 和 newEnd 之间的任何节点都需要作为新的子节点进行挂载。那么,应该怎样将这些节点挂载到正确位置呢?这就要求我们必须找到正确的锚点元素。观察图 上图 中新的一组子节点可知,新增节点应该挂载到节点 p-2 所对应的真实DOM 前面。所以,节点 p-2 对应的真实 DOM 节点就是挂载操作的锚点元素。有了这些信息,我们就可以给出具体的代码实现了,如下所示:
function patchKeyedChildren(n1, n2, container) {
            const newChildren = n2.children
            const oldChildren = n1.children

            // 处理相同的前置节点
            // 索引 j 指向新旧两组子节点的开头
            let j = 0
            let oldVNode = oldChildren[j]
            let newVNode = newChildren[j]

            // while 循环向后遍历,直到遇到拥有不同 key 值的节点为止
            while(oldVNode.key === newVNode.key) {
                // 调用 patch 函数进行更新
                patch(oldVNode, newVNode, container)
                // 更新索引 j,让其递增
                j++
                oldVNode = oldChildren[j]
                newVNode = newChildren[j]
            }

            // 处理后置节点:
            // 索引 oldEnd 指向旧的一组子节点的最后一个节点
            let oldEnd = oldChildren.length - 1
            
            // 索引 newEnd 指向新的一组子节点的最后一个节点
            let newEnd = newChildren.length - 1

            oldVNode = oldChildren[oldEnd]
            newVNode = newChildren[newEnd]

            // while 循环从后向前遍历,直到遇到拥有不同 key 值的节点为止
            while(oldVNode.key === newVNode.key) {

                // 调用 patch 函数进行更新
                patch(oldVNode, newVNode, container)

                // 递减 oldEnd 和 nextEnd
                oldEnd --
                newEnd--
                oldVNode = oldChildren[oldEnd]
                newVNode = newChildren[newEnd]
            }

            // 新增
            // 预处理完毕后,如果满足如下条件,则说明从 j --> newEnd 之间的节点应作 为新节点插入
  +          if(j > oldEnd && j <= newEnd) {
                // 锚点索引
  +              const anchorIndex = newEnd + 1
                // 锚点元素
  +              const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
  +              while(j <= newEnd) {
  +                  patch(null, newChildren[j++], container, anchor)
  +              }
            }
        }

在上面这段代码中,首先计算锚点的索引值(即 anchorIndex) 为newEnd + 1。如果小于新的一组子节点的数量,则说明锚点元素 在新的一组子节点中,所以直接使用 newChildren[anchorIndex].el 作为锚点元素;否则说明索引 newEnd 对应的节点已经是尾部节点了,这时无须提供锚点元素。有了 锚点元素之后,我们开启了一个 while 循环,用来遍历索引 j 和索引 newEnd 之间的节点,并调用 patch 函数挂载它们。

删除
案例:
  • 旧的一组子节点:p-1、p-2、p-3。
  • 新的一组子节点:p-1、p-3。

vuejs 设计与实现 - 快速diff算法,vue.js,算法,前端
当前置节点,后置节点都处理完成,后剩余未被处理的节点如下图所示:
vuejs 设计与实现 - 快速diff算法,vue.js,算法,前端

索引 j 和索引 oldEnd 之间的任何节点都应该被卸载,具体实现如下:

function patchKeyedChildren(n1, n2, container) {
            const newChildren = n2.children
            const oldChildren = n1.children

            // 处理相同的前置节点
            // 索引 j 指向新旧两组子节点的开头
            let j = 0
            let oldVNode = oldChildren[j]
            let newVNode = newChildren[j]

            // while 循环向后遍历,直到遇到拥有不同 key 值的节点为止
            while(oldVNode.key === newVNode.key) {
                // 调用 patch 函数进行更新
                patch(oldVNode, newVNode, container)
                // 更新索引 j,让其递增
                j++
                oldVNode = oldChildren[j]
                newVNode = newChildren[j]
            }

            // 处理后置节点:
            // 索引 oldEnd 指向旧的一组子节点的最后一个节点
            let oldEnd = oldChildren.length - 1
            
            // 索引 newEnd 指向新的一组子节点的最后一个节点
            let newEnd = newChildren.length - 1

            oldVNode = oldChildren[oldEnd]
            newVNode = newChildren[newEnd]

            // while 循环从后向前遍历,直到遇到拥有不同 key 值的节点为止
            while(oldVNode.key === newVNode.key) {

                // 调用 patch 函数进行更新
                patch(oldVNode, newVNode, container)

                // 递减 oldEnd 和 nextEnd
                oldEnd --
                newEnd--
                oldVNode = oldChildren[oldEnd]
                newVNode = newChildren[newEnd]
            }

            // 新增
            // 预处理完毕后,如果满足如下条件,则说明从 j --> newEnd 之间的节点应作 为新节点插入
            if(j > oldEnd && j <= newEnd) {
                // 锚点索引
                const anchorIndex = newEnd + 1
                // 锚点元素
                const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
                while(j <= newEnd) {
                    patch(null, newChildren[j++], container, anchor)
                }
   +         } else if (j > newEnd && j <= oldEnd) {
                // 删除
                // j -> oldEnd 之间的节点应该被卸载
    +            while(j <= oldEnd) {
    +                unmount(oldChildren[j++])
                }
            }
        }

在上面这段代码中,我们新增了一个 else…if 分支。当满足条件j > newEnd && j <= oldEnd时,则开启一个while循环,并调用unmount 函数逐个卸载这些遗留节点。

移动

有点复杂文章来源地址https://www.toymoban.com/news/detail-636713.html

到了这里,关于vuejs 设计与实现 - 快速diff算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • vuejs 设计与实现 - 组件的实现原理

    如果是组件则: vnode .type的值是一个对象。 如下: 为了让 渲染器 能处理组件类型的虚拟节点,我们还需要在patch函数中对组件类型的虚拟节点进行处理,如下: 一个组件必须包含一个渲染函数,即render函数,并且渲染函数的返回值应该是虚拟dom。如下: 有了基本的结构,

    2024年02月12日
    浏览(33)
  • 前端(八)——深入探索前端框架中的Diff算法:优化视图更新与性能提升

    😊博主:小猫娃来啦 😊文章核心: 深入探索前端框架中的Diff算法:优化视图更新与性能提升 前端框架中的diff算法是一种比较两个虚拟DOM树之间差异的算法。在更新页面时,为了提高性能,前端框架通常会先生成新的虚拟DOM树,然后通过diff算法比较新旧虚拟DOM树的差异,

    2024年02月16日
    浏览(49)
  • vuejs 设计与实现 - 渲染器的设计

    本节,我们暂时将渲染器限定在 DOM 平台。既然渲染器用来渲染真实 DOM 元素,那么严格来说,下面的函数就是一个合格的渲染器: 使用渲染器: 如果页面中存在 id 为 app 的 DOM 元素,那么上面的代码就会将 插入到该 DOM 元素内。 当然,我们不仅可以渲染静态的字符串,还可以

    2024年02月13日
    浏览(36)
  • 【vue】diff 算法详解

    diff算法是一种通过 同层的树节点 进行比较的高效算法         diff算法的目的就是找出新旧不同虚拟DOM之间的差异,使最小化的更新视图,所以 diff 算法本质上就是比较两个js对象的差异 特点         1. 比较只会在同层级进行,不会跨层级比较         2. 在diff比较的构成

    2024年02月02日
    浏览(34)
  • vue的diff算法原理

    vue基于虚拟DOM做更新,diff的核心就是比较两个虚拟节点的差异。 vue的diff算法是 平级比较 ,不考虑跨级比较的情况。内部采用 深度递归 + 双指针 的方式进行比较 先比较是否是相同节点 key tag (标识,标签名) 相同节点比较属性,并复用老节点(将老的虚拟dom复用给新的虚拟

    2023年04月25日
    浏览(36)
  • vue diff 双端比较算法

    使用四个变量 oldStartIdx、oldEndIdx、newStartIdx 以及 newEndIdx 分别存储旧 children 和新 children 的两个端点的位置索引 除了位置索引之外,还需要拿到四个位置索引所指向的 VNode 使用旧 children 的头一个 VNode 与新 children 的头一个 VNode 比对,即 oldStartVNode 和 newStartVNode 比较对。 使用

    2024年02月14日
    浏览(43)
  • vuejs 设计与实现 - 渲染器 - 挂载与更新

    渲染器的核心功能:挂载与更新 1.2挂载子节点 (vnode.children) vnode.children可以是字符串类型的,也可以是数组类型的,如下: 可以看到,vnode.children 是一个数组,它的每一个元素都是一个独立的虚拟节点对象。这样就形成了树型结构,即虚拟DOM 树。 为了完成子节点的渲染,我们

    2024年02月13日
    浏览(34)
  • 【源码系列#06】Vue3 Diff算法

    专栏分享:vue2源码专栏,vue3源码专栏,vue router源码专栏,玩具项目专栏,硬核💪推荐🙌 欢迎各位ITer关注点赞收藏 🌸🌸🌸 Vue2 Diff算法可以参考此篇文章 【Vue2.x源码系列08】Diff算法原理 两个不同虚拟节点不需要进行比较,直接移除老节点,将新的虚拟节点渲染成真实D

    2024年01月17日
    浏览(42)
  • vue和react的diff算法源码

    Vue.js 的 Diff 算法主要基于 Snabbdom,以下是 Vue.js 中虚拟 DOM Diff 算法的简化版伪代码,以便说明其基本思想: 这里主要关注 patchVnode 函数,它是 Diff 算法的核心。Vue.js 的 Diff 算法采用了一种双端比较的策略,具体步骤如下: 1.同层级比较: 首先比较新旧节点的同层级,通过

    2024年03月15日
    浏览(54)
  • vue diff 前后缀+最长递增子序列算法

    如上图所示,新旧 children 拥有相同的前缀节点和后缀节点 对于前缀节点,我们可以建立一个索引,指向新旧 children 中的第一个节点,并逐步向后遍历,直到遇到两个拥有不同 key 值的节点为止 对于相同的后缀节点,由于新旧 children 中节点的数量可能不同,所以我们需要两个

    2024年02月13日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包