diff 算法概述

  • diff 即对比,是一个广泛的概念,如 linux diff 命令,git diff 等
  • 两个 js 对象也可以做 diff,如:https://github.com/cujojs/jiff
  • 两颗树做 diff,如这里的 vdom diff

微信截图_20201113155825-1024x498.png

树 diff 的时间复杂度 O(n^3)

  • 第一,遍历 tree1;第二,遍历 tree2
  • 第三,排序
  • 1000 个节点,需要计算 1 亿次,算法不可用

优化时间复杂度到 O(n),采用的措施

  • 只比较同一层级,不跨级比较
  • tag 不相同,则直接删除重建,不再深度比较
  • tag 和 key,两者都相同,则认为相同节点,不再深度比较

微信截图_20201113161047.png
微信截图_20201113161131.png

标签: none

添加新评论