React Diff算法之diff的发展(一)

[SinLv]

React的核心思想

内存中维护一颗虚拟DOM树，数据变化时（setState），自动更新虚拟DOM，得到一棵新树，然后Diff新老虚拟DOM树，找到有变化的部分，得到一个Change(Patch)，将这个Patch加入队列，最终批量更新这些Patch到DOM中。

传统Diff算法

传统diff算法需要循环比较两棵树，所有节点的循环，那么单纯比较次数就是O(n^2)，n*n

每次都需要循环遍历，于是有以下的查找过程：
PA -> LA, PA -> LB, PA -> LC, PA -> LD, PB -> LA, ......
除了查询过程消耗了O(n^2)之外，找到差异后还要计算最小转换方式，最终结果为O(n^3)。
所以，传统的diff算法的时间复杂度为O(n^3)。

React 15的Diff算法

《深入React技术栈》这本书，给出了三种Diff策略分析：Tree diff、Component dif、Element diff。

Tree diff
什么是Tree diff？

首先，进行同级比较，并非循环比较。这样比较次数就降为一层一次，时间复杂度直接降为O(n)。如果同级相同位置节点不一样，则直接删除替换。而对于节点移动，同样道理，也是简单粗暴的删除重建。如下图所示（图中第四步应该是删除左侧的整棵A树）：

Component diff
不多说，先上图：

其实component diff相当于是子树的diff，基本方案和tree diff是一致的，如果如上图D变为G，那么直接删除D这一整棵树，然后重新渲染G树。

Element diff
对于同一节点的元素，diff算法提供了三种操作：插入、移动、删除。

此时的操作，是B、D不做任何操作，AC移动到相应位置（前提是都有相同的key）。如果，此时的key不相同，全都发生了变化，那么节点都是要重新构建，将会消耗大量的性能。

React 16的Diff算法

React 16相比于 React 15的Diff算法发生了很大的变化，其中最主要就是引入Fiber循环任务调度算法。

Fiber

Fiber是什么？干了什么？
Fiber在diff阶段，做了如下操作：

1. 可以随时将diff操作进行任务拆分。
2. diff阶段的每个任务可以随时执行或者终止。
3. diff阶段任务调度优先级控制

所以，Fiber相当于是在15的diff算法阶段，做了优先级的任务调度控制。Fiber是根据一个fiber节点（VDOM节点）来拆分，以fiber node为一个任务单元，一个组件实例都是一个任务单元。
他又是如何能够进行这样的异步操作的呢？这就不得不说一个方法：requestIdleCallback
浏览器提供的requestIdleCallback API中的Cooperative Scheduling 可以让浏览器在空闲时间执行回调，在回调参数中可以获取到当前帧剩余时间。利用这个信息可以合理的安排当前帧需要做的事情，如果时间足够，那继续做下一个任务，如果时间不够就歇一歇，调用requestIdleCallback来获知主线程不忙的时候，再继续做任务。