10.双端Diff算法

1.双端比较的原理

从上帝视角看,只需要给p-3移动到p-1之前就可以了,不需要再移动p-1和p-2了。
但对于简单Diff算法,是做不到的。这就需要优化一下算法,实现双端Diff

//新节点            //原节点
// p-3  key:2       // p-1 key:0
// p-1  key:0       // p-2 key:1
// p-2  key:1       // p-3 key:2

新旧节点组首尾节点索引值

/***   *                      新子节点                   旧子节点newStartIdx  -→    p-4                        p-1          ←- oldStartIdx   p-2                        p-2p-1                        p-3newEndIdx    -→    p-3                        p-4          ←- oldEndIdx   */

根据四个点进行双端比较,过程如下

• 第一步:比较旧节点组中第一个子节点p-1和新节点组中的第一个子节点p-4,因为两者的key不同,因此节点不同,不可复用,什么也不做。
• 第二步:比较旧节点组中最后一个子节点p-4和新节点组中的最后一个子节点p-3,因为两者的key不同,因此节点不同,不可复用,什么也不做。
• 第三步:比较旧节点组中第一个子节点p-1和新节点组中的最后一个子节点p-3,因为两者的key不同,因此节点不同,不可复用,什么也不做。
• 第四步:比较旧节点组中最后一个子节点p-4和新节点组中的第一个子节点p-4,因为两者的key相同,所以确定为是可复用DOM。

function patchKeyedChildren(n1,n2,container){const oldChildren = n1.childrenconst newChildren = n2.children//四个索引值let oldStartIdx = 0let oldEndIdx = oldChildren.length - 1let newStartIdx = 0let newEndIdx = newChildren.length - 1//四个索引指向的vnode节点let oldStartVnode = oldChildren[oldStartIdx]let oldEndVnode = oldChildren[oldEndIdx]let newStartVnode = newChildren[newStartIdx]let newEndVnode = newChildren[newEndIdx]if(oldStartVnode.key === newStartVnode.key){//第一步}else if(oldEndVnode.key === newEndVnode.key){//第二步}else if(oldStartVnode.key === newEndVnode.key){//第三步}else if(oldEndVnode.key === newStartVnode.key){//第四步,可复用//调用patch函数patch(oldEndVnode,newStartVnode,container)//移动DOMinsert(oldEndVnode.el,container,oldStartVnode.el)//移动完DOM后,更新索引值,指向下一个位置oldEndVnode = oldChildren[--oldEndIdx]newStartVnode = newChildren[++newStartIdx]}
}

顺着这些节点,一步一步的往下走,可以推导出各个判断条件需要做的事

//可复用节点移动完成后,需要完成一个关键步骤,更新索引值。由于第四步中涉及的两个索引分别是oldEndIdx和newStartIdx,所以需要更新两者的值,让各自朝正确的方向前进一步,指向下一个节点。//第一次执行完毕之后,p-4作为第一个被复用并且移动值,所以根据p-4的key,推导出新的索引值如下/***                  新子节点               旧子节点(p-4)                   p-1        ←- oldStartIdxnewStartIdx  -→   p-2                    p-2p-1                    p-3        ←- oldEndIdxnewEndIdx    -→   p-3                   (p-4)*///使用while循环,更新key,寻找可复用元素,循环的执行条件为头部索引值要小于尾部索引值function patchKeyedChildren(n1,n2,container){const oldChildren = n1.childrenconst newChildren = n2.children//四个索引值let oldStartIdx = 0let oldEndIdx = oldChildren.length - 1let newStartIdx = 0let newEndIdx = newChildren.length - 1//四个索引指向的vnode节点let oldStartVnode = oldChildren[oldStartIdx]let oldEndVnode = oldChildren[oldEndIdx]let newStartVnode = newChildren[newStartIdx]let newEndVnode = newChildren[newEndIdx]while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){if(oldStartVnode.key === newStartVnode.key){//第一步,旧头===新头。更新相关索引,不需要移动patch(oldStartVnode,newStartVnode,container)oldStartVnode = oldChildren[++oldStartIdx]newStartVnode = newChildren[++newStartIdx]}else if(oldEndVnode.key === newEndVnode.key){//第二步,旧尾===新尾。更新相关索引,不需要移动patch(oldEndVnode,newEndVnode,container)oldEndVnode = oldChildren[--oldEndIdx]newEndVnode = newChildren[--newEndIdx]}else if(oldStartVnode.key === newEndVnode.key){//第三步,旧头===新尾。更新相关索引,需要移动DOMpatch(oldStartVnode,newEndVnode,container)insert(oldStartVnode.el,container,oldEndVnode.el.nextSibling)oldStartVnode = oldChildren[++oldStartIdx]newEndVnode = newChildren[--newEndIdx]}else if(oldEndVnode.key === newStartVnode.key){//第四步,旧尾===新头。更新相关索引,需要移动DOMpatch(oldEndVnode,newStartVnode,container)insert(oldEndVnode.el,container,oldStartVnode.el)oldEndVnode = oldChildren[--oldEndIdx]newStartVnode = newChildren[++newStartIdx]}}
}

