VueDiff算法的简单分析和一些个人思考

Diff算法是Vue视图动态改变的核心算法之一

本文包括对Diff算法的简单概括,和我闲的难受对Diff算法的一些思考

什么是Diff算法

简单的来说Diff算法就是寻找两个Vnode树之间差异的算法

Diff算法发生在Watcher接收到数据改变,之后进行页面渲染的vm._update过程中,

vm._update => vm.patch 而vm.patch是定义在createPatchFunction中的patch

createPatchFunction => patch => patchVnode => updateChildren

updateChildren中包含Diff的核心算法,具体如下:

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

      if (isUndef(oldStartVnode)) { // 没有旧的开始

        oldStartVnode = oldCh[++oldStartIdx]; // 旧的起点右移

      } else if (isUndef(oldEndVnode)) { // 没有旧的结束 旧的终点左移

        oldEndVnode = oldCh[--oldEndIdx];

      } else if (sameVnode(oldStartVnode, newStartVnode)) { // 旧的起点,新的节点,如果相等,指针往后

        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);

        oldStartVnode = oldCh[++oldStartIdx];

        newStartVnode = newCh[++newStartIdx];

      } else if (sameVnode(oldEndVnode, newEndVnode)) { // 旧的结束,新的结束,如果相等指针往前

        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);

        oldEndVnode = oldCh[--oldEndIdx];

        newEndVnode = newCh[--newEndIdx];

      } else if (sameVnode(oldStartVnode, newEndVnode)) { // 旧的开始,新的结束,如果相等各自向中间

        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);

        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));

        oldStartVnode = oldCh[++oldStartIdx];

        newEndVnode = newCh[--newEndIdx];

      } else if (sameVnode(oldEndVnode, newStartVnode)) { // 旧的结束,新的开始,如果相等各自向中间

        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);

        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);

        oldEndVnode = oldCh[--oldEndIdx];

        newStartVnode = newCh[++newStartIdx];

      } else { // 如果都不行,新的起点去旧的里面找key,找不到新建节点,找到了会insertBefore,然后新的起点++

        if (isUndef(oldKeyToIdx)) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); }

        idxInOld = isDef(newStartVnode.key)

          ? oldKeyToIdx[newStartVnode.key]

          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);

        if (isUndef(idxInOld)) { // 如果旧节点中没有

          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);

        } else {

          vnodeToMove = oldCh[idxInOld];

          if (sameVnode(vnodeToMove, newStartVnode)) { // 如果旧的节点中有相同的节点

            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);

            oldCh[idxInOld] = undefined;  // 对应的旧节点会变成undefined,为了防止最后removeVnodes删除掉有用的节点,因为删除的方法是通过去父级直接删掉所有对应的(相同的)子节点

            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);

          } else { // 如果有相同key但是不相同的节点,创建新的节点

            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);

          }

        }

        newStartVnode = newCh[++newStartIdx];

      }

    }

    if (oldStartIdx > oldEndIdx) { // 执行了上方的循环,新旧Vnode有以一方遍历结束,如果此时旧的起点遍历到旧的结束后面去了

      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;

      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);

    } else if (newStartIdx > newEndIdx) { // 如果此时新的起点遍历到新的结束后面去了,也就是新节点遍历完了,但是旧节点还有剩余,也就是旧旧节点

      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);

    }

大致的流程为

我们可以理解为有旧的Vnode数组和新的Vnode数组这两个数组

然后有四个变量充当指针分别指到两个数组的头尾

重复下面的对比过程,直到两个数组中任一数组的头指针超过尾指针,循环结束

  1. 对比两个数组的头部,如果找到,把新节点patch到旧节点,头指针后移
  2. 对比两个数组的尾部,如果找到,把新节点patch到旧节点,尾指针前移
  3. 然后互相交叉对比,旧尾新头,如果找到,把新节点patch到旧节点,旧尾指针前移,新头指针后移
  4. 继续互相交叉对比,旧头新尾,如果找到,把新节点patch到旧节点,新尾指针前移,旧头指针后移
  5. 都没有,开始用新指针对应节点的key去旧数组中直接找 i.如果没有key,创建新的节点 ii.如果有key并且是相同的节点,把新节点patch到旧节点 iii.如果有key但是不是相同的节点,创建新节点

循环结束后,

1.先对比旧数组的头尾指针,如果旧数组遍历完了(可能新数组没遍历完,有漏添加的问题),添加新数组中漏掉的节点

2.再对比新数组的头尾指针,如果新数组遍历完了(可能旧数组没遍历完,有漏删除的问题),删除旧数组中漏掉的节点

图示如下:

初始状态


头部比较:1 == 1,头部指针后移

第一次循环结束


头部比较:2 != 4; 尾部比较:5 == 5,尾部指针前移

第二次循环结束

头部比较:2 != 4; 尾部比较:4 != 100 交叉比较:2 != 100, 4 == 4,旧尾前移,新头后移

第三次循环结束



头部比较:2 != 6; 尾部比较:3 != 100 交叉比较:2 != 100, 3 != 6
插入6
新头后移

第四次循环结束


头部比较:2 != 1000; 尾部比较:3 != 100 交叉比较:2 != 1000, 3 != 100
插入1000
新头后移

第五次循环结束


头部比较:2 != 100; 尾部比较:3 != 100 交叉比较:2 != 100, 3 != 100
插入100
新头后移

第六次循环结束

新数组的头指针超过了尾指针循环结束!
新数组遍历完毕,旧数组有残留,然后删除掉2和3节点,diff完毕!

Diff算法大致就是这样了,最后来说说困扰我的问题

  1. 为什么Diff算法的遍历过程是单向循环的,头头比较,尾尾比较,然后交叉比较,然后key值寻找这样,如果说一个node节点前两个互换,从1,2,3………,10000变成了2,1,3……….,10000,如果按照现在的比较方法就是,while的头尾指针判断,头头不相等,尾尾相等,下次循环,while的头尾指针判断,头头不相等,尾尾相等,头头不相等,尾尾相等。。。无敌了!每次都去对比不相等的头部,怕不是你写的算法和CXK一样好。当然这个例子比较极端,但是如果在尾部比较我们加上一个新的while会变成什么样子,首先这个while也需要判断停止条件,也就是头尾指针的问题,现在我们的逻辑变成了,while头尾指针判断,头头不相等,尾尾相等,内层while头尾指针判断,尾尾相等,内层while头尾指针判断,尾尾相等。。。。没毛病,我省去了头部指针的多余判断逻辑。看似循环套了循环,实则减少了代码判断次数,即使从1,2,3变成了4,2,3,原来的判断历程为:while=>头❌=>尾✔️=>while=>头❌=>尾✔️=>while=>头❌=>尾❌=>插入4删除1完事,尾部判断加个while:外层while=>头❌=>尾✔️=>内层while=> 尾✔️=>内层while=>尾❌=>头❌=>插入4删除1完事。对比一下同样多的while少了一次sameVnode的判断。但是我的代价是什么!代码变丑了,不直观了,换来很小的提升?(可能我想的也不见得对)
  2. 为什么我即使只改了一个data内的变量,他patchVnode的过程也要遍历所有当前Vue组件的Vnode,虽然这些Vnode都是全等的,效率很高,而且都是异步的,但是就是不太能理解。如果这么改,在建立依赖的时候把dep的id映射到Vnode里去,在dep的notify()我知道你对应的dep的id,然后我根据dep的id去判断我需要去修改、增加、删除哪些Vnode,但是我的代价是什么?首先是代码又变得不够简单粗暴了,其次Vnode是树形结构,我如何根据dep的id定位任意位置的节点: i. 要么深度优先遍历,那和原来有多大区别?原来我什么都不用管,无脑遍历就行了,现在我还需要增加额外的判断逻辑,找到了再进行内部diff,或者从根节点替换,添加,删除, ii. 要么记录树的路径,根据路径直接找到节点,再进行替换,添加,删除

结束语:

没准我的脑洞本来就是大错特错的,但是我思考了是不是就是在进步呢?哈哈哈,如有问题欢迎大佬们指正

发表评论