likes
comments
collection
share

diff算法核心原理精讲之双端比较

作者站长头像
站长
· 阅读数 88

大家好，我是苏先生，一名热爱钻研、乐于分享的前端工程师，跟大家分享一句我很喜欢的话：人活着，其实就是一种心态，你若觉得快乐，幸福便无处不在

github与好文

前言

diff算法核心原理精讲之双端比较

问题分析

假设我们现在有如下两组dom节点

// 新
<p></p>
<span></span>
<div></div>
// 旧
<span></span>
<div></div>
<p></p>

  • 取新节点p，到旧节点中找到对应节点p，并记录其位置为2

  • 取新节点span，到旧节点中找到对应节点span的位置为0，由于0<2，则进行移动

  • 取新节点div，到旧节点中找到对应节点div的位置为1，由于1<2，则进行移动

由此可知，一共需要进行两次dom节点的移动操作，但是我们观察示例的新旧两组节点，应该不难看出：span和div的相对位置是一样的，只需要将p节点从原来的2号位置移动到新的0号位置就可以了。换句话说，我们浪费了一次dom移动操作

原因分析

function patchChildren(n1,n2,continer){
    ...
    for(let i=0;i<newChildren.length;i++){
        for(j;j<oldChildren.length;j++){
            ...
        }
    }
}

我们使用内外两层for循环来挨个处理节点，由于是同步的，外层循环必须等到内层循环结束后才能进入下一轮，这意味着一次只能处理一个。所以，如果我们能将两个for循环拆开，使它们平级运行，那就意味着有机会同时拿到两个列表的不同节点来进行操作，带入到前文示例中去，如果我们一个从新节点索引位置为0处开始遍历，一个从旧节点索引位置为2处开始遍历，岂不是一次就找到需要移动的节点了嘛

diff算法核心原理精讲之双端比较

实现版本一

端点确认

在前文中，我们通过原因分析找到了双端比较的核心是平行运行，且针对前文的特定示例我们发现只需要一个从前向后，一个从后向前，就能在第一次就发现需要移动的点。那么我们合理对其进行推断就能知道，一定也存在某个对立的情况需要将两次遍历的起始位置进行对调

故，我们的起始位置针对每一个节点列表都有两个

    let oldStartIndex = 0
    let oldEndIndex = oldChildren.length - 1
    let newStartIndex = 0
    let newEndIndex = newChildren.length - 1

也即，我们可以通过索引拿到对应的四个节点

    let oldStartNode = oldChildren[oldStartIndex]
    let oldEndNode = oldChildren[oldEndIndex]
    let newStartNode = newChildren[newStartIndex]
    let newEndNode = newChildren[newEndIndex]

遍历分支

现在我们一共有两个for循环、四个端点，按照穷举法，有如下四种运行方式：

1-新列表对应的for循环从newStartIndex开始遍历，旧列表对应的for循环从oldStartIndex开始遍历

2-新列表对应的for循环从newStartIndex开始遍历，旧列表对应的for循环从oldEndIndex开始遍历

3-新列表对应的for循环从newEndIndex开始遍历，旧列表对应的for循环从oldStartIndex开始遍历

4-新列表对应的for循环从newEndIndex开始遍历，旧列表对应的for循环从oldEndIndex开始遍历

判断临界

现在我们来判定临界，以如下新旧两组dom节点为例：

// 新
<p></p>
<span></span>
<div></div>
<menu></menu>
// 旧
<div></div>
<span></span>
<menu></menu>
<p></p>

第1轮：newStartIndex=0；oldStartIndex=0

div !== p，无法复用，且无相对位置关系无法判断和处理节点移动，跳过会导致最终结果错误，故程序应当停止

第2轮：newStartIndex=0；oldEndIndex=3

p === p，可以复用，复用的节点无需执行额外操作，故进入下一次循环，即newStartIndex=1，oldEndIndex=2，此时span !== menu，无法复用，同上，程序应当停止

第3轮：newEndIndex=3；oldStartIndex=0

menu !== div，无法复用，同上，程序应当停止

第4轮：newEndIndex=3；oldEndIndex=3 menu !== p，无法复用，同上，程序应当停止

综上，临界点为两节点不可复用时

