Diff 算法 · 前端笔记

[TOC] # React 的核心思想 React 最为核心的就是 Virtual DOM 和 Diff 算法。React 在内存中维护一颗虚拟 DOM 树，当数据发生改变时（state & props），会自动的更新虚拟 DOM，获得一个新的虚拟 DOM 树，然后通过 Diff 算法，比较新旧虚拟 DOM 树，找出最小的有变化的部分，将这个变化的部分（Patch）加入队列，最终批量的更新这些 Patch 到实际的 DOM 中。 # 传统 diff 算法将一颗 Tree 通过最小操作步数映射为另一颗 Tree，这种算法称之为 Tree Edit Distance（树编辑距离）。如图： ![](https://img.kancloud.cn/22/eb/22ebf5aef8e2dff007e98a4432b0b622_1232x718.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](http://vldb.org/pvldb/vol5/p334_mateuszpawlik_vldb2012.pdf) # React diff 传统 diff 算法其时间复杂度最优解是 O(n^3)，那么如果有 1000 个节点，则一次 diff 就将进行 10 亿次比较，这显然无法达到高性能的要求。而 React 通过大胆的假设，并基于假设提出相关策略，成功的将 O(n^3) 复杂度的问题转化为 O(n) 复杂度的问题。 **两个假设** 为了优化 diff 算法，React 提出了两个假设： 1. 两个不同类型的元素会产生出不同的树 2. 开发者可以通过`key`prop 来暗示哪些子元素在不同的渲染下能保持稳定 **三个策略** 基于这上述两个假设，React 针对性的提出了三个策略以对 diff 算法进行优化： 1. Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计 2. 拥有相同类型的两个组件将会生成相似的树形结构，拥有不同类型的两个组件将会生成不同树形结构 3. 对于同一层级的一组子节点，它们可以通过唯一 key 进行区分 **diff 具体优化** 基于上述三个策略，React 分别对以下三个部分进行了 diff 算法优化 * tree diff * component diff * element diff ## tree diff React 只对虚拟 DOM 树进行分层比较，不考虑节点的跨层级比较。如下图： ![](https://img.kancloud.cn/3b/96/3b9628dae811626aab9a017ddf2b4cb6_1120x706.png) 如上图，React 通过 updateDepth 对虚拟 Dom 树进行层级控制，只会对相同颜色框内的节点进行比较，根据对比结果，进行节点的新增和删除。如此只需要遍历一次虚拟 Dom 树，就可以完成整个的对比。 如果发生了跨层级的移动操作，如下图： ![](https://img.kancloud.cn/a4/c7/a4c75fff9eb8f5a7c4452a508c824b0a_1038x686.png) 通过分层比较可知，React 并不会复用 B 节点及其子节点，而是会直接删除 A 节点下的 B 节点，然后再在 C 节点下创建新的 B 节点及其子节点。因此，如果发生跨级操作，React 是不能复用已有节点，可能会导致 React 进行大量重新创建操作，这会影响性能。所以 React 官方推荐尽量避免跨层级的操作。 ## component diff React 是基于组件构建的，对于组件间的比较所采用的策略如下： * 如果是同类型组件，首先使用`shouldComponentUpdate()`方法判断是否需要进行比较，如果返回`true`，继续按照 React diff 策略比较组件的虚拟 DOM 树，否则不需要比较 * 如果是不同类型的组件，则将该组件判断为 dirty component，从而替换整个组件下的所有子节点 ![](https://img.kancloud.cn/33/51/3351f1b6961880235a9644e8de029516_1630x872.png) 如上图，虽然组件 C 和组件 H 结构相似，但类型不同，React 不会进行比较，会直接删除组件 C，创建组件 H。 从上述 component diff 策略可以知道： 1. 对于不同类型的组件，默认不需要进行比较操作，直接重新创建。 2. 对于同类型组件，通过让开发人员自定义`shouldComponentUpdate()`方法来进行比较优化，减少组件不必要的比较。如果没有自定义，`shouldComponentUpdate()`方法默认返回`true`，默认每次组件发生数据（state & props）变化时，都会进行比较。 ## element diff element diff 涉及三种操作：移动、创建、删除。对于同一层级的子节点，对于是否使用 key 分别进行讨论。 对于不使用 key 的情况，如下图： ![](https://img.kancloud.cn/9b/4f/9b4ffd9fa5718434b1af7fcedf20171a_960x440.png) React 对新老同一层级的子节点对比，发现新集合中的 B 不等于老集合中的 A，于是删除 A，创建 B，依此类推，直到删除 D，创建 C。这会使得相同的节点不能复用，出现频繁的删除和创建操作，从而影响性能。 对于使用 key 的情况，如下图： ![](https://img.kancloud.cn/0b/0d/0b0d0975ba584d4e63fd724dcaa8ff97_1090x494.png) React 首先会对新集合进行遍历，通过唯一 key 来判断老集合中是否存在相同的节点，如果没有则创建，如果有的，则判断是否需要进行移动操作。并且 React 对于移动操作也采用了比较高效的算法，使用了一种顺序优化手段，这里不做详细讨论。 从上述可知，element diff 就是通过唯一 key 来进行 diff 优化，通过复用已有的节点，减少节点的删除和创建操作。 **如何进行 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 则在在更加细节上做了进一步优化。 # 参考资料 * [深入理解React：diff 算法](https://www.cnblogs.com/forcheng/p/13246874.html)