diff算法原理 、 Vue、React区别

Myth丶恋晨 2024-03-31 11:06 174阅读 0赞

目录

传统Diff算法

React优化Diff算法

Vue的Diff算法

在了解Vue和React的区别之前,我们首先来了解一下MVC和MVVM架构,这个知识点有助于我们对后续知识的了解。一提到前端框架,相信大家都对Vue和React不陌生,这两个前端框架都是比较主流的,用户也都比较多,但是我们在使用这些框架的时候,是否对这两个框架之间的区别有所了解呢?接下来,让我们来一起的系统梳理这两个框架的区别是什么吧~

MVC架构
首先MVC指的是Model-View-Controller,分别代表着模型层、视图层、控制器。

Model(模型层),主要管理的是业务模型的数据和处理数据的逻辑。

View(视图层)主要是接收用户的交互请求并展示数据信息给用户。

Controller(控制器层)主要担任的是Model和View之间的桥梁,用于控制程序的流程。Controller负责确保View可以访问到需要显示的Model对象的数据,View接收到用户的交互请求之后,会将请求转发给控制器,控制器解析请求之后,会交给对应的Model处理。

MVVM架构
MVVM架构指的是Model-View-ViewModel,我们可以看到MVVM架构和MVC架构的区别在于有一个ViewModel部分,首先我们要知道在已经有了MVC架构的时候,为什么还要衍生出MVVM架构,这是因为View中很多控件的数据类型和Model中的属性不相同,例如Model中的时间数据可能是一串数字,View想要展示成日期的格式,这就需要一种转化,这个转换如果放在View不合适,因为View中不应该出现逻辑代码,放在Model中也不合适,这回导致Model臃肿庞大,因为这种问题的存在诞生了ViewModel,这一层可以帮助View转化为相应的数据给Model或者从Model中转化成View可以显示的内容。

Vue和React的区别是什么?
一、核心思想不同
Vue的核心思想是尽可能的降低前端开发的门槛,是一个灵活易用的渐进式双向绑定的MVVM框架。

React的核心思想是声明式渲染和组件化、单向数据流,React既不属于MVC也不属于MVVM架构。

React1:声明式是什么意思?
声明式与之相对应的是命令式,命令式指的是通过DOM操作一步步把网页变成想要的样子,而声明式则是只需要通过状态去形容最后的网页长什么样子即可。

React2:组件化是什么意思?
组件化指的是尽可能的将页面拆分成一个个较小的、可以复用的组件,这样让我们的代码更加方便组织和管理,并且拓展性页更强。

React3:如何理解React的单向数据流?
React的单向数据流指的是数据主要从父节点通过props传递到子节点,如果顶层某个props改变了,React会重新渲染所有的子节点,但是单向数据流并非单向绑定,React想要从一个组件去更新另一个组件的状态,需要进行状态提升,即将状态提升到他们最近的祖先组件中,触发父组件的状态变更,从而影响另一个组件的显示。单向数据流的好处是能够保证状态改变的可追溯性,假如,父组件维护了一个状态,子组件如果能够随意更改父组件的状态,那么各组件的状态改变就会变得难以追溯。

二、组件写法上不同
Vue的组件写法是通过template的单文件组件格式。

React的组件写法是JSX+inline style,也就是吧HTML和CSS全部写进JavaScript中。

三、Diff算法不同
Diff算法前置知识:虚拟DOM

虚拟Dom,其实很简单,就是一个用来描述真实Dom的对象

它有六个属性,sel表示当前节点标签名,data内是节点的属性,children表示当前节点的其他子标签节点,elm表示当前虚拟节点对应的真实节点(这里暂时没有),key即为当前节点的key,text表示当前节点下的文本,结构类似这样。

  1. let vnode = {
  2. sel: 'ul',
  3. data: {},
  4. children: [
  5. {
  6. sel: 'li', data: { class: 'item' }, text: 'son1'
  7. },
  8. {
  9. sel: 'li', data: { class: 'item' }, text: 'son2'
  10. },
  11. ],
  12. elm: undefined,
  13. key: undefined,
  14. text: undefined
  15. }

在了解Diff算法之前,我们首先要知道什么是虚拟DOM,虚拟DOM是一个用来描述真实DOM的对象,本质是对象。

什么是Diff算法?
Diff算法是一种对比算法,主要是对比旧的虚拟DOM和新的虚拟DOM,找出发生更改的节点,并只更新这些接地那,而不更新未发生变化的节点,从而准确的更新DOM,减少操作真实DOM的次数,提高性能。

Diff算法是深度优先还是广度优先?时间复杂度是多少?
Diff算法是深度优先算法,时间复杂度是O(n³)。

传统Diff算法

处理方案: 循环递归每一个节点

传统diff

