传统diff,计算两颗树形结构差异并进行转换,传统diff算法是这样做的:循环递归每一个节点。比如左侧树a节点依次进行如下对比,左侧树节点b、c、d、e亦是与右侧树每个节点对比
react优化的diff策略
传统diff算法复杂度达到O(n^3)这意味着1000个节点就要进行数10亿次的比较,这是非常消耗性能的。react大胆的将diff的复杂度从O(n^3)降到了O(n),他是如何做到的呢
由于webUI中跨级移动操作非常少、可以忽略不计,所以react实现的diff是同层级比较
算法复杂度能达到O(n^2),n代表节点的个数
a->e、a->d、a->b、a->c、a->a
查找完差异后还需计算最小转换方式,这其中的原理我没仔细去看,最终达到的算法复杂度是O(n^3)
拥有相同类型的两个组件产生的DOM结构也是相似的,不同类型的两个组件产生的DOM结构则不近相同
对于同一层级的一组子节点,通过分配唯一唯一id进行区分(key值)
diff虚拟节点
dom中没有直接提供api让我们获取一棵树结构,这里我们自己构建一个虚拟的dom结构,遍历这样的数据结构是一件很轻松直观的事情。
对于下面的dom,可以用js构造出一个简单的虚拟dom
<divclassName="myDiv">
<p>1</p>
<div>2</div>
<span>3</span>
</div>
{
type:'div',
props:{
className:'myDiv',
},
chidren:[
{type:'p',props:{value:'1'}},
{type:'div',props:{value:'2'}},
{type:'span',props:{value:'3'}}
]
}
先序深度优先遍历
首先要遍历新旧两棵树,采用深度优先策略,为树的每个节点标示唯一一个id
在遍历过程中,对比新旧节点,将差异记录下来,记录差异的方式后面会提到
//若新旧树节点只是位置不同,移动
总之,diff节点两两进行对比时,我们知道新节点较旧节点有什么不同。如果同一层的多个子节点进行对比,他们只是顺序不同,按照上面的算法,会先删除旧节点,再新增一个相同的节点,这可不是我们想看到的结果。