江苏龙网

  1. 主页 > 生活百科 > >

diff算法介绍

diff算法

diff算法的作用
计算出Virtual DOM中真正变化的部分 ， 并只针对该部分进行原生DOM操作 ， 而非重新渲染整个页面 。
传统diff算法
通过循环递归对节点进行依次对比 ， 算法复杂度达到 O(n^3)  ， n是树的节点数 ， 这个有多可怕呢？——如果要展示1000个节点 ， 得执行上亿次比较 。。即便是CPU快能执行30亿条命令 ， 也 很难在一秒内 计算出差异 。
react的diff算法
diff算法是调和的具体实现 。
调和：将Virtual DOM树转换成actual DOM树的最少操作的过程 称为 调和。
diff策略
React用 三大策略 将O(n^3)复杂度 转化为 O(n)复杂度
策略一（ tree diff ）：
Web UI中DOM节点跨层级的移动操作特别少 ， 可以忽略不计 。
策略二（ component diff ）：
拥有相同类的两个组件 生成相似的树形结构 ， 
拥有不同类的两个组件 生成不同的树形结构 。
策略三（ element diff ）：
对于同一层级的一组子节点 ， 通过唯一id区分 。
tree diff算法
（1）React通过updateDepth对Virtual DOM树进行 层级控制  。
（2）对树分层比较 ， 两棵树 只对 同一层次节点 进行比较 。如果该节点不存在时 ， 则该节点及其子节点会被完全删除 ， 不会再进一步比较 。
（3）只需遍历一次 ， 就能完成整棵DOM树的比较 。

diff算法介绍

文章插图
 
对于策略一 ， React 对树进行了分层比较 ， 两棵树只会对同一层次的节点进行比较 。
只会对相同层级的 DOM 节点进行比较 ， 当发现节点已经不存在时 ， 则该节点及其子节点会被完全删除 ， 不会用于进一步的比较 。
如果出现了 DOM 节点跨层级的移动操作 。
如上图这样 ， A节点就会被直接销毁了 。
Diif 的执行情况是：create A -> create C -> create D -> delete A
component diff
React对不同的组件间的比较 ， 有三种策略
（1）同一类型的两个组件 ， 按原策略（层级比较）继续比较Virtual DOM树即可 。
（2）同一类型的两个组件 ， 组件A变化为组件B时 ， 可能Virtual DOM没有任何变化 ， 如果知道这点（变换的过程中 ， Virtual DOM没有改变） ， 可节省大量计算时间 ， 所以 用户 可以通过 shouldComponentUpdate() 来判断是否需要 判断计算 。
（3）不同类型的组件 ， 将一个（将被改变的）组件判断为dirty component（脏组件） ， 从而 替换 整个组件的所有节点  。
注意：如果组件D和组件G的结构相似 ， 但是 React判断是 不同类型的组件 ， 则不会比较其结构 ， 而是删除 组件D及其子节点 ， 创建组件G及其子节点 。
element diff
当节点处于同一层级时 ， diff提供三种节点操作： 删除、插入、移动  。
插入：组件 C 不在集合（A,B）中 ， 需要插入
删除：（1）组件 D 在集合（A,B,D）中 ， 但 D的节点已经更改 ， 不能复用和更新 ， 所以需要 删除 旧的 D  ， 再创建新的 。
（2）组件 D 之前在 集合（A,B,D）中 ， 但集合变成新的集合（A,B）了 ， D 就需要被删除 。
移动：组件D已经在集合（A,B,C,D）里了 ， 且集合更新时 ， D没有发生更新 ， 只是位置改变 ， 如新集合（A,D,B,C） ， D在第二个 ， 无须像传统diff ， 让旧集合的第二个B和新集合的第二个D 比较 ， 并且删除第二个位置的B ， 再在第二个位置插入D ， 而是 （对同一层级的同组子节点） 添加唯一key进行区分 ， 移动即可 。
element diff
当节点处于同一层级时 ， diff提供三种节点操作： 删除、插入、移动  。
插入：组件 C 不在集合（A,B）中 ， 需要插入
删除：（1）组件 D 在集合（A,B,D）中 ， 但 D的节点已经更改 ， 不能复用和更新 ， 所以需要 删除 旧的 D  ， 再创建新的 。
（2）组件 D 之前在 集合（A,B,D）中 ， 但集合变成新的集合（A,B）了 ， D 就需要被删除 。


推荐阅读


上一篇：安溪龙涓乡,茶农5万余斤铁观音亟待出售

下一篇：国家茶业技术体系专家行调查安化低氟茶品种