前言
常常咱们在各类文章中都看到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采纳了三个策略，限度了很多状况，不会做过于简单的计算。所有的比拟都在同级进行，只须要一次循环就能实现所有的操作。
参考文章
发表回复