React-diff

作者: 太_2_真_人 | 来源:发表于2020-05-08 00:05 被阅读0次

React是根据Virtual DOM的对比来更新DOM的。这种用来对比的方法被称为diff算法，该算法由fb进一步的优化，使得React的渲染性能得到进一步提升。

1. 传统diff

传统diff算法通过循环递归对节点进行依次对比，效率低下，使得算法复杂度为O(n^3)，如果节点数过于庞大，即使cpu的计算速度达到30亿次/s，也很难在1s内计算出结果。

1）Tree edit distance（树的编辑距离）

从左图修改成右图

image

删除ul节点
添加p节点
添加text

在递归过程中依次将当前节点拆分成子树，然后依次计算每个子树的edit distance，所以上图的树的最小编辑距离为3

2）Tree edit distance算法演进

image

2. React的diff

diff算法的复杂度取决于策略，React采用的三大策略将diff复杂度由O(n^3)转化为O(n)，效果提升如图：

image

三大策略分别为：

tree diff
- React对树的算法进行了简洁的优化，由于DOM节点操作涉及到跨层级的移动操作少到可以忽略不计，所以React只对树进行分层比较。当发现节点已经不存在时，会删除该节点及所有子节点，不回再做多余的遍历比较，只需要对树进行依次比较即可。
image
- 如果涉及到了DOM的跨层级操作，React只会执行添加和删除2个操作，先添加一个新节点，然后添加子节点，再删除旧节点。如下图，执行步骤为： create A => create B => create C => delete A
  image
  A节点会被重新创建而不是移动，所以React官方建议不要进行DOM节点的跨层级操作，可以通过css属性的隐藏、显示对节点操作，而不是真正的删除、插入节点。
component diff

React是基于组件构建应用的，对组件的diff也非常简洁
- 同一类型组件，按照原策略进行Visual DOM对比
- 同一类型组件，Visual DOM没发生任何变化，React提供一个shouldComponentUpdate api供用户手动选择是否需要进行diff比较，如果使用了forceUpdate则强制比较，shouldComponentUpdate失效。
- 不同类型组件，将原有组件标记为dirty component，删除旧组件重新添加新组件。
element diff

当节点处于同一层时，diff提供了3种节点操作
- INSERT_MARKUP
  - 组件C不在集合（AB）中，需要插入操作
- REMOVE_NODE
  - 组件C在集合（ABC）中，集合需要变成新集合（AB），则需要删除C
  - 组件C在集合（ABC）中，但C改变了，不能复用和移动，需要删除C在新建C
- MOVE_EXISTING
  - 组件C在集合（ABC）中，集合更新时需要将C和A的位置调换，传统diff需要将C移动到A的位置，并将C和旧A进行diff，再添加C，React diff只需要将C移动到A位置，并添加一个唯一的key进行区分，直接移动即可。