关于前端:react-diff算法

前言

常常咱们在各类文章中都看到 react 将 diff 的复杂度从 O(n^3) 优化为了 O(n)，那么传统的 O(n^3) 到底是如何失去的呢？react 又是如何将其优化为了 O(n) 呢？

传统 diff 算法

传统的 diff 算法计算一棵树变成另一棵所须要的起码步骤的复杂度是 O(n^3)，如何失去？

• 旧数上的一个节点，它要跟新树上的所有节点比照 (复杂度为 O(n))
• 如果这个节点在新树上没有找到，那么这个节点将被删除，同时会从新树中遍历找几个节点去填补 (复杂度减少到 O(n^2))
• 旧树上的所有节点都会走这个过程 (复杂度减少到 O(n^3))

// 伪代码
const oldNodes = ['a', 'b', 'c', 'd', 'e'];
const newNodes = ['a', 'c', 'f', 'd', 'e'];
for (let i = 0; i< oldNodes.length; i++) {// 复杂度 O(n)
    for (let j = 0; j< newNodes.length; j++) {// 复杂度 O(n^2)
        // 旧节点在新节点中比对
        if(未找到){for (let k = 0; k< newNodes.length; k++) {// 复杂度 O(n^3)
                // 寻找填补项
            }
        } 
    }
}

有一篇论文专门讲述 diff 算法：diff 论文

React diff

react diff 制订的三个策略

• Web UI 中的 DOM 节点跨层级的挪动特地少，能够忽略不计（tree diff）；
• 领有雷同类的两个组件将会生成类似的树形构造，领有不同类的两个组件将会生成不同的树形构造（component diff）；
• 对于同一层级的一组子节点，他们能够通过惟一的 key 进行辨别（element diff）；

tree diff

基于策略一，react 对树的算法进行分层比拟优化，两颗树只会对处在同一层级的节点进行比拟。

装置策略一疏忽了跨层级之间的挪动操作，react tree diff 只会对雷同色彩内的 DOM 节点进行比对，当发现某一层级的节点曾经不存在了，则该节点及其所有子节点都会被齐全删除掉，不会进行进一步的比对，这样只须要对树遍历一次便能实现整个 DOM 树的比拟，复杂度变为了 O(n)。

依据下面的规定，在开发组件时，保持稳定的 DOM 构造会有助于性能的晋升。例如，能够通过 visibility 属性管制元素的显示与暗藏，而不是 display。

component diff

• 组件类型没有发生变化，持续比拟 Virtual DOM tree；
• 组件类型发生变化，则将该组件视为 dirty component，并从新创立新的组件，包含所有的子节点，替换该组件；
• 对于同一类型的组件，有可能 Virtual DOM 并不会有任何变动，那么能够通过 shouldComponentUpdate 来判断组件是否须要进行 diff；

如上图中组件 D 变更为组件 G 时，尽管他们的构造很类似，然而因为组件类型不同，react diff 会从新创立一个新的组件 G 来替换整个组件 D，并且 E、F 也会从新创立，不会复用组件 D 的。

element diff

当节点处于同一层级时，react 提供了三种节点操作形式：INSERT_MARKUP（插入）、MOVE_EXISTING（挪动）、REMOVE_NODE（删除）。

• INSERT_MARKUP，新节点在不原汇合中，须要对新节点执行插入操作；
• MOVE_EXISTING，新老汇合中都有某一节点，然而所处地位不同，能够复用老节点，须要对节点进行挪动操作；
• REMOVE_NODE，老汇合中有节点在新汇合中不存在，或者某一属性不统一，则须要执行删除操作；

针对 element diff react 提供了一个优化策略，同一层级的同组子节点，增加惟一 key 进行辨别，这也是节点是否复用的前提。

无 key 示例

老汇合中蕴含节点：A、B、C、D，更新后的新汇合中蕴含节点：B、A、D、C，此时新老汇合进行 diff 差异化比照，发现 B != A，则创立并插入 B 至新汇合，删除老汇合 A；以此类推，创立并插入 A、D 和 C，删除 B、C 和 D。

有 key 示例

上面咱们看看具体的 diff 流程

lastIndex 示意拜访过的节点在老汇合中的最大索引地位，这是一个初始化为 0 的动静值。

• 遍历到 C，B 不做挪动，lastindex = 1
• 遍历到 C，发现旧汇合中不存在，则创立 E 并放在新汇合对应的地位，lastindex = 1
• 遍历到 C，不满足 index < lastindex，C 不动，lastindex = 2
• 遍历到 A，满足 index < lastindex，A 挪动到对应地位，lastindex = 2
• 当实现新汇合中所有节点 diff 时，最初还须要对老汇合进行循环遍历，判断是否存在新汇合中没有但老汇合中仍存在的节点，发现存在这样的节点 D，因而删除节点 D，到此 diff 全副实现

diff 算法的有余

因为 D 节点在老汇合外面的 index 是最大的，使得 A、B、C 三个节点都会 index < lastindex，从而导致 A、B、C 都会去做挪动操作。另外这只是极其状况，事实的场景中蕴含很多相似的状况。能够思考倒着循环。

react diff 算法的复杂度为什么是 O(n)

起因在于 React 采纳了三个策略，限度了很多状况，不会做过于简单的计算。所有的比拟都在同级进行，只须要一次循环就能实现所有的操作。

参考文章