彻底读懂VUE3 VDOM DIFF - 下

前端bubucuo

发布于 2022-09-16 17:46:43

4210

发布于 2022-09-16 17:46:43

文章被收录于专栏：bubucuo

在《彻底读懂VUE3 VDOM DIFF - 上》的4.4中，我们已经实现了节点的mount，即新增节点。当然，这里我强调过，源码中用的是patch函数，patch的新节点为null。文章中我用的是mount函数，主要为了区分新增节点与更新节点方便。

接下来最难的问题来了，move还没有完成。如下：

// old [i ... e1 + 1]: a b [c d e] f g
// new [i ... e2 + 1]: a b [e c d h] f

从cde到ecdh，如何变换呢？

就像魔方一样，有很多种归位的方法，但是考虑到现在我们说的是DOM，是页面，如果我们move节点太多，那么DOM更新负担太重，整不好用户会看到页面闪烁，这显然不是我们要的效果。

因此可不可以计算出最小成本的move节点呢，也就是如果能让1个节点move就达到最终效果，那么我们绝不move两个。并且能近距离move就不要远距离move。

怎么计算呢，从cde到ecdh？

你可以先想想，再继续往下看。

当然，眼神好的，马上就能看出来，h是新增，所以把节点e移动到c前面就行了。但是我们现在要写一个规则出来，毕竟计算机是按照规则做事的。

再来观察规律，如下数组，我写出了下标，cde的下标为234，

                       0 1 [2 3 4] 5 6
// old [i ... e1 + 1]: a b [c d e] f g
// new [i ... e2 + 1]: a b [e c d h] f

这个下标其实之前在4.2有记录过：

而在4.3节中，遍历老元素的时候，大家还记得吗，有这么一行代码：

也就是说，经历过4.2与4.3之后，keyToNewIndexMap存的数据是[5, 3, 4, 0]，其中，因为h节点是4.4中新增的，所以值是0。

                       0 1 [2 3 4] 5 6
// old [i ... e1 + 1]: a b [c d e] f g
// new [i ... e2 + 1]: a b [e c d h] f 
                            5 3 4 0

既然keyToNewIndexMap中，下标是老元素的新的相对位置，值是老元素的下标+1。那么找到keyToNewIndexMap的最长递增子序列，不就是对老元素的最大复用嘛~

判断是否需要移动元素

当然找最长递增子序列的这件事会很麻烦，因此4.3对应的源码有个moved来判断是否需要移动，毕竟能不去找最长递增子序列就不找嘛。什么情况下不需要移动呢，就是如果节点相对位置没有发生变化，那就不需要移动。因此完整的4.3代码是：

// *4.3 先遍历老元素 检查老元素是否要被复用，如果复用就patch，如果不能复用就删除
    let moved = false;
    let maxNewIndexSoFar = 0;
    for (i = s1; i <= e1; i++) {
      const prevChild = c1[i];

      if (patched >= toBePatched) {
        unmount(prevChild.key);
        continue;
      }

      const newIndex = keyToNewIndexMap.get(prevChild.key);

      if (newIndex === undefined) {
        // 节点没法复用
        unmount(prevChild.key);
      } else {
        //移动发生在这里，这里的节点可能要被移动（ecd）
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex;
        } else {
          // 相对位置发生变化
          moved = true;
        }
        newIndexToOldIndexMap[newIndex - s2] = i + 1;
        patch(prevChild.key);
        patched++;
      }
    }

如上19行，maxNewIndexSoFar每次记录index的最大位置，如果newIndex忽然小于上次记录的最大位置了，证明有节点需要移动，moved设置为true。

                       0 1 [2 3 4] 5 6
// old [i ... e1 + 1]: a b [c d e] f g
// new [i ... e2 + 1]: a b [e c d h] f 
                            5 3 4 0

比如上面的例子，遍历到c的时候，newIndex是3，maxNewIndexSoFar从0被赋值为3；遍历到d的时候，newIndex是4，maxNewIndexSoFar从3被赋值为4；遍历到e的时候，newIndex是2，也就是说原先都排队排到4了，忽然来个人说他是第2位，这不就是想插队吗？因此这时候moved设置为true。