过程模拟

现在我们来思考，如何执行这四个分支？

diff算法核心原理精讲之双端比较

我们的核心诉求是让新旧列表中的每一个节点都能参与比较，现在我们结合临界点中的结论看如下示例：

顺序对比

新旧的dom节点如下

// 新
<span></span>
<div></div>
<menu></menu>
// 旧
<span></span>
<p></p>
<menu></menu>

1-分支1

当第二次时，即索引位置为1时，div !== p，程序停止，此时还有div和p未处理。此时由于节点span已经被明确可复用，而分支2和分支3会导致节点重新参与比较，因此需要舍弃

2-分支4

此时，我们使用分支4，开始从后向前遍历比对，同样在索引位置为1时，得到div !== p，程序停止。此时我们已经处理完所有可复用的节点，并且两次程序停止时的节点位置相同，此时有充分证据能够表明div标签需要去替换掉p标签

交叉对比

在顺序对比对比中，我们的示例刚刚好能处理完所有的节点，现在我们来考虑另外一个例子:

// 新
<span></span>
<div></div>
<h1></h1>
<menu></menu>
// 旧
<span></span>
<h1></h1>
<div></div>
<menu></menu>

在此示例中，使用顺序对比仍然可以很轻松的处理完头尾两个节点，但是对于中间的两个节点将会无法处理，此时如果我们用交叉方式比对，即分支2对应的情况，那么就可以准确找到可复用的节点

对于分支3是一样的，故此处不再赘述

调用顺序

根据前文对分支1到分支4的分析，我们知道了，先顺序调用（ps：分支1和分支4），再交叉调用（ps：分支2和分支3）可以很好的处理完所有的节点。那么反过来，是否可以先交叉后顺序呢？貌似也是可以的，比如下边这种情况，先进行交叉处理完双端节点，再进行顺序对比处理余下的节点

// 新
<div></div>
<span></span>
<menu></menu>
<h1></h1>
// 旧
<h1></h1>
<span></span>
<menu></menu>
<div></div>

结论

综上所述，我们需要在遍历的过程中分别就四种情况进行比对

代码示例

结合目前的分析，我们知道需要对每一个节点至少执行四次比对，才能覆盖完分支1到分支4。因此我们的遍历代码大致长下边这样：

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
    if(oldStartNode === newStartNode){
        ...
    }else if(oldStartNode === newEndNode){
        ...
    }else if(oldEndNode === newEndNode){
        ...
    }else if(oldEndNode === newStartNode){
        ...
    }
}

结合前文分析，当找到可复用节点时，我们需要将指针移动到下一个节点继续进行比对，并且，根据当前适用分支的不同，指针的移动方向也不同。如下以分支1为例

oldStartNode = oldChildren[++oldStartIndex]
newStartNode = newChildren[++newStartIndex]

实现版本二

在版本一中，我们的思路是乌托邦式的，因为我们隐式的假定了每一次都能够命中一个分支，然而这在现实中是不可能的

diff算法核心原理精讲之双端比较

// 新
<div></div>
<span></span>
<menu></menu>
<h1></h1>
// 旧
<span></span>
<h1></h1>
<div></div>
<menu></menu>

在上述的示例节点中，无法命中四个节点中的任何一个分支，但肉眼可见的是它们确确实实是可复用的，只不过位置发生了移动

相信聪明的你已经有答案了！但是先别急着公布，我先来说说我的看法，看是不是与君不谋而合

diff算法核心原理精讲之双端比较

但是作为本文，是为了正确处理完虚拟节点。按照我们目前的实现逻辑，当找不到可复用节点时while循环应该被break掉，但这种粗暴的做法直接导致除端点节点外的其他n个节点都无法被处理。因此我们要新增else分支来将指针移动到下一个位置继续对剩余节点进行处理

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
    if(oldStartNode === newStartNode){
        ...
    }else if(oldStartNode === newEndNode){
        ...
    }else if(oldEndNode === newEndNode){
        ...
    }else if(oldEndNode === newStartNode){
        ...
    }else{
        // 两端点找不到可复用节点
    }
}