示例图

四个索引值,分别代表新旧两组子节点的首尾

四个位置的节点进行相互对比

①新头&旧头 ②新尾&旧尾 ③新尾&旧头 ④新头&旧尾

当前DOM顺序,还没有进行比对和移动,现在的真实DOM顺序和旧节点的顺序是一样的

新头和旧尾相同,节点为p-4,触发了第四步。新头的索引+1,也就是向下移动,旧头的索引减一,向上移动。

刚才匹配到的节点p-4就排在真实DOM的首位

继续循环,新尾和旧尾节点相同,匹配的节点是p-3,触发了第二步。因为在新节点中,这个肯定是最后一个,所以这个环节不需要移动

继续循环,旧头等于新尾,p-1节点,需要移动位置。原本p-1是旧组的起始节点,在新顺序中,应该在p-2后面,所以需要将节点移动到p-2后面,并且更新索引。

上一步操作完毕后,形成如下结果,新头新尾旧头旧尾指向同一个值。

旧头和新头相同,节点可复用,但是不需要移动。

这一轮更新完毕后,形成如下结果:

真实DOM顺序和新节点顺序一致。

新头和旧头的值都小于新尾和旧尾。

循环结束

规则总结:

1. 两头相等: 更新索引都加加
2. 两尾相等: 更新索引都减减
3. 旧头等新尾: 更新索引旧头加,新尾减,移动位置(旧头,容器,旧尾后)
4. 新头等旧尾: 更新索引旧尾减,新头加,移动位置(旧尾,容器,旧头)

2.双端比较的优势

简单diff算法的过程:

当使用简单diff算法的时候,一共发生了两次DOM移动操作

p-1和p-2进行了移动

双端diff算法的过程:

新头===旧尾,p-3,需要移动位置

旧头===新头,不需要移动

四值重叠了,也是不需要移动

最终结果

所以,双端diff算法只移动了一次,在性能上更优

3.非理想状况的处理方式

之前上一轮,每轮都能命中一种情况,但是如果遇到了节点对比,都不符合以上四种逻辑。

如果四种情况都无法命中时,就需要添加对应的逻辑处理了。既然两头和两尾都没有可以复用的节点,那么就去看非头部,非尾部的节点是否能够复用。

方法:拿新的节点组中的头部去旧的节点组中去寻找。

 //新增逻辑判断,在旧节点组中,找到和新节点组中头部节点key值相同的节点:idxInOldwhile (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (oldStartVNode.key === newStartVNode.key) {// 省略部分代码} else if (oldEndVNode.key === newEndVNode.key) {// 省略部分代码} else if (oldStartVNode.key === newEndVNode.key) {// 省略部分代码} else if (oldEndVNode.key === newStartVNode.key) {// 省略部分代码} else {// 遍历旧的一组子节点，试图寻找与 newStartVNode 拥有相同 key 值的节点// idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)}}

在下图中,可以看到p-2就是我们找到的那个节点,p-2的key值是1。这意味着p-2本来是第二个节点,但是现在新节点组的头部节点匹配到了它,更新后它就是需要成为头部节点。

所以需要把p-2所对应的真实DOM节点移动到旧节点组中头部节点p-1对应的真实DOM之前

具体实现:

     // 遍历旧的一组子节点，试图寻找与 newStartVNode 拥有相同 key 值的节点// idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)//大于0,说明找到了可复用节点,并且需要将对应的真实DOM移动到头部if(idxInOld>0){//idxInOld位置对应的vnode就是需要移动的节点const vnodeToMove = oldChildren[idxInOld]//打补丁patch(vnodeToMove,newStartVNode,container)//将vnodeToMove.el移动到头部节点oldStartVnode.el之前,因此需要使用后者作为锚点insert(vnodeToMove.el,container,oldStartVnode.el)//由于位置idxInOld处节点对应的真实DOM已经移动到了别处,因此将其设置为undefinedoldChildren[idxInOld] = undefined//最后更新newStartIdx到下一个位置newStartVNode = newChildren[++newStartIdx]}

找到p-2,移动p-2,并且将原位置的节点变成undefined,更新newStartIdx的值

