Vue.js快速Diff算法之最长递增子序列算法在DOM中的应用-Vue.js-PHP中文网

Vue.js 的快速 Diff 算法利用最长递增子序列（LIS）识别可复用节点以最小化 DOM 移动，先构建新节点在旧列表中的位置数组，再用贪心+二分求 LIS，据此标记不动节点并指导 patch 操作。

vue.js快速diff算法之最长递增子序列算法在dom中的应用

Vue.js 的快速 Diff 算法在处理列表更新时，并不直接暴力比对所有节点，而是借助最长递增子序列（LIS）来最小化 DOM 移动操作。它的核心目标不是找出“完全匹配”，而是确定哪些节点可以复用、哪些需要移动——而 LIS 正是求解“最少移动次数”的数学钥匙。

为什么需要 LIS？——从“移动代价”说起

当新旧 vnode 列表长度相同但顺序变化时（如 [a,b,c,d] → [b,a,d,c]），理想策略是只移动真正位置变了的节点，其余保持原位并复用。但如何判断“哪些能不动”？关键在于找出新列表中在旧列表里已有相对顺序的最长子序列。这个子序列里的节点，在 DOM 中原本就处于“正确相对位置”，无需移动；其余节点则需插入或调整。

LIS 在这里的作用是：把“节点复用+最小移动”问题，转化为一个经典的贪心动态规划问题，时间复杂度控制在 O(n log n)，远优于暴力 O(n²)。

如何构建 LIS 所需的“位置数组”？

算法第一步不是直接找子序列，而是为新列表中每个节点，查它在旧列表中的索引位置，生成一个 映射数组 newIndexToOldIndexMap：

遍历新列表，对每个节点 key，查它在旧列表中最后一次出现的索引（即 oldKeyToIndex 哈希表查找）
若没找到，记为 0（表示新节点）；若找到，记下该索引值
最终得到一个长度为 newLength 的数组，例如：[2, 0, 3, 1]（对应新节点在旧列表的位置）

这个数组中，严格递增的子序列（如 [2,3] 或 [0,1]）就代表一组在旧列表中本就“顺序靠前→靠后”的节点，它们在新列表中依然维持了这种偏序关系，因此可保留在原 DOM 位置上。

用贪心法求 LIS，并反推“不动节点”的索引

Vue 不需要完整 LIS 序列，只需要知道哪些新节点索引属于 LIS，从而标记为“不移动”。它采用经典贪心 + 二分方式构造 LIS 的 tails 数组，并同步维护 prev 和 result 数组回溯路径：

vue-composition-api-best-practices

Vue 3 组合式 API 与最佳实践，涵盖代码组织、useXxx 模式、组合式函数设计、Store 集成、响应式优化及功能抽取。

下载

tails[i] 存储长度为 i+1 的递增子序列的最小末尾值
遍历位置数组时，用二分定位插入点，更新 tails，同时记录每个位置的前驱索引
最后从 tails 最长长度处倒推，还原出 LIS 对应的新节点下标集合

这些下标对应的 vnode 就是“可原位复用、无需移动”的节点；其余节点则进入 insert/move 流程。

DOM 操作如何与 LIS 结果联动？

LIS 输出的“不动节点集合”，直接指导 patch 过程：

对属于 LIS 的新节点：跳过移动，仅执行 props 更新和子树 diff
对不属于 LIS 的节点：
- 若在旧列表中存在（key 匹配），则调用 moveNode 插入到正确位置（参考其在新列表的索引）
- 若不存在（key 新增），则创建新节点并插入
整个过程只需一次 DOM 插入/移动循环，避免反复重排

例如新列表 [b,a,d,c] 对应位置数组 [1,0,3,2]，其 LIS 可能是 [0,2]（对应新索引 1 和 3），意味着 a 和 c 可保位，b 和 d 需调整位置。

不复杂但容易忽略：LIS 在这里不是为了排序，而是为了识别“顺序保真度”最高的节点链——它是 Vue 在响应式更新中兼顾性能与准确性的关键数学支点。