react16之前diff算法的理解和总结

Love The Way You Lie 2023-10-15 16:52 15阅读 0赞

此篇文章所讨论的是 React 16 以前的 Diff 算法。而 React 16 启用了全新的架构 Fiber，相应的 Diff 算法也有所改变，本片不详细讨论Fiber。

> fiber架构是为了支持react进行可中断渲染，降低卡顿，提升流畅度。
> 
> react16之前的版本，diff虚拟dom时候是一口气完成的。这可能造成卡顿，因为人眼可识别的帧率是1s 60帧，即16ms一帧，如果diff时间超过16ms，阻塞渲染，就会感觉卡顿。
> 
> 为了避免这种情况，需要让diff操作不超过16ms，如果超过16ms，就先暂停，让给浏览器进行渲染操作，后续渲染间隙再继续diff。
> 
> fiber架构就是为了支持这种“可中断渲染”而涉及的。fiber tree是一种数据结构，它把虚拟dom tree连接成一个链表，从而可以让遍历操作可以支持断点重启。

## **React 的核心思想** ##

React 最为核心的就是 Virtual DOM 和 Diff 算法。React 在内存中维护一颗虚拟 DOM 树，当数据发生改变时（state & props），会自动的更新虚拟 DOM，获得一个新的虚拟 DOM 树，然后通过 Diff 算法，比较新旧虚拟 DOM 树，找出最小的有变化的部分，将这个变化的部分（Patch）加入队列，最终批量的更新这些 Patch 到实际的 DOM 中。

## **传统 diff 算法** ##

将一颗 Tree 通过最小操作步数映射为另一颗 Tree，这种算法称之为 Tree Edit Distance（树编辑距离）。如图：![279f9f2db4874cfb873a998ba527c1c6.png][]

上图中，最小操作步数（编辑距离）为 3：

1.  删除 ul 节点
2.  添加 span 节点
3.  添加 text 节点

而 Tree Edit Distance 算法从 1979 年到 2011年，经过了30多年的发展演变，其时间复杂度最终被优化到 O(n^3)，其发展历程大致如下（n 是树中节点的总数）：

> 1.  1979年，Tai 提出了次个非幂级复杂度算法，时间复杂度为 O(m3\*n3)
> 2.  1989年，Zhang and Shasha 将 Tai 的算法进行优化，时间复杂度为 O(m2\*n2)
> 3.  1998年，Klein 将 Zhang and Shasha 的算法再次优化，时间复杂度为 O(n^2\*m\*log(m))
> 4.  2009年，Demiane 提出最坏情况下的计算公式，将时间复杂度控制在 O(n^2\*m\*(1+log(m/n)))
> 5.  2011年，Pawlik and N.Augsten 提出适用于所有形状的树的算法，并将时间复杂度控制在 O(n^3)

这里不会展开讨论 Tree Edit Distance 算法的具体实现和原理，有兴趣可以直接看这篇论文 [A Robust Algorithm for the Tree Edit Distance][]

## **React diff** ##

传统 diff 算法其时间复杂度最优解是 O(n^3)，那么如果有 1000 个节点，则一次 diff 就将进行 10 亿次比较，这显然无法达到高性能的要求。而 React 通过大胆的假设，并基于假设提出相关策略，成功的将 O(n^3) 复杂度的问题转化为 O(n) 复杂度的问题。

**（1）两个假设**

为了优化 diff 算法，React 提出了两个假设：

1.  两个不同类型的元素会产生出不同的树
2.  开发者可以通过 `key` prop 来暗示哪些子元素在不同的渲染下能保持稳定

**（2）三个策略**

基于这上述两个假设，React 针对性的提出了三个策略以对 diff 算法进行优化：

1.  Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计
2.  拥有相同类型的两个组件将会生成相似的树形结构，拥有不同类型的两个组件将会生成不同树形结构
3.  对于同一层级的一组子节点，它们可以通过唯一 key 进行区分

**（3）diff 具体优化**

基于上述三个策略，React 分别对以下三个部分进行了 diff 算法优化

*  tree diff
 *  component diff
 *  element diff

## **tree diff** ##

React 只对虚拟 DOM 树进行分层比较，不考虑节点的跨层级比较。如下图：![bb4bc5546c5c49429eacf4cea6c66c77.png][]

如上图，React 通过 updateDepth 对虚拟 Dom 树进行层级控制，只会对相同颜色框内的节点进行比较，根据对比结果，进行节点的新增和删除。如此只需要遍历一次虚拟 Dom 树，就可以完成整个的对比。

如果发生了跨层级的移动操作，如下图：![38264c2c318944ec883876f8bfa4b045.png][]

