Vue3渲染器之快速Diff算法

站长

2023年10月07日 19:12 · 阅读数 14

Vue3中使用的就是快速Diff算法性能优于Vue2所采用的双端 Diff 算法可能其他的文章会让你先看一道算法题,即力扣第300题最长递增子序列,对于没有算法基础的同学理解会有困难. 里面涉及到动态规划,二分查找,Vue源码中采用的是二分查找.区别就是二分复杂度是nlogn,动态规划是n的平方,笔者写这篇文章的时候也只是弄懂了动态规划. 所以如果实在看不懂可以先跳过,毕竟并不是快速Diff第一步就需要它.

快速 Diff 算法第一步是预处理

Vue3渲染器之快速Diff算法其实很简单就是比较首和尾是否相同.上面就是前置节点1,后置节点2,3相同

对于相同的前置节点和后置节点，由于它们在新旧两组子节点中的相对位置不变，所以我们无须移动它们，但仍然需要在它们之间打补丁。

遍历前置节点,新旧节点只需要从同一位置开始比较,所以只需要设置一个索引j的值为 0.进入while循环,判断key是否相同.退出循环,j变成1
遍历后置节点,新旧节点因为长度可能不同,需要声明两个索引newEnd,oldEnd,指向新旧数组最后一个元素进入while循环,判断key是否相同.退出循环,此时newEnd变成1,oldEnd变成0.这些指的都是数组下标.

由这几个下标可知:

oldEnd < j 成立：说明在预处理过程中，所有旧子节点都处理完毕了
newEnd >= j 成立：说明在预处理过后，在新的一组子节点中，仍然有未被处理的节点，而这些遗留的节点将被视作新增节点
当这两个条件都满足,表示旧节点数组不用处理,新节点数组中需要添加节点,添加范围就是j和newEnd之间的元素.
找到一个挂载点进行挂载,即是新数组中下标为newEnd+1的元素.然后循环将j和newEnd之间的元素进行挂载

// 预处理完毕后，如果满足如下条件，则说明从 j --> newEnd 之间的节点应作为新节点插入
if (j > oldEnd && j <= newEnd) {
  // 锚点的索引
  const anchorIndex = newEnd + 1
  // 锚点元素
  const anchor =
    anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
  // 采用 while 循环，调用 patch 函数逐个挂载新增节点
  while (j <= newEnd) {
    patch(null, newChildren[j++], container, anchor)
  }
}

接下来看另一种情况,就是要将旧节点元素删除

Vue3渲染器之快速Diff算法

这里很类似,就不再赘述

else if (j > newEnd && j <= oldEnd) {
     // j -> oldEnd 之间的节点应该被卸载
     while (j <= oldEnd) {
     unmount(oldChildren[j++])
     }
     }

上面给出的例子比较理想化，当处理完相同的前置节点或后置节点后，新旧两组子节点中总会有一组子节点全部被处理完毕。在这种情况下，只需要简单地挂载、卸载节点即可

对于所有的Diff算法都遵循两个规则

判断是否有节点需要移动，以及应该如何移动
找出那些需要被添加或移除的节点。

对于非理想的情况下，当相同的前置节点和后置节点被处理完毕后，索引 j、newEnd 和 oldEnd都不满足上面两个条件，所以需要增加新的 else 分支

现在我们的代码逻辑是

先进行预处理，预处理之后获取下标j newEnd oldEnd,根据他们的关系进入不同的条件分支一种情况是新节点全部被处理，另一种是旧节点全部被处理，非理想情况下新旧都没有处理完当成最后一种情况

下面这种情况多了一个节点7，少了一个节点6，预处理之后新旧数组都没处理完。

   children: [
                { type: 'p', children: '1', key: 1 },
                { type: 'p', children: '2', key: 2 },
                { type: 'p', children: '3', key: 3 },
                { type: 'p', children: '4', key: 4 },
                { type: 'p', children: '6', key: 6 },
                { type: 'p', children: '5', key: 5 },
            ]
  vnode.children =
            [
                { type: 'p', children: '1', key: 1 },
                { type: 'p', children: '3', key: 3 },
                { type: 'p', children: '4', key: 4 },
                { type: 'p', children: '2', key: 2 },
                { type: 'p', children: '7', key: 7 },
                { type: 'p', children: '5', key: 5 },
            ]

