【vue】diff算法简介

一、先搞懂：最长递增子序列（LIS）是什么？

最长递增子序列（Longest Increasing Subsequence，简称 LIS）是动态规划/贪心+二分领域的经典算法问题，核心是找一个数组中「元素严格/非严格递增、且不要求连续」的最长子序列。

1. 核心概念（通俗举例）

• 子序列：数组中挑出部分元素（顺序不变，可间隔），比如[10,9,2,5,3,7,101,18]的子序列可以是[2,5,7,101]；
• 递增：子序列中后一个元素 > 前一个（严格递增，也可定义为 ≥ 非严格）；
• LIS：满足递增的最长子序列，比如上面数组的 LIS 长度是 4（[2,3,7,101]或[2,5,7,101]）。

2. 两种核心解法（重点讲 Vue3 用的高效版）

贪心+二分 通俗示例（比如数组[2,5,3,7,11,8,10,13,6]）

1. 初始化空数组tails = []；
2. 遍历每个元素：
   • 2：tails 空，直接加 →[2]；
   • 5：比 tails 最后一个大，加 →[2,5]；
   • 3：比 5 小，找 tails 中第一个 ≥3 的位置（索引1），替换 5 →[2,3]；
   • 7：比 3 大，加 →[2,3,7]；
   • 11：加 →[2,3,7,11]；
   • 8：替换 11 →[2,3,7,8]；
   • 10：替换 8 →[2,3,7,10]；
   • 13：加 →[2,3,7,10,13]；
   • 6：替换 7 →[2,3,6,10,13]；
3. 最终 tails 长度 5，就是 LIS 长度（注意 tails 不是真正的 LIS，只是长度相等）。

二、Vue3 中是否用到 LIS？—— 不仅用了，还很关键！

Vue3 在虚拟 DOM 的 diff 算法中，核心使用了 LIS 算法优化「列表更新时的 DOM 移动逻辑」，是提升 diff 性能的关键。

1. 为什么需要 LIS？（背景）

当 Vue 渲染列表（比如v-for）且节点有key时，更新列表（比如增删、排序）需要对比「老 vnode 数组」和「新 vnode 数组」，核心目标是：最小化 DOM 操作（少移动、少删除/新增）。

比如老列表：[a, b, c, d]（key 对应），新列表：[b, d, a, c]。如果直接暴力更新，会大量移动 DOM；但如果找到「不需要移动的最长节点序列」，只移动其他节点，就能大幅减少操作。

2. Vue3 中 LIS 的具体应用流程

Vue3 的patchChildren方法（处理子节点更新）中，针对「新老节点都是数组且有 key」的场景，核心步骤：

步骤1：建立映射，筛选“可复用节点”

• 遍历新节点数组，记录「key → 新节点索引」的映射；
• 遍历老节点数组，找到“新数组中也存在的节点”，生成一个source数组：source[i] = 新数组中该老节点的索引（不存在则为 -1）。

举例：

• 老节点：[a(key:a), b(key:b), c(key:c), d(key:d)]
• 新节点：[b(key:b), d(key:d), a(key:a), c(key:c)]
• source 数组：[2, 0, 3, 1]（a 在新数组索引 2，b 在 0，c 在 3，d 在 1）。

步骤2：计算 source 数组的 LIS（关键！）

上面的 source 数组[2,0,3,1]，其严格递增的 LIS是[0,1]（对应老节点 b、d）或[2,3]（对应 a、c）—— 这个 LIS 对应的老节点，就是「不需要移动的最长序列」。

步骤3：基于 LIS 最小化 DOM 移动

Vue3 会从后往前遍历新节点，结合 LIS 结果：

• LIS 中的节点：位置已经“天然有序”，无需移动；
• 非 LIS 中的节点：只需要移动到目标位置，而非删除重建。

3. 为什么用 LIS？

因为 LIS 是「最长的无需移动序列」，能最大程度减少 DOM 操作次数（DOM 移动是高性能开销操作），把 diff 算法的时间复杂度从 O(n²) 优化到 O(n log n)，这也是 Vue3 diff 比 Vue2 更高效的核心原因之一。

4. Vue3 中 LIS 的源码位置

核心代码在runtime-core/src/patchChildren.ts中的getSequence函数（就是贪心+二分实现的 LIS），简化版核心逻辑如下：

// Vue3 源码中 getSequence 函数（简化版）functiongetSequence(arr){constlen=arr.length;constresult=[0];// 存储 LIS 的索引（不是值）constp=newArray(len).fill(0);// 记录前驱节点，用于还原完整 LISletlastIndex;letstart,end,mid;for(leti=0;i<len;i++){constval=arr[i];lastIndex=result[result.length-1];if(val>arr[lastIndex]){p[i]=lastIndex;result.push(i);continue;}// 二分找替换位置start=0;end=result.length-1;while(start<end){mid=(start+end)>>1;if(arr[result[mid]]<val){start=mid+1;}else{end=mid;}}if(val<arr[result[start]]){if(start>0){p[i]=result[start-1];}result[start]=i;}}// 还原完整的 LIS 索引leti=result.length;letlast=result[i-1];while(i--){result[i]=last;last=p[last];}returnresult;}

三、总结

1. 最长递增子序列（LIS）是找数组中「最长递增非连续子序列」的算法，Vue3 用的是 O(n log n) 的贪心+二分实现；
2. Vue3 在列表 diff 算法中核心依赖 LIS：通过计算可复用节点索引数组的 LIS，找到“无需移动的最长节点序列”，最小化 DOM 操作，提升更新性能；
3. 这是 Vue3 对比 Vue2 diff 算法的重要优化点（Vue2 未用 LIS，diff 时间复杂度更高）。