多图讲解Vue3的diff算法最长递增子序列实现原理

vue3的diff的算法用到了最长递增子序列 那么到底vue3是如何实现的呐？ 本文将通过一系列图文的方式，给大家分析下。

最后会附上Vue3的源码和注释。多图警告

算法整体思路

动态规划 + 二分查找 + 贪心算法 + 反向链表回溯修正

具体实现

let i = 0;
const source = [2, 5, 6, 1, 7, 3, 4, 10]; // 原数组
const resIndex = [] // 存储下标索引的结果

接下来我们一步一步通过图文的方式看vue是如何求出source的最长递增子序列的。

i = 0

resIndex为空数组，所以source[0] = 2的下标 直接放入resIndex结果中。 此时resIndex中最大值为2.

i =1

source[i] = 5 大于resIndex最后一项代表的值2，所以将5对象的下标 1 加入resIndex中。 resIndex中下标1的前一项索引为0 添加1指向0的前指针 如图箭头。

i =2

source[i] = 6 大于resIndex最后一项代表的值5，所以将6对象的下标 2 加入resIndex中。 resIndex中下标2的前一项索引为1 添加2指向1的前指针 如图箭头。

i =3

source[i] = 1 小于resIndex最后一项代表的值6，所以通过二分查找找到第一个比对象1大的值 然后用1替换掉。 例如这个例子中 resIndex=[0,1,2] resValue=[2,5,6] 因为序列是递增的，1和2相比 大于2的数字一定大于1 所以这里根据贪心算法 使用1替换掉2 同时更新resIndex=[3,1,2] resIndex中下标3的前一项索引为空 所以不需要添加前指针 如图箭头。

i = 4

source[i] = 7 大于resIndex最后一项代表的值6，所以将7对象的下标 4 加入resIndex中 resIndex中下标4的前一项索引为2 添加4指向2的前指针 如图箭头。

i = 5

source[i] = 3 小于resIndex最后一项代表的值7，所以通过二分查找找到第一个比对象3大的值，然后用3替换掉。 例如这个例子中 resIndex=[3,1,2,4] resValue=[1,5,6,7] 因为序列是递增的，3和5相比 大于5的数字一定大于3 所以这里根据贪心算法 使用3替换掉5 同时更新resIndex=[3,5,2，4] resIndex中下标5的前一项索引为3 添加5指向3的前指针 如图箭头。

i = 6

source[i] = 4 小于resIndex最后一项代表的值7，所以通过二分查找找到第一个比对象4大的值，然后用4替换掉。 例如这个例子中 resIndex=[3,5,2,4] resValue=[1,3,6,7] 因为序列是递增的，4和6相比 大于6的数字一定大于4 所以这里根据贪心算法 使用4替换掉6 同时更新resIndex=[3,5, 6，4] resIndex中下标6的前一项索引为5 添加6指向5的前指针 如图箭头。

i = 7

source[i] = 10 大于resIndex最后一项代表的值7，所以将 10 对象的下标 7 加入resIndex中 resIndex中下标7的前一项索引为4 添加7指向4的前指针 如图箭头。

产生的问题

目前我们已经得到了resIndex=[3,5,6,4,7] 代表的值value =[1,3,4,7,10] 我们已知最终结果为：[2,5,6,7,10] 显然目前长度是和结果一致的但是数据明显不对。 这是因为贪心算法在做替换的时 只关注当前的局部最优解而导致了最终结果的偏差。 所以我们需要对结果进行修正，此时就会用到我们之前设置的前指针.

回溯修正

我们从resIndex的最后一项开始 从后向前根据前指针 重新生成一个新的resIndex和新的结果。

• 第一步： resIndex = [7] value=[10]

• 第二步： 下标7的前指针为下标4 所以将下标4加入 resIndex = [4,7] value=[7,10]

• 第三步： 下标4的前指针为下标2 所以将下标2加入 resIndex = [2,4,7] value=[6,7,10]

• 第四步： 下标2的前指针为下标1 所以将下标1加入 resIndex = [1,2,4,7] value=[5,6,7,10]

• 第五步： 下标1的前指针为下标0 所以将下标0加入 resIndex = [0,1,2,4,7] value=[2,5,6,7,10]

得到最终的递增序列：resIndex = [0,1,2,4,7] value=[2,5,6,7,10]

vue源码解析: getSequence

function getSequence(arr) {
  const p = arr.slice(); // 这个是用于标识前指针的数组 和文章中的箭头等价
  const result = [0]; // result 这个是存储结果索引的数组 和文章中的resIndex等价
  let i, j, u, v, c;
  const len = arr.length;
  for (i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) { // arrI !== 0 这个判断可以先忽略和最长递增子序列算法无关 是dom操作用于新增节点的
      j = result[result.length - 1];
      if (arr[j] < arrI) { // 这里是判断数组的item是否大于结果的最大值 大于最大值说明递增 
        p[i] = j; // 这里是更新前指针
        result.push(i); // 递增的情况 下标直接加入到结果索引
        continue;
      }
      u = 0;
      v = result.length - 1;
      while (u < v) { // 不大于最大值 通过二分查找 找到正确位置 插入替换
        c = (u + v) >> 1;
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]; // 插入替换时 同样更新前指针
        }
        result[u] = i; // 插入替换
      }
    }
  }
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) { // 这里从后向前 回溯修正结果 
    result[u] = v;
    v = p[v];
  }
  return result; // 返回正确的结果索引 注意并不是返回结果数值 算法从头到尾都是对索引操作
}