我们需要构造一个数组 source，它的长度等于新的一组子节点在经过预处理之后剩余未处理节点的数量，并且 source 中每个元素的初始值都是 -1

const count = newEnd - j + 1
const source = new Array(count)
source.fill(-1)

source 数组将用来存储新的一组子节点中的节点在旧的一组子节点中的位置索引也就是 [2, 3, 1, -1]
可以使用双重for循环，如果查找到新旧数组元素key相同，则将旧数组的索引赋给source的对应下标，但是复杂度有点高。所以可以新建一个索引表，即新数组的key，对应新数组的下标。
第一个 for 循环用来构建索引表，索引表存储的是节点的 key 值与节点在新的一组子节点中位置索引之间的映射，第二个 for 循环用来遍历旧的一组子节点。可以看到，我们拿旧子节点的 key 值去索引表 keyIndex 中查找该节点在新的一组子节点中的位置，并将查找结果存储到变量 u 中。如果 u 存在，说明该节点是可复用的，所以我们调用 patch 函数进行打补丁，并填充 source 数组；否则说明该节点已经不存在于新的一组子节点中了，这时我们需要调用 unmount 函数卸载它。

                            // 构建索引表
                            const keyIndex = {}
                            for (; newStart <= newEnd; newStart++) {
                                keyIndex[newChildren[newStart].key] = newStart
                            }
                            for (; oldStart <= oldEnd; oldStart++) {
                                oldVNode = oldChildren[oldStart]
                                let u = keyIndex[oldVNode.key]
                                if (u) {
                                    newVNode = newChildren[u]
                                    // 调用 patch 函数完成更新
                                    patch(oldVNode, newVNode, container)
                                    source[u - j] = oldStart
                                }
                                else {
                                    //not found
                                    unmount(oldVNode)
                                }
                            }

此时我们只需要专注于source.由于在处理source时，旧节点数组需要被卸载的已经卸载了，source中的-1代表新元素需要挂载。那么我们现在要考虑的是哪些元素需要移动，这与之前讲的简单diff有些相似，如果一个新元素在旧节点数组的索引小于上一个元素在旧节点数组的索引，那么他就需要移动。
换言之，我们只需要找到一条最长的递增子序列就能保证大多数节点不需要移动，(最长递增子序列可能有多种情况但只需要任意一种即可)，上面的例子获得的子序列索引数组就是[0,1]代表key为2，3节点。也就是不需要移动
接下来就只需要处理剩下的source元素，如果等于-1代表新增节点。具体处理如下，大功告成

for (let i = source.length - 1; i >= 0; i--) {
    if (source[i] === -1) {
        const pos = i + j 
        const newVNode = newChildren[pos] 
        let anchor = newChildren[pos + 1] ? newChildren[pos + 1].el: null patch(null, newVNode, container, anchor)
    }
    if (getSequence(source).filter(item = >item !== i)) {
        const pos = i + j 
        const newVNode = newChildren[pos] 
        let anchor = newChildren[pos + 1] ? newChildren[pos + 1].el: null insert(newVNode.el, container, anchor)
    }
}

这是我自己写的返回最长递增子序列索引数组函数，仅供参考哦

var lengthOfLIS = function (nums) {
  let dp = [];
  let arr = [[0]];
  dp.length = nums.length;
  dp.fill(1);
  for (let i = 1; i < nums.length; i++) {
    let flag = false;
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        flag = true;
        if (dp[i] < dp[j] + 1) {
          arr[i] = [...arr[j], i];
        }
        dp[i] = Math.max(dp[i], dp[j] + 1);
      } else if (!flag) {
        arr[i] = [i];
      }
    }
  }
  console.log(arr);
  let length = 0;
  let index = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i].length > length) {
      index = i;
      length = arr[i].length;
    }
  }
};
lengthOfLIS([1, 2, 3, 4, 1]);