c297eb7dd1054990856c505eb3cc0927.png

如上所示, 左侧树a节点依次进行如下对比:

a->e、a->d、a->b、a->c、a->a

之后左侧树其它节点b、c、d、e亦是与右侧树每个节点对比, 算法复杂度能达到O(n^2)

查找完差异后还需计算最小转换方式,这其中的原理我没仔细去看,最终达到的算法复杂度是O(n^3)

将两颗树中所有的节点一一对比需要O(n²)的复杂度,在对比过程中发现旧节点在新的树中未找到,那么就需要把旧节点删除,删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n),同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是O(n³)

(优化的)diff三点策略:

  • web UI中DOM节点跨层级的移动操作特别少,可以忽略不计。
  • 拥有相同类型的两个组件将会生成相似的树形结构,拥有不同类型的两个组件将会生成不同树形结构。
  • 对于同一层级的一组自节点,他们可以通过唯一id进行区分。

即, 比较只会在同层级进行, 不会跨层级比较

React优化Diff算法

基于以上优化的diff三点策略,react分别进行以下算法优化

  • tree diff
  • component diff
  • element diff

tree diff

react对树的算法进行了分层比较。react 通过 updateDepth对Virtual Dom树进行层级控制,只会对相同颜色框内的节点进行比较,即同一个父节点下的所有子节点。当发现节点不存在,则该节点和其子节点都会被删除。这样是需要遍历一次dom树,就完成了整个dom树的对比

分层比较 img

3aa6f23ecc3f4093988ad82e99ec2b1e.png

如果是跨层级的移动操作,如图

跨层级操作 img

6323e1dd9e8945bfbb80bdf4e54cfda7.png

当根结点发现A消失了,会删除掉A以及他的子节点。当发现D上多了一个A节点,会创建A(包括其子节点)节点作为子节点

所以:当进行跨层级的移动操作,react并不是简单的进行移动,而是进行了删除和创建的操作,这会影响到react性能。所以要尽量避免跨层级的操作。(例如:控制display来达到显示和隐藏,而不是真的添加和删除dom)

component diff

  • 如果是同类型的组件,则直接对比virtual Dom tree
  • 如果不是同类型的组件,会直接替换掉组件下的所有子组件
  • 如果类型相同,但是可能virtual DOM 没有变化,这种情况下我们可以使用shouldComponentUpdate() 来判断是否需要进行diff

component vs img

eebaf568321041589d9f611be317c4c4.png

如果组件D和组件G,如果类型不同,但是结构类似。这种情况下,因为类型不同,所以react会删除D,创建G。所以我们可以使用shouldComponentUpdate()返回false不进行diff。

针对react15, 16出了新的生命周期

所以:component diff 主要是使用shouldComponentUpdate() 来进行优化

element diff

element diff 涉及三种操作:插入,移动,删除

不使用key的情况 img

067c0a17a586454fae5f9c64f85d9b98.png

不使用key的话,react对新老集合对比,发现新集合中B不等于老集合中的A,于是删除了A,创建了B,依此类推直到删除了老集合中的D,创建了C于新集合。=

酱紫会产生渲染性能瓶颈,于是react允许添加key进行区分

使用key的情况 img075a03d34e2f42a2b9c888a52ce7685b.png

react首先对新集合进行遍历,for( name in nextChildren),通过唯一key来判断老集合中是否存在相同的节点,如果没有的话创建,如果有的话,if (preChild === nextChild ) 进行移动操作

移动优化
在移动前,会将节点在新集合中的位置和在老集合中lastIndex进行比较,如果if (child._mountIndex < lastIndex) 进行移动操作,否则不进行移动操作。这是一种顺序移动优化。只有在新集合的位置 小于 在老集合中的位置 才进行移动。

如果遍历的过程中,发现在新集合中没有,但是在老集合中的节点,会进行删除操作

所以:element diff 通过唯一key 进行diff 优化。

总结:
1.react中尽量减少跨层级的操作。 2.可以使用shouldComponentUpdate() 来避免react重复渲染。 3.添加唯一key,减少不必要的重渲染

Vue的Diff算法

下面是Vue的diff算法的主要流程:

2880b5c493884a13abb07523c237aa72.png

数据发生变化的时候,会触发setter,然后通过Dep类的notify方法去通知所有的订阅者Watcher,订阅者会调用patch方法。

patch方法会通过sameVnode方法来判断当前同层的虚拟节点是否是同一种类型的节点,如果则调用patchVnode方法,不是则直接替换成新的节点。
如果是同一类型的节点,patchVnode会首先找到节点对应的真实DOM,然后判断新旧节点是否是指向的同一个对象,如果则直接return

