Skip to content

Latest commit

 

History

History
150 lines (108 loc) · 8.21 KB

9.diff算法.md

File metadata and controls

150 lines (108 loc) · 8.21 KB

diff算法

课程地址 https://xiaochen1024.com/courseware/60b1b2f6cf10a4003b634718/60b1b354cf10a4003b634721

参考文章 15张图，20分钟吃透Diff算法核心原理，我说的！！！https://juejin.cn/post/6994959998283907102 聊一聊Diff算法（React、Vue2.x、Vue3.x）https://zhuanlan.zhihu.com/p/149972619

Diff算法概念

Diff算法是一种对比算法。对比两者是旧虚拟DOM和新虚拟DOM，对比出是哪个虚拟节点更改了，找出这个虚拟节点，并只更新这个虚拟节点所对应的真实节点，而不用更新其他数据没发生改变的节点，实现精准地更新真实DOM，进而提高效率。 使用虚拟DOM算法的损耗计算： 总损耗 = 虚拟DOM增删改+（与Diff算法效率有关）真实DOM差异增删改+（较少的节点）排版与重绘 直接操作真实DOM的损耗计算： 总损耗 = 真实DOM完全增删改+（可能较多的节点）排版与重绘

Diff算法的原理

传统Diff算法

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

左侧树每个节点与右侧树每个节点对比查找差异, 算法复杂度能达到O(n^2), 查找完差异后还需计算最小转换方式,最终达到的算法复杂度是O(n^3)

优化的Diff算法

vue和react的虚拟DOM的diff算法大致相同，其核心是基于两个简单的假设: 两个相同的组件产生类似的DOM结构，不同的组件产生不同的DOM结构 同一层级的一组节点，他们可以通过唯一的id进行区分

(优化的)diff三点策略:

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

React优化Diff算法

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

  • tree diff
  • component diff
  • element diff

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

component diff:

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

component vs

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

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

不使用key的情况 不使用key的话，react对新老集合对比，发现新集合中B不等于老集合中的A，于是删除了A，创建了B， 依此类推直到删除了老集合中的D，创建了C于新集合。 酱紫会产生渲染性能瓶颈，于是react允许添加key进行区分

使用key的情况 react首先对新集合进行遍历，for( name in nextChildren),通过唯一key来判断老集合中是否存在相同的节点， 如果没有的话创建，如果有的话，if (preChild === nextChild ) 进行移动操作 移动优化 在移动前，会将节点在新集合中的位置和在老集合中lastIndex进行比较， 如果if (child._mountIndex < lastIndex) 进行移动操作，否则不进行移动操作。 这是一种顺序移动优化。只有在新集合的位置 小于 在老集合中的位置 才进行移动。

Vue优化Diff

Vue2的核心Diff算法采用了双端比较的算法，同时从新旧children的两端开始进行比较，借助key值找到可复用的节点，再进行相关操作。 相比React的Diff算法，同样情况下可以减少移动节点次数，减少不必要的性能损耗，更加的优雅 oldCh和newCh各有两个头尾的变量StartIdx和EndIdx，它们的2个变量相互比较，一共有4种比较方式。 如果4种比较都没匹配，如果设置了key，就会用key进行比较，在比较的过程中，变量会往中间靠， 一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了，就会结束比较 双端比较

Vue 2.x vs Vue 3.x Vue3.x借鉴了 ivi算法和 和 inferno算法 （求解最长递归子序列）。 在创建VNode时就确定其类型，以及在mount/patch的过程中采用位运算来判断一个VNode的类型， 在这个基础之上再配合核心的Diff算法，使得性能上较Vue2.x有了提升

React Diff流程

在render阶段更新Fiber节点时，我们会调用reconcileChildFibers对比current Fiber和jsx对象构建workInProgress Fiber， 这里current Fiber是指当前dom对应的fiber树，jsx是class组件render方法或者函数组件的返回值。

在reconcileChildFibers中会根据newChild的类型来进入单节点的diff或者多节点diff

diff过程

react diff策略总结:

  1. 只对同级比较，跨层级的dom不会进行复用
  2. 不同类型节点生成的dom树不同，此时会直接销毁老节点及子孙节点，并新建节点
  3. 可以通过key来对元素diff的过程提供复用的线索

单点diff有如下几种情况：

  • key和type相同表示可以复用节点
  • key不同直接标记删除节点，然后新建节点
  • key相同type不同，标记删除该节点和兄弟节点，然后新创建节点

多节点diff

在源码中多节点diff有三个for循环遍历（并不意味着所有更新都有经历三个遍历，进入循环体有条件，也有条件跳出循环）， 第一个遍历处理节点的更新（包括props更新和type更新和删除）， 第二个遍历处理其他的情况（节点新增），其原因在于在大多数的应用中，节点更新的频率更加频繁， 第三个处理位节点置改变

第一次遍历 因为老的节点存在于 current Fiber 中，所以它是个链表结构， 还记得Fiber双缓存结构嘛，节点通过 child 、 return 、sibling 连接， 而newChildren存在于jsx当中，所以遍历对比的时候， 首先让newChildren[i]与oldFiber对比，然后让i++、nextOldFiber = oldFiber.sibling。 在第一轮遍历中，会处理三种情况，其中第1，2两种情况会结束第一次循环

  1. key不同，第一次循环结束
  2. newChildren或者oldFiber遍历完，第一次循环结束
  3. key同type不同，标记oldFiber为DELETION
  4. key相同type相同则可以复用 ​ newChildren遍历完，oldFiber没遍历完，在第一次遍历完成之后将oldFiber中没遍历完的节点标记为DELETION，即删除的DELETION Tag

第二个遍历 第二个遍历考虑三种情况:

  1. newChildren和oldFiber都遍历完：多节点diff过程结束
  2. newChildren没遍历完，oldFiber遍历完，将剩下的newChildren的节点标记为Placement，即插入的Tag
  3. newChildren和oldFiber没遍历完，则进入节点移动的逻辑

第三个遍历 主要逻辑在placeChild函数中 例如更新前节点顺序是ABCD，更新后是ACDB

  1. newChild中第一个位置的A和oldFiber第一个位置的A，key相同可复用，lastPlacedIndex=0
  2. newChild中第二个位置的C和oldFiber第二个位置的B，key不同跳出第一次循环，将oldFiber中的BCD保存在map中
  3. newChild中第二个位置的C在oldFiber中的index=2 > lastPlacedIndex=0不需要移动，lastPlacedIndex=2
  4. newChild中第三个位置的D在oldFiber中的index=3 > lastPlacedIndex=2不需要移动，lastPlacedIndex=3
  5. newChild中第四个位置的B在oldFiber中的index=1 < lastPlacedIndex=3,移动到最后