但我们没有一种类似回溯的机制，如果跳过了当前的节点，就永远不可能回过头进行二次处理了。所以，在移动到下一个指针之前，我们还需要对当前节点存在的可能性进行处理，比如是否发生了移动

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
    if(oldStartNode === newStartNode){
        ...
    }else if(oldStartNode === newEndNode){
        ...
    }else if(oldEndNode === newEndNode){
        ...
    }else if(oldEndNode === newStartNode){
        ...
    }else{
        // 两端点找不到可复用节点
        const indexOfOld = oldChildren.findIndex((v)=>v.key === newStartNode.key)
        if(indexOfOld > -1){
            const needMoved =  oldChildren[indexOfOld]
            // 将当前节点作为根节点继续patch
            ...
            helper.insert(needMoved,continer,oldStartNode)
            oldChildren[indexOfOld] = undefined
            newStartNode = newChildren[++newStartIndex]
        }
    }
}

如上，如果indexOfOld>-1，则说明存在可复用的节点，此时我们通过oldChildren[indexOfOld]获取到需要移动的节点，并调用前文实现的helper.insert函数将needMoved插入到oldStartNode前边（ps：如果是头节点，就不会进入到该else分支）,接着将空出来的位置标记为undefined（ps：思考一下，为什么说是空出来？）。最后，由于本次只处理了一个节点为新节点，所以我们只能移动newChildren的指针newStartIndex

此时，我们页面中的dom结构和虚拟节点如下，并且newStartIndex=1，newStartNode为span

// 新
<div></div>
<span></span>
<h1></h1>
<menu></menu>
// 虚拟节点
<span></span>
<h1></h1>
undefined
<menu></menu>

此时，仍然是先顺序对比再交叉对比，显然，在顺序对比时，span === span，此时同时移动新旧节点的指针，此时newStartIndex=2，newStartNode为h1；oldStartIndex=1，oldStartNode为h1

newStartNode = newChildren[++newStartIndex]
oldStartNode = oldChildren[++oldStartIndex]

同理可复用，此时newStartIndex=3，newStartNode为menu；oldStartIndex=2，oldStartNode为undefined，由于undefined表示已经被处理过，所以我们直接跳过即可，即在while中新增if分支进行处理，同理oldEndNode为undefined时我们也进行跳过

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
    if(oldStartNode === undefined){
        oldStartNode = oldChildren[++oldStartIndex]
        continue
    }
    if(oldEndNode === undefined){
        oldEndNode = oldChildren[--oldEndNode]
        continue
    }
    ...
}

我们继续执行程序，此时newStartIndex=3，newStartNode为menu；oldStartIndex=3，oldStartNode为menu，可复用，并且此时所有的节点都被处理完毕

实现版本三

处理新增

版本二中我们优化了版本一假设每次while循环都能命中一个分支的问题，但同时我们又隐式的假设每次总是能从旧节点中找到可复用的节点，现实是，并不总是能找到，比如新增了元素时

diff算法核心原理精讲之双端比较

如下，我们新增else分支来处理新增，在这里我们只是调用了一下patch函数，该函数本质上是一次递归diff，我们这里省略...；最后，我们对剩余节点依次进行挂载（ps：原因见下）

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
    ...
    // 两端点找不到可复用节点
    const indexOfOld = oldChildren.findIndex((v)=>v.key === newStartNode.key)
    if(indexOfOld > -1){
        ... 
    }else{
        patch(null,newStartNode)
    }
}

if(oldEndIndex < oldStartIndex && newStartIndex <= newEndIndex){
        for(let i=newStartIndex;i<newEndIndex;i++){
            patch(null,newChildren[i])
}

处理删除

最后，我们来处理删除节点，由于删除节点会导致新节点更早被遍历完，即newEndIndex < newStartIndex会break出while，此时可能还存在多余的节点未被卸载

if(newEndIndex < newStartIndex && oldStartIndex <= oldEndIndex){
   for(let i=newStartIndex;i<newEndIndex;i++){
      unmount(oldChildren[i])
   }
}

如果本文对您有用，希望能得到您的点赞和收藏

订阅专栏，每周更新2-3篇类型体操，每月1-3篇vue3源码解析，等你哟😎

转载自:https://juejin.cn/post/7248452420765696058
评论
请登录