最长递增子序列的用处

接下来我们要考虑获取最长递增子序列了，也就是LIS。这个LIS在Vue源码中由getSequence函数返回，具体算法我们稍等说，我们先说结果和LIS的用法。

依然是下面的这个例子，根据getSequence计算，返回的LIS就是不需要移动的元素，也就是cd。鉴于是数组，返回的是相对下标，即[1, 2]。

                       0 1 [2 3 4] 5 6
// old [i ... e1 + 1]: a b [c d e] f g
// new [i ... e2 + 1]: a b [e c d h] f 
                            5 3 4 0

接下来我们需要来看完整的4.4的代码：

    // *4.4 遍历新元素 mount move
    // 返回不需要移动的节点
    const increasingNewIndexSequece = moved
      ? getSequence(newIndexToOldIndexMap)
      : [];
    let lastIndex = increasingNewIndexSequece.length - 1;
    // 相对下标
    // console.log("increasingNewIndexSequece", increasingNewIndexSequece); //sy-log
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextChildIndex = s2 + i;
      const nextChild = c2[nextChildIndex];

      // 判断nextChild是mount还是move
      // 在老元素中出现的元素可能要move，没有出现过的要mount
      if (newIndexToOldIndexMap[i] === 0) {
        mountElement(nextChild.key);
      } else {
        // 可能move
        if (lastIndex < 0 || i !== increasingNewIndexSequece[lastIndex]) {
          move(nextChild.key);
        } else {
          lastIndex--;
        }
      }
    }

increasingNewIndexSequece存的就是LIS，首先根据moved判断是否有节点要移动，需要移动则去用getSequence计算LIS，否则都不需要移动，则LIS为空数组。

在第9行for循环的时候，如果newIndexToOldIndexMap[i]不是0，则证明节点可能需要移动。为什么是可能呢？因为如果节点属于LIS，那么节点就是不需要移动的，否则才需要移动。

那么还用我们上面的例子，得到的LIS，即increasingNewIndexSequece是[1, 2]，lastIndex是increasingNewIndexSequece的最后一个节点的下标，并且这个下标是要不断移动的，也就是说每遍历一个不需要移动的节点，这个下标就往前走一下，也就是lastIndex--;

等lastIndex为-1了，也就是increasingNewIndexSequece中不要移动的节点遍历完了，剩下的节点都是要move的，因此move函数执行的一个条件就是lastIndex<0。

还有一种情况节点不需要移动，就是这个节点ecdh的相对下标i不等于increasingNewIndexSequece[lastIndex]，比如h节点。

因此move的条件是：

至此，我们说完了节点如何move。

如何获取最长递增子序列

接下来我们来看如何获取最长递增子序列，以上面的例子，从[5, 3, 4, 0]中获取最长递增子序列LIS，并返回LIS的下标数组。

上篇文章提到说让大家去做题LeetCode的「300. 最长递增子序列：https://leetcode-cn.com/problems/longest-increasing-subsequence/」，不知道大家做的怎么样了，其实核心原理是一样的，但是这里会难一些，因为LeetCode300只是让你返回LIS长度，而这里需要你把LIS路径计算下来。

对于LIS，有两种做法：纯动态规划的暴力解法、二分查找的优化解法。这两种解法我在b站都有视频讲解。前者时间复杂度高达O(n^2)，这样的时间复杂度在大项目中几乎是致命的，因此必须采用后者，后者时间复杂度只有O(nlogn)，在n值特别大的时候，这两个时间复杂度相差是很大的。