如果不是则判断文本节点是否相等,不相等则将真实DOM的文本节点改为新节点的文本内容,然后看旧节点和新节点的子节点的关系,如果旧的有新的没有,则删除真实DOM的子节点,如果新有旧没有,则将虚拟节点真实化之后,添加上去,如果二者都有子节点则执行updateChildren函数比较子节点。

  1. function patch (oldVnode, vnode) {
  2. // some code
  3. if (sameVnode(oldVnode, vnode)) {
  4. patchVnode(oldVnode, vnode) //当结构一致时执行patchvnode函数
  5. }
  6. else {//当结构不一样时执行的操作就简单多了,将之前的文本节点替换掉就行
  7. const oEl = oldVnode.el // 当前oldVnode对应的真实元素节点
  8. let parentEle = api.parentNode(oEl) // 父元素
  9. createEle(vnode) // 根据Vnode生成新元素
  10. if (parentEle !== null) {//判断父元素是否为空
  11. api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
  12. api.removeChild(parentEle, oldVnode.el) // 移除以前的旧元素节点
  13. oldVnode = null //解除全局变量的引用,回收内存
  14. }
  15. }
  16. // some code
  17. return vnode //最后更新虚拟dom
  18. }

那么接下来就分析结构一致的情况,那么什么情况下结构是一致的呢,看一下samevnode源码

  1. function sameVnode (a, b) {
  2. return (
  3. a.key === b.key && // key值一致
  4. a.tag === b.tag && // 标签名一致
  5. a.isComment === b.isComment && // 是否都为注释节点
  6. // 是否都定义了data,data包含一些具体信息,例如onclick , style
  7. isDef(a.data) === isDef(b.data) &&
  8. sameInputType(a, b) // 当标签是<input>的时候,type必须相同
  9. )
  10. }

那这些都一致了的话我们就要看他们的内容(文本)和子节点了

  1. patchVnode (oldVnode, vnode) {
  2. const el = vnode.el = oldVnode.el
  3. let i, oldCh = oldVnode.children, ch = vnode.children
  4. if (oldVnode === vnode) return //如果两个节点完全一样就直接return
  5. if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
  6. api.setTextContent(el, vnode.text) //如果是文本节点当两个节点的文本不为空并且不相等是,直接替换
  7. }else {
  8. updateEle(el, vnode, oldVnode)
  9. if (oldCh && ch && oldCh !== ch) {
  10. updateChildren(el, oldCh, ch)
  11. }else if (ch){
  12. createEle(vnode) //create el's children dom
  13. }else if (oldCh){
  14. api.removeChildren(el)
  15. }
  16. }
  17. }

当文本内容不同是直接替换,之后做了如下事情

  • 找到对应的真实dom,称为el
  • 判断VnodeoldVnode是否指向同一个对象,如果是,那么直接return
  • 如果他们都有文本节点并且不相等,那么将el的文本节点设置为Vnode的文本节点。
  • 如果oldVnode有子节点而Vnode没有,则删除el的子节点
  • 如果oldVnode没有子节点而Vnode有,则将Vnode的子节点真实化之后添加到el
  • 如果两者都有子节点,则执行updateChildren函数比较子节点,这一步很重要

updateChildren方法的核心对比思路就是通过首尾指针的方法进行对比。

  1. updateChildren (parentElm, oldCh, newCh) {
  2. let oldStartIdx = 0, newStartIdx = 0
  3. let oldEndIdx = oldCh.length - 1
  4. let oldStartVnode = oldCh[0]
  5. let oldEndVnode = oldCh[oldEndIdx]
  6. let newEndIdx = newCh.length - 1
  7. let newStartVnode = newCh[0]
  8. let newEndVnode = newCh[newEndIdx]
  9. let oldKeyToIdx
  10. let idxInOld
  11. let elmToMove
  12. let before //四个指针
  13. while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { //四个指针往中间走,
  14. //当开始和结束指针位置相反时,表示有一个vnode已经走完了跳出循环
  15. if (oldStartVnode == null) { // 后面用key值时会将已经移动的vnode用null替换,所以这里
  16. //如果遇到了只要将指针往后面移动就行
  17. oldStartVnode = oldCh[++oldStartIdx]
  18. }else if (oldEndVnode == null) {
  19. oldEndVnode = oldCh[--oldEndIdx]
  20. }else if (newStartVnode == null) {
  21. newStartVnode = newCh[++newStartIdx]
  22. }else if (newEndVnode == null) {
  23. newEndVnode = newCh[--newEndIdx]
  24. }else if (sameVnode(oldStartVnode, newStartVnode)) {
  25. patchVnode(oldStartVnode, newStartVnode)
  26. oldStartVnode = oldCh[++oldStartIdx]
  27. newStartVnode = newCh[++newStartIdx]
  28. //头指针和头指针比较如果相同调用patchVnode()这里会有递归知道把后面的更新完才会return,
  29. //最简单的情况是两个内容相同直接return,之后两个头指针往中间走
  30. }else if (sameVnode(oldEndVnode, newEndVnode)) {
  31. patchVnode(oldEndVnode, newEndVnode)
  32. oldEndVnode = oldCh[--oldEndIdx]
  33. newEndVnode = newCh[--newEndIdx]
  34. //同理之后两个尾指针往中间走
  35. }else if (sameVnode(oldStartVnode, newEndVnode)) {
  36. patchVnode(oldStartVnode, newEndVnode)
  37. api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
  38. oldStartVnode = oldCh[++oldStartIdx]
  39. newEndVnode = newCh[--newEndIdx]
  40. //这里的比较会很大的提升性能,将oldvnode的头指针和newnode的尾指针调用patchvonde(),这里和上面
  41. //也是一样的,不同的是这里会在真实dom上将返回的vnode从之前的位置到oldEndVnode指针对应的节点之前,
  42. //之后相同的key值的指针往前面走
  43. }else if (sameVnode(oldEndVnode, newStartVnode)) {
  44. patchVnode(oldEndVnode, newStartVnode)
  45. api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
  46. oldEndVnode = oldCh[--oldEndIdx]
  47. newStartVnode = newCh[++newStartIdx]
  48. //这里会在真实dom上将返回的vnode插入到oldStartVnode指针对应的节点之前
  49. }else {
  50. // 当前面所用情况都没有时就使用key比较,那newvnode的当前头索引在oldvnode的key值里面找
  51. if (oldKeyToIdx === undefined) {
  52. oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
  53. // 有key生成index表
  54. }
  55. idxInOld = oldKeyToIdx[newStartVnode.key]
  56. if (!idxInOld) {
  57. api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
  58. newStartVnode = newCh[++newStartIdx]
  59. //如果新的vnode中的key值在oldvode中不存在,则真实dom的在oldStartVnode前插入现在的newvnode节点,
  60. //指针向后
  61. }
  62. else {
  63. elmToMove = oldCh[idxInOld]
  64. if (elmToMove.sel !== newStartVnode.sel) {
  65. api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
  66. }else {
  67. patchVnode(elmToMove, newStartVnode)
  68. oldCh[idxInOld] = null
  69. api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
  70. }
  71. newStartVnode = newCh[++newStartIdx]
  72. }
  73. //如果存在则在真实dom的oldStartVnode前插入该节点,并将oldvnode的值设置为null,索引后移
  74. }
  75. }
  76. if (oldStartIdx > oldEndIdx) {
  77. before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
  78. addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
  79. //如果oldvnode里面头索引大于尾索引,说明newVnode里面还有节点,这时需要将newvnode里头索引到尾索引
  80. //的node添加到真实dom中
  81. }else if (newStartIdx > newEndIdx) {
  82. removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  83. }
  84. //反之说明需要将oldvnode中多余的值删掉
  85. }

过程可以概括为:oldCh和newCh各有两个头尾的变量StartIdx和EndIdx,它们的2个变量相互比较,一共有4种比较方式。如果4种比较都没匹配,如果设置了key,就会用key进行比较,在比较的过程中,变量会往中间靠,一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了,就会结束比较

f83a65709f3f470b968f113c106a25a9.png

下面是从别处看到的例子

format_png

format_png 1

format_png 2

format_png 3

React的diff和Vue的diff算法的不同之处
vue和react的diff算法都是进行同层次的比较,主要有以下两点不同:

vue对比节点,如果节点元素类型相同,但是className不同,认为是不同类型的元素,会进行删除重建,但是react则会认为是同类型的节点,只会修改节点属性。
vue的列表比对采用的是首尾指针法,而react采用的是从左到右依次比对的方式,当一个集合只是把最后一个节点移动到了第一个,react会把前面的节点依次移动,而vue只会把最后一个节点移动到最后一个,从这点上来说vue的对比方式更加高效。

四、响应式原理不同
React的响应式原理
React主要是通过setState()方法来更新状态,状态更新之后,组件也会重新渲染。

Vue的响应式原理
vue会遍历data数据对象,使用Object.definedProperty()将每个属性都转换为getter和setter,每个Vue组件实例都有一个对应的watcher实例,在组件初次渲染的时候会记录组件用到了那些数据,当数据发生改变的时候,会触发setter方法,并通知所有依赖这个数据的watcher实例调用update方法去触发组件的compile渲染方法,进行渲染数据。

#

发表评论

表情:
评论列表 (有 0 条评论,174人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Virtual DOM diff算法

    首先浏览器加载一个HTML页面时会经过创建DOM 树、创建样式规则(style rules)、构建渲染树(render tree)、布局layout 和 绘制页面(painti