继续使用双端diff比较

如果循环旧节点组的首尾时,遇到了我们设置的undefined时,说明这个节点已经被处理过,可以直接跳过这个节点的所有匹配过程,直接跳到下一个位置

//新增逻辑判断,在旧节点组中,找到和新节点组中头部节点key值相同的节点:idxInOld
function patchKeyedChildren(n1, n2, container) {const oldChildren = n1.childrenconst newChildren = n2.children//四个索引值let oldStartIdx = 0let oldEndIdx = oldChildren.length - 1let newStartIdx = 0let newEndIdx = newChildren.length - 1//四个索引指向的vnode节点let oldStartVnode = oldChildren[oldStartIdx]let oldEndVnode = oldChildren[oldEndIdx]let newStartVnode = newChildren[newStartIdx]let newEndVnode = newChildren[newEndIdx]while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (!oldStartVnode) {//旧头遇到undefinedoldStartVnode = oldChildren[++oldStartIdx]} else if (!oldEndVNode) {//旧尾遇到undefinedoldEndVnode = oldChildren[--oldEndIdx]}else if (oldStartVnode.key === newStartVNode.key) {// 省略部分代码} else if (oldEndVNode.key === newEndVNode.key) {// 省略部分代码} else if (oldStartVnode.key === newEndVNode.key) {// 省略部分代码} else if (oldEndVNode.key === newStartVNode.key) {// 省略部分代码} else {// 遍历旧的一组子节点，试图寻找与 newStartVNode 拥有相同 key 值的节点// idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)//大于0,说明找到了可复用节点,并且需要将对应的真实DOM移动到头部if (idxInOld > 0) {//idxInOld位置对应的vnode就是需要移动的节点const vnodeToMove = oldChildren[idxInOld]//打补丁patch(vnodeToMove, newStartVNode, container)//将vnodeToMove.el移动到头部节点oldStartVnode.el之前,因此需要使用后者作为锚点insert(vnodeToMove.el, container, oldStartVnode.el)//由于位置idxInOld处节点对应的真实DOM已经移动到了别处,因此将其设置为undefinedoldChildren[idxInOld] = undefined//最后更新newStartIdx到下一个位置newStartVNode = newChildren[++newStartIdx]}}}
}

4.添加新元素

当新节点组中比旧节点组元素多的时候,必然是有需要新增的元素,如下

const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key
)//大于0,说明找到了可复用节点
if (idxInOld > 0) {const vnodeToMove = oldChildren[idxInOld]patch(vnodeToMove, newStartVNode, container)insert(vnodeToMove.el, container, oldStartVnode.el)oldChildren[idxInOld] = undefinednewStartVNode = newChildren[++newStartIdx]
}else{//没有可复用的节点,将newStartVNode作为新节点挂载到头部,使用当前头部节点oldStartVNode.el作为锚点patch(null,newStartVNode,container,oldStartVnode.el)
}
newStartVNode = newChildren[++newStartIdx]

循环遗漏问题处理

如图所示

第一步匹配到了p-3,p-3出列

第二步匹配到了p-2,p-2出列

第三步匹配到了p-1,p-1出列

现在只剩p-4了。但是因为触发了while的终止循环条件: oldStartIdx > oldEndIx,终止了循环,p-4就被遗忘了

修改如下

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// 省略部分代码if(!oldStartVnode){//省略}/** 各种else if */else{const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key)//大于0,说明找到了可复用节点if (idxInOld > 0) {const vnodeToMove = oldChildren[idxInOld]patch(vnodeToMove, newStartVNode, container)insert(vnodeToMove.el, container, oldStartVnode.el)oldChildren[idxInOld] = undefinednewStartVNode = newChildren[++newStartIdx]} else {//没有可复用的节点,将newStartVNode作为新节点挂载到头部,使用当前头部节点oldStartVNode.el作为锚点patch(null, newStartVNode, container, oldStartVnode.el)}newStartVNode = newChildren[++newStartIdx]}}// 循环结束后检查索引值的情况,
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {// 如果满足条件，则说明有新的节点遗留，需要挂载它们for (let i = newStartIdx; i <= newEndIdx; i++) {patch(null, newChildren[i], container, oldStartVNode.el)}
}

5.移除不存在的元素

新节点少于旧节点,那必然是有些旧元素不存在了,需要被移除

处理方法:循环结束后,多余出来的节点,必然就是不存在的节点,直接进行循环移除

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// 省略部分代码}if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {// 添加新节点// 省略部分代码} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {// 移除操作for (let i = oldStartIdx; i <= oldEndIdx; i++) {unmount(oldChildren[i])}}

总结