通过分层比较可知，React 并不会复用 B 节点及其子节点，而是会直接删除 A 节点下的 B 节点，然后再在 C 节点下创建新的 B 节点及其子节点。因此，如果发生跨级操作，React 是不能复用已有节点，可能会导致 React 进行大量重新创建操作，这会影响性能。所以 React 官方推荐尽量避免跨层级的操作。

## **component diff** ##

React 是基于组件构建的，对于组件间的比较所采用的策略如下：

*  如果是同类型组件，首先使用 `shouldComponentUpdate()`方法判断是否需要进行比较，如果返回`true`，继续按照 React diff 策略比较组件的虚拟 DOM 树，否则不需要比较
 *  如果是不同类型的组件，则将该组件判断为 dirty component，从而替换整个组件下的所有子节点

![cad493fb02df472b9816ff4f96258b0c.png][]

如上图，虽然组件 C 和组件 H 结构相似，但类型不同，React 不会进行比较，会直接删除组件 C，创建组件 H。

从上述 component diff 策略可以知道：

1.  对于不同类型的组件，默认不需要进行比较操作，直接重新创建。
2.  对于同类型组件， 通过让开发人员自定义`shouldComponentUpdate()`方法来进行比较优化，减少组件不必要的比较。如果没有自定义，`shouldComponentUpdate()`方法默认返回`true`，默认每次组件发生数据（state & props）变化时，都会进行比较。

## **element diff** ##

element diff 涉及三种操作：移动、创建、删除。对于同一层级的子节点，对于是否使用 key 分别进行讨论。

对于不使用 key 的情况，如下图：![718dee96d3db449c98d37ce721365b01.png][]

React 对新老同一层级的子节点对比，发现新集合中的 B 不等于老集合中的 A，于是删除 A，创建 B，依此类推，直到删除 D，创建 C。这会使得相同的节点不能复用，出现频繁的删除和创建操作，从而影响性能。

对于使用 key 的情况，如下图：

![使用 key 的情况][key]

React 首先会对新集合进行遍历，通过唯一 key 来判断老集合中是否存在相同的节点，如果没有则创建，如果有的，则判断是否需要进行移动操作。并且 React 对于移动操作也采用了比较高效的算法，使用了一种顺序优化手段，这里不做详细讨论。

从上述可知，element diff 就是通过唯一 key 来进行 diff 优化，通过复用已有的节点，减少节点的删除和创建操作。

**（4）如何进行 diff**

上面已经说完了 React 的 diff 策略和具体优化，这里简单谈一下 React 是如何应用这些策略来进行 diff ：

React 是基于组件构建的，首先可以将整个虚拟 DOM 树，抽象为 React 组件树（每一个组件又是由一颗更小的组件树构成，依次类推），将 React diff 策略应用比较这颗组件树，若其中某个组件需要进行比较，将这个组件看成一颗较小的组件树，继续用 React diff 策略比较这颗较小的组件树，依次类推，直到层次遍历完所有的需要比较的组件。

## **小结** ##

React 通过大胆的假设，制定对应的 diff 策略，将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题

*  通过分层对比策略，对 tree diff 进行算法优化
 *  通过相同类生成相似树形结构，不同类生成不同树形结构以及`shouldComponentUpdate`策略，对 component diff 进行算法优化
 *  通过设置唯一 key 策略，对 element diff 进行算法优化

综上，tree diff 和 component diff 是从顶层设计上降低了算法复杂度，而 element diff 则在在更加细节上做了进一步优化。

[279f9f2db4874cfb873a998ba527c1c6.png]: https://img-blog.csdnimg.cn/279f9f2db4874cfb873a998ba527c1c6.png
[A Robust Algorithm for the Tree Edit Distance]: http://vldb.org/pvldb/vol5/p334_mateuszpawlik_vldb2012.pdf
[bb4bc5546c5c49429eacf4cea6c66c77.png]: https://img-blog.csdnimg.cn/bb4bc5546c5c49429eacf4cea6c66c77.png
[38264c2c318944ec883876f8bfa4b045.png]: https://img-blog.csdnimg.cn/38264c2c318944ec883876f8bfa4b045.png
[cad493fb02df472b9816ff4f96258b0c.png]: https://img-blog.csdnimg.cn/cad493fb02df472b9816ff4f96258b0c.png
[718dee96d3db449c98d37ce721365b01.png]: https://img-blog.csdnimg.cn/718dee96d3db449c98d37ce721365b01.png
[key]: https://img-blog.csdnimg.cn/img_convert/bed35f496e607d64c590f56ac9ed50ac.png