Renderer 更新 -> 最长递增子序列优化

在上一章中，我们实现了乱序 diff 算法，通过倒序插入的方式调整节点顺序。但这种做法存在一个性能问题——即使某些节点本身的相对顺序是正确的，也会被移动。实际上， DOM 移动操作是相对昂贵的，我们应该尽可能减少不必要的移动。这就是最长递增子序列算法发挥作用的地方。

问题场景：减少不必要的 DOM 移动

为什么需要优化

来看一个典型的场景：

节点变化：

• 旧节点：[a, b, c, d, e]
• 新节点：[a, c, d, b, e]

在这个例子中，节点 b 从索引 1 移动到了索引 3。如果我们按照之前的乱序 diff 算法，在倒序插入阶段会移动所有节点。但仔细观察可以发现：

• 节点 c 和 d 的相对位置没有变化，它们本来就是按顺序排列的
• 实际上只需要移动节点 b 到正确位置即可
• 移动 c、d 是完全不必要的操作

性能差异：

• 未优化：移动 3 个节点（c、d、b）
• 优化后：只移动 1 个节点（b）

这种优化在列表较长时效果更明显。通过找出新节点数组中相对顺序保持不变的最长子序列，我们就能确定哪些节点不需要移动，从而最小化 DOM 操作。

最长递增子序列的作用

在 diff 算法中，最长递增子序列（Longest Increasing Subsequence，简称 LIS）用于：

1. 识别稳定节点：找出在新旧节点映射关系中，位置呈递增关系的节点序列
2. 减少移动操作：这些节点的相对顺序没有变化，不需要移动
3. 优化性能：只移动必须移动的节点，最小化 DOM 操作

最长递增子序列算法

什么是最长递增子序列

**定义：**在一个序列中，找出最长的子序列，使得子序列中的元素严格递增。

示例 1：

数组: [1, 5, 3, 4, 7, 8]
最长递增子序列: [1, 3, 4, 7, 8]
长度: 5

示例 2：

数组: [10, 3, 5, 9, 12, 8, 15]
最长递增子序列: [3, 5, 9, 12, 15]
长度: 5

基础算法：贪心 + 二分查找

最长递增子序列有多种解法，最常见的是贪心 + 二分查找，时间复杂度为 O(n log n)。核心思路是：

1. 维护一个递增序列 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小末尾值
2. 遍历数组，对于每个元素：
   • 如果比 tails 最后一个元素大，直接追加
   • 否则，找到第一个大于等于它的位置，进行替换
3. 最终 tails 的长度就是最长递增子序列的长度

示例 1 ：1, 5, 3, 4, 7, 8

让我们逐步演示算法的执行过程：

结果：[1, 3, 4, 7, 8]，长度为 5

关键理解：

• 在步骤 3 中，用 3 替换 5，是因为 3 更小，为后续元素留出更多增长空间
• 虽然 tails 数组的最终值是 [1, 3, 4, 7, 8]，但这并不一定是实际的最长递增子序列（只是长度正确）
• 要获取实际的子序列，需要使用反向追溯技术

示例 2 ：10, 3, 5, 9, 12, 8, 15

**问题：**此时 tails 数组是 [3, 5, 8, 12, 15]，但这个序列有问题！

在原数组 [10, 3, 5, 9, 12, 8, 15] 中：

• 8 的索引是 5
• 12 的索引是 4
• 8 在 12 的后面，不满足递增关系

这就是为什么我们需要反向追溯来还原真正的最长递增子序列。

Vue 中的优化：反向追溯

为什么需要反向追溯

基础的贪心算法只能得到最长递增子序列的长度，但无法得到实际的子序列内容。在 Vue 的 diff 算法中，我们需要知道具体哪些节点是稳定的，所以必须还原出实际的子序列。

反向追溯的核心思路

在遍历数组时，不仅维护 tails 数组，还要记录每个元素的前驱节点：

• 前驱节点：在当前最长递增子序列中，当前元素的前一个元素
• 追溯过程：从最后一个元素开始，通过前驱关系反向构建子序列

示例 2 的反向追溯：10, 3, 5, 9, 12, 8, 15

让我们重新执行算法，这次记录前驱关系：

前驱关系图：

null ← 3 ← 5 ← 9 ← 12 ← 15
           ↖ 8

反向追溯过程：

从最后一个元素 15 开始，沿着前驱关系倒推：

1. 最后一个元素：15
2. 15 的前驱：12
3. 12 的前驱：9
4. 9 的前驱：5
5. 5 的前驱：3
6. 3 的前驱：null（结束）

最终结果：[3, 5, 9, 12, 15]

关键点理解

1. 为什么 8 不在最终结果中？
   • 虽然 8 被添加到了 tails 数组，但它的前驱是 5
   • 从最后一个元素 15 开始追溯时，路径是 15 → 12 → 9 → 5 → 3
   • 这条路径不经过 8，所以 8 不在最终的子序列中
2. tails 数组的作用
   • tails 数组只是算法的中间状态，用于维护贪心策略
   • 它的长度表示最长递增子序列的长度
   • 但它的内容不一定是实际的子序列
3. 前驱关系的重要性
   • 前驱关系记录了每个元素在递增序列中的"上一个"元素
   • 通过前驱关系，可以还原出实际的最长递增子序列
   • 追溯时从最后一个元素开始，保证了得到的是最长的那条路径

总结

通过本章的学习，我们理解了最长递增子序列算法及其在 Vue diff 优化中的应用。让我们回顾一下核心内容：

1. 为什么需要最长递增子序列：
   • 减少不必要的 DOM 移动操作
   • 识别出相对顺序未改变的节点
   • 显著提升列表更新的性能
2. 算法的核心思路：
   • 贪心策略：维护 tails 数组，记录不同长度子序列的最小末尾值
   • 二分查找：快速定位插入或替换位置
   • 时间复杂度：O(n log n)
3. 基础算法的局限性：
   • 只能得到子序列的长度
   • 无法直接获取实际的子序列内容
   • tails 数组可能包含不满足递增关系的元素
4. Vue 的优化：反向追溯：
   • 记录每个元素的前驱节点
   • 从最后一个元素开始反向构建子序列
   • 确保得到的是真正满足递增关系的序列
5. 关键技术点：
   • 前驱记录：维护元素在递增序列中的前一个元素
   • 倒序追溯：从结果向前回溯，还原完整路径
   • 路径选择：追溯过程自然选择了最长的那条路径

在下一章中，我们将把最长递增子序列算法应用到 diff 算法中，进一步优化节点的移动策略，实现真正高效的列表更新。