接下来我们先看下Vue中的getSequence代码的实现，这里我对Vue源码的命名做了一些改变，因为源码中的getSequence全是i、j、u、v、c这种命名，可读性太差。除了命名修改和赋值换行，其余代码是一样的：

  // 返回不需要移动的节点
  // 得到最长递增子序列lis（算法+实际应用，跳过0），返回路径
  function getSequence(arr) {
    // return [1, 2];

    // 最长递增子序列路径, 有序递增
    const lis = [0];

    // 相当于复制一份arr数组，此数组用于稍后纠正lis用的
    const recordIndexOfI = arr.slice();

    const len = arr.length;
    for (let i = 0; i < len; i++) {
      const arrI = arr[i];
      // 如果元素值为0，证明节点是新增的，老dom上没有，肯定不需要移动，所以跳过0，不在lis里
      if (arrI !== 0) {
        // 判断arrI插入到lis哪里
        const last = lis[lis.length - 1];
        // arrI比lis最后一个元素还大，又构成最长递增
        if (arr[last] < arrI) {
          // 记录第i次的时候，本来的元素是什么，后面要做回溯的
          recordIndexOfI[i] = last;
          lis.push(i);
          continue;
        }
        // 二分查找插入元素
        let left = 0,
          right = lis.length - 1;
        while (left < right) {
          const mid = (left + right) >> 1;
          //  0 1 2 3 4 (1.5)
          if (arr[lis[mid]] < arrI) {
            // mid< 目标元素 ， 在右边
            left = mid + 1;
          } else {
            right = mid;
          }
        }

        if (arrI < arr[lis[left]]) {
          // 从lis中找到了比arrI大的元素里最小的那个，即arr[lis[left]]。
          // 否则则没有找到比arrI大的元素，就不需要做什么了
          if (left > 0) {
            // 记录第i次的时候，上次的元素的是什么，便于后面回溯
            recordIndexOfI[i] = lis[left - 1];
          }
          lis[left] = i;
        }
      }
    }

    // 遍历lis，纠正位置
    let i = lis.length;
    let last = lis[i - 1];

    while (i-- > 0) {
      lis[i] = last;
      last = recordIndexOfI[last];
    }

    return lis;
  }

接下来我们来解析下这段代码，分为三点：

arrI值为0

首先注意下，我们现在说的是Vue实际场景，和纯算法不一样的一点是，上面例子中[5，3，4，0]中的0是新增的节点，而我们要寻找的是更新节点中的不需要移动的节点，因此新增的节点不能加入LIS计算中。

因此在getSequence中14行那里有一个判断arrI!==0，就是不计算0值。

记录路径与二分查找

记录路径需要一个数组，这里定义为lis，因为arr不可能为空，因此lis的结果至少有一个元素，因此lis初始值可设置为[0]。

// 最长递增子序列路径, 有序递增
 const lis = [0];

接下来遍历arr，arr[last]是lis的最后一个元素，如果arr[last]<arrI，则证明arrI加入原先的lis依然是递增的，因此这个值又可以记录下来加入lis了：

因为lis本身是递增的，而我们现在要寻找的是最长的lis，因此我们在不断往lis中加入新值的时候，为了lis尽可能的长，希望每次加入的值都尽可能的小。因此如果arr[last]>=arrI的时候，我们接下来可以去lis中寻找，看arrI能把谁替换掉。换谁呢？为了lis尽可能的长，当然是换那个比arrI大的元素中最小的了。

举个🌰，假如现在的数组里有[1, 3, 10]，这个时候忽然来了一个新值，怎么办？如果来的新值是20，则直接加到原先数组的末尾就行了，依然递增嘛。但是如果来了个5，怎么办，为了后面持续的可能递增，就用5把10换掉。不然后面再来了6，10挡着没法继续递增了呢。

那么，怎么换那个比arrI大的元素中最小的值呢，考虑到这里的lis是递增数组，很明显，用二分嘛~

因此，这个时候，lis中left的位置需要更换为i。但是注意这里我们要求取的是连续的最长递增子序列，比如[1, 3, 10，20]，来了新值5，如果我们只是单纯地把10换成了5，但是这样的[1, 3, 5, 20]并不是连续的最长递增子序列，只是长度恰好等于连续的最长递增子序列的长度，因为5在20的后面。所以在LeetCode300中可以这样二分完之后只修改left值就行了，但是在Vue中，还需要记录路径。