Fram/Lib

VUE3.0更新后的diff算法

字数:2683    阅读时间:14min
阅读量:1883

VUE3.0的diff算法原理相比较vue2.X还是有很大改变的;最重要的改变有以下几点:标记静态节点不再全量对比,前置和后置元素预处理,利用"最长递增子序列"移动节点。

标记静态节点

问题背景:在VUE2.X中当一个节点数据发生改变时,VUE会全量对比所有子节点,找出差异,进行复用和更新;然而子节点中的一些静态节点,无论如何是不会被改变的, 重新创建 这些静态节点并参与对比,显然造成了不小的性能浪费。

解决方案:VUE3.0引入了一个叫flag静态标记的东西,在生成虚拟节点的时候,会根据以下节点特点,为节点添加一个静态标记

然后利用这些标记,知道哪些节点会改变,哪些节点不会改变;进而做到静态元素只渲染一次只对比可能会改变的节点

如何标记节点:只这样说还是难直观的看到VUE是怎样标记节点的,我们可以通过一个测试网址来了解一下。例如我们要生成两个虚拟节点:<span>我是一只小小鸟</span> <div>{{meg}}</div>;VUE是这么添加标记的:

静态节点提升:标记完了节点之后,VUE会把所有不参与更新的静态节点提升起来, 只做一次渲染 ,有用到该节点的地方直接复用不再重复渲染;在测试网址里我们可以勾选options-hostStatic来模拟该操作

事件监听缓存:事件监听被视为动态绑定,所以每次都会追踪它的变化,但是因为是同一个函数,所以不用追踪变化,为了优化性能,VUE会将事件监听缓存起来,用到的时候直接复用就行。我们可以通过测试网站勾选options-cacheHandlers来对比一下开启事件侦听器缓存前后的变化(例如渲染虚拟节点<div @click='sss'></div>):

未开启事件监听缓存,有静态标记,每次改变都会重新创建对比
开启事件监听缓存,没有静态标记,节点改变的时候复用缓存的函数就行

patchChildren

从子节点的比较开始说起;patchChildren相当于VUE2.0里的patchVnode,比较子节点的情况:

  • 当patchFlag > 0 时:
    • 子节点有key值的调用:patchKeyedChildren函数进行比较
    • 子节点没有key值的调用:patchUnKeyedChildren函数进行比较
  • 没有patchflag或者patchflag <=0 时:
    • 新子节点是文本节点:删除旧子节点并添加新节点的文本节点
    • 新节点的子节点是数组或者没有
      • 旧子节点是数组
        • 新子节点也是数组,直接调用patchKeyedChildren函数进行full diff
        • 新节点没有子节点,则直接删除
      • 旧子节点是文本或者没有
        • 旧子节点是文本的时候,清空文本
        • 新节点是数组的时候,直接新增

patchUnkeyedChildren

当子节点没有key的时候比较子节点用patchUnkeyedChildren函数;这个函数比较简单,就是遍历新旧子节点最小公共长度部分,然后进行patch,最后把多余子节点卸载,新增的挂载:

patchKeyedChildren

当子节点有key的时候,比较子节点用patchKeyedChildren函数;这个函数算是VUE3.0diff算法的核心了;它首先会进行一个预处理:把相同的前置和后置节点找出来不参与对比,处理只有删除或者添加节点的情况。然后处理剩余的真正需要diff的节点:创建一个map对象存放新节点的key-index映射关系,遍历旧子节点删除多余节点,依次找到新子节点对应旧节点所在的位置,然后存放在一个数组内,最后根据最长递增子序列移动需要移动的数据,并挂载需要新增的节点

预处理

VUE3.0的预处理主要做的工作是找出前置和后置相同节点,使他们不参与diff对比,然后在处理只有添加节点和删除节点的情况,这样我们可以极大提高算法速度(当我们只是添加和删除节点的话根本就不用执行向下更复杂的算法步骤):

前置和后置相同节点预处理:从头部或尾部开始遍历,遇到相同节点执行patch,下标 + 1或 - 1,继续循环,遇到不同节点就跳出循环 ,结束遍历

只有新增或删除节点预处理: 如果旧节点遍历完毕,新节点还有剩余,就新增剩余节点 ; 如果新节点遍历完毕,旧节点还有剩余,就删除剩余节点

记录节点位置

VUE3.0预处理完了之后就开始真正的diff中间剩余节点了;

创建新节点位置映射表:首先用一个生成一个map对象keyToNewIndexMap,创建一个新子节点的key-index映射表

记录新节点在旧节点中的位置:遍历旧子节点,新旧节点对比,找出新子节点在旧子节点中所在的位置,存进一个newIndexToOldIndexMap数组的对应位置里(初始化为[0,0,0...],对应位置存放对应新节点对应旧节点的位置下标 + 1),当旧节点在新节点里无法找到,就删除多余的旧节点

移动节点

记录完节点位置之后就开始移动需要移动的节点了;VUE2.0算法是找到对应节点之后一个个节点进行移动,但是如下图我们知道只需要将移动C到E后边就可以了,再移动D和E就浪费性能了

于是VUE3.0引入了一个叫"最长递增子序列"的概念;那么什么是"最长递增子序列"呢?官方给出的定义是:在一个给定的数值序列中,找到一个子序列,使得这个子序列元素的数值依次递增,并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中可以是不连续的;注意最长递增子序列可能不是唯一的

如此一来我们既可以使用这个"最长递增子序列"作为参照序列,即不需要移动的元素序列,移动那些没有在序列中的元素,就可以达到移动最少的节点进行更新节点的要求;如我们上述移动节点的例子中newIndexToOldIndexMap:[4,5,3,0],这个数组的最长递增子序列是:[4,5] ;也就是说需要操作的节点是[3,0]因为0代表新增,所以我们只需要移动旧节点下标是2(3-1=2)的节点,到对应节点的后边就好(因为是向后移)

总结

至此VUE3.0的算法算是梳理完毕了;其实也不复杂,最重要的就是前置和后置节点的预处理,然后根据"最长递增子序列"最小程度的移动节点

野生小园猿
励志做一只遨游在知识海洋里的小白鲨
查看“野生小园猿”的所有文章 →

发表评论

邮箱地址不会被公开。

相关推荐