在上一章中，我们深入理解了最长递增子序列算法的原理和反向追溯技术。现在，是时候将这个强大的算法应用到 Vue 的 diff 过程中了。通过这一优化，我们能够显著减少 DOM 移动操作，提升列表更新的性能。

核心思路：从理论到实践

关键点理解

在将算法应用到 diff 中之前，有一个重要的细节需要明确：

最长递增子序列计算的是索引，而不是值。

在 Vue 的场景中：

输入：新节点在旧节点中的位置索引数组
输出：不需要移动的节点索引数组
目标：找出相对顺序保持不变的节点

应用场景回顾

假设我们有这样的节点变化：

旧节点：[a, b, c, d, e] （索引：0, 1, 2, 3, 4）
新节点：[a, c, d, b, e] （索引：0, 1, 2, 3, 4）

索引映射关系：

新节点位置	节点	在旧节点中的位置
0	a	0
1	c	2
2	d	3
3	b	1
4	e	4

映射数组：[0, 2, 3, 1, 4]

对这个数组求最长递增子序列，得到 [0, 2, 3, 4]，这意味着索引 0、1、2、4 位置的节点（即 a、c、d、e）不需要移动。

实现最长递增子序列算法

完整代码实现

基于前面的理论，我们来实现带有反向追溯功能的最长递增子序列算法：

function getSequence(arr) {
  const result = []
  const map = new Map()

  for (let i = 0; i < arr.length; i++) {
    const item = arr[i]
    // 跳过无效值（-1 表示新增节点）
    if (item === -1 || item === undefined)
      continue

    // 初始情况：result 为空，直接添加第一个元素
    if (result.length === 0) {
      result.push(i)
      continue
    }

    // 获取当前最长序列的最后一个元素
    const lastIndex = result[result.length - 1]
    const lastItem = arr[lastIndex]

    // 情况1：当前元素比最后一个大，直接追加
    if (item > lastItem) {
      result.push(i)
      map.set(i, lastIndex) // 记录前驱
      continue
    }

    // 情况2：需要替换，使用二分查找找到插入位置
    let left = 0
    let right = result.length - 1

    while (left < right) {
      const mid = Math.floor((left + right) / 2)
      const midItem = arr[result[mid]]

      if (midItem < item) {
        left = mid + 1
      }
      else {
        right = mid
      }
    }

    // 替换找到的位置，并记录前驱关系
    if (arr[result[left]] > item) {
      if (left > 0) {
        map.set(i, result[left - 1])
      }
      result[left] = i
    }
  }

  // 反向追溯，还原真正的最长递增子序列
  let l = result.length
  let last = result[l - 1]
  while (l > 0) {
    l--
    result[l] = last
    last = map.get(last)
  }
  return result
}

代码逐步解析

1. 初始化阶段

const result = [] // 存储当前最长递增子序列的索引
const map = new Map() // 记录前驱关系

2. 遍历数组

对每个元素有三种情况：

情况	条件	操作	前驱记录
跳过	值为 -1 或 undefined	continue	-
追加	比最后一个元素大	result.push(i)	map.set(i, lastIndex)
替换	比最后一个元素小	resultleft = i	map.set(i, resultleft-1)

3. 二分查找

当需要替换时，使用二分查找快速定位插入位置：

let left = 0
let right = result.length - 1

while (left < right) {
  const mid = Math.floor((left + right) / 2)
  const midItem = arr[result[mid]]

  if (midItem < item) {
    left = mid + 1 // 在右半部分
  }
  else {
    right = mid // 在左半部分或就是 mid
  }
}

4. 反向追溯

通过前驱关系还原真正的子序列：

let l = result.length
let last = result[l - 1]
while (l > 0) {
  l--
  result[l] = last
  last = map.get(last) // 找到前一个元素
}

算法示例演示

以数组 [0, 2, 3, 1, 4] 为例：

步骤	元素	操作	result	前驱关系
1	0	追加	0	-
2	2	追加	0, 1	1 → 0
3	3	追加	0, 1, 2	2 → 1
4	1	替换	0, 3, 2	3 → 0
5	4	追加	0, 3, 2, 4	4 → 2

反向追溯：

从 4 开始 → 2 → 1 → 0
最终结果：[0, 1, 2, 4]

集成到 diff 算法中

第一步：构建索引映射

在乱序 diff 阶段，我们需要记录新节点在旧节点中的位置：

function patchKeyedChildren(c1, c2, container) {
  const s1 = i
  const s2 = i

  const keyToNewIndexMap = new Map()

  // 创建映射数组，记录新节点在旧节点中的位置
  const newIndexToOldIndexMap = new Array(e2 - s2 + 1)
  // -1 表示这是新增的节点（在旧节点中不存在）
  newIndexToOldIndexMap.fill(-1)

  // 遍历新节点，建立 key 到索引的映射
  for (let j = s2; j <= e2; j++) {
    const n2 = c2[j]
    keyToNewIndexMap.set(n2.key, j)
  }

  // 遍历旧节点，更新映射数组
  for (let j = s1; j <= e1; j++) {
    const n1 = c1[j]
    const newIndex = keyToNewIndexMap.get(n1.key)

    if (newIndex != null) {
      // 记录这个新节点在旧节点中的位置
      newIndexToOldIndexMap[newIndex - s2] = j
      patch(n1, c2[newIndex], container)
    }
    else {
      // 旧节点在新节点中不存在，卸载
      unmount(n1)
    }
  }

  // ... 后续处理
}

第二步：应用最长递增子序列

function patchKeyedChildren(c1, c2, container) {
  // ... 前面的代码

  // 计算最长递增子序列
  const newIndexSequence = getSequence(newIndexToOldIndexMap)
  // 使用 Set 提升查找性能
  const sequenceSet = new Set(newIndexSequence)

  // 倒序遍历新节点，进行插入和移动
  for (let j = e2; j >= s2; j--) {
    const n2 = c2[j]
    const anchor = c2[j + 1]?.el || null

    if (n2.el) {
      // 节点已存在
      if (!sequenceSet.has(j - s2)) {
        // 不在最长递增子序列中，需要移动
        hostInsert(n2.el, container, anchor)
      }
      // 在子序列中的节点不需要移动
    }
    else {
      // 新增节点，直接挂载
      patch(null, n2, container, anchor)
    }
  }
}

关键逻辑解析

1. 为什么使用 Set？

const sequenceSet = new Set(newIndexSequence)

判断元素是否在数组中，Set 的时间复杂度是 O(1)
数组的 includes 方法是 O(n)
在循环中频繁查找时，Set 性能更优

2. 为什么倒序遍历？

倒序遍历确保每次插入时，锚点元素（anchor）已经处于正确位置：

for (let j = e2; j >= s2; j--) {
  const anchor = c2[j + 1]?.el || null
  // 使用下一个元素作为锚点进行插入
}

3. 移动判断

if (!sequenceSet.has(j - s2)) {
  hostInsert(n2.el, container, anchor)
}

只有不在最长递增子序列中的节点才需要移动，这就是优化的核心。

进一步优化：避免不必要的计算

优化场景分析

虽然我们已经通过最长递增子序列优化了移动操作，但算法本身的计算也是有成本的。考虑这样的场景：

示例：

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

在这个例子中：

新增了 h 和 g 两个节点
b、c、d 的相对顺序完全没变
索引映射：[-1, 1, 2, 3, -1, 4]（-1 表示新增）

观察发现：

去除新增节点后：[1, 2, 3, 4]
这本身就是递增序列，不需要移动任何节点
只需要插入 h 和 g 即可

**结论：**如果节点本身就是递增的，就不需要计算最长递增子序列了。

判断是否需要移动

我们可以在遍历过程中判断索引是否递增：

function patchKeyedChildren(c1, c2, container) {
  // ... 前面的代码

  // 记录上一个处理的新索引位置
  let pos = -1
  // 标记是否需要移动
  let moved = false

  for (let j = s1; j <= e1; j++) {
    const n1 = c1[j]
    const newIndex = keyToNewIndexMap.get(n1.key)

    if (newIndex != null) {
      // 如果当前索引比上一个大，说明是递增的
      if (newIndex > pos) {
        pos = newIndex
      }
      else {
        // 出现了递减，说明需要移动
        moved = true
      }

      newIndexToOldIndexMap[newIndex - s2] = j
      patch(n1, c2[newIndex], container)
    }
    else {
      unmount(n1)
    }
  }

  // 只有需要移动时才计算最长递增子序列
  const newIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : []
  const sequenceSet = new Set(newIndexSequence)

  for (let j = e2; j >= s2; j--) {
    const n2 = c2[j]
    const anchor = c2[j + 1]?.el || null

    if (n2.el) {
      // 只有在需要移动时才判断是否在子序列中
      if (moved) {
        if (!sequenceSet.has(j - s2)) {
          hostInsert(n2.el, container, anchor)
        }
      }
      // 不需要移动时，所有节点都保持原位
    }
    else {
      patch(null, n2, container, anchor)
    }
  }
}

优化效果分析

场景对比：

场景	旧节点	新节点	moved	操作
需要移动	a,b,c,d,e	a,c,d,b,e	true	计算 LIS，移动 b
无需移动	a,b,c,d,e	a,h,b,c,d,g,e	false	跳过 LIS，仅插入 h、g

性能提升：

避免不必要的 O(n log n) 计算
减少内存分配（不创建 result 和 map）
在节点顺序基本稳定的场景下效果显著

递增判断的原理

let pos = -1
for (let j = s1; j <= e1; j++) {
  const newIndex = keyToNewIndexMap.get(n1.key)
  if (newIndex != null) {
    if (newIndex > pos) {
      pos = newIndex // 更新最大索引
    }
    else {
      moved = true // 出现递减，标记需要移动
    }
  }
}

工作原理：

初始化 pos = -1，表示还没有处理过任何节点
递增情况：每次 newIndex > pos，更新 pos，说明顺序正常
递减情况：出现 newIndex <= pos，说明有节点位置倒退了，需要移动

示例：

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

遍历过程：
- a: newIndex=0, pos=-1 → 0>-1, pos=0 ✓
- b: newIndex=3, pos=0  → 3>0,  pos=3 ✓
- c: newIndex=1, pos=3  → 1<3,  moved=true ✗
- d: newIndex=2, pos=3  → 2<3,  继续
- e: newIndex=4, pos=3  → 4>3,  pos=4 ✓

完整代码汇总

getSequence 函数

function getSequence(arr) {
  const result = []
  const map = new Map()

  for (let i = 0; i < arr.length; i++) {
    const item = arr[i]
    if (item === -1 || item === undefined)
      continue
    if (result.length === 0) {
      result.push(i)
      continue
    }
    const lastIndex = result[result.length - 1]
    const lastItem = arr[lastIndex]
    if (item > lastItem) {
      result.push(i)
      map.set(i, lastIndex)
      continue
    }

    let left = 0
    let right = result.length - 1

    while (left < right) {
      const mid = Math.floor((left + right) / 2)
      const midItem = arr[result[mid]]

      if (midItem < item) {
        left = mid + 1
      }
      else {
        right = mid
      }
    }

    if (arr[result[left]] > item) {
      if (left > 0) {
        map.set(i, result[left - 1])
      }
      result[left] = i
    }
  }

  let l = result.length
  let last = result[l - 1]
  while (l > 0) {
    l--
    result[l] = last
    last = map.get(last)
  }
  return result
}

patchKeyedChildren 函数

function patchKeyedChildren(c1, c2, container) {
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1

  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container)
    }
    else {
      break
    }
    i++
  }
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container)
    }
    else {
      break
    }
    e1--
    e2--
  }
  if (i > e1) {
    const nextPos = e2 + 1
    const anchor = nextPos < c2.length ? c2[nextPos].el : null
    while (i <= e2) {
      patch(null, c2[i], container, anchor)
      i++
    }
  }
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i])
      i++
    }
  }
  else {
    const s1 = i
    const s2 = i
    const keyToNewIndexMap = new Map()
    const newIndexToOldIndexMap = new Array(e2 - s2 + 1)
    newIndexToOldIndexMap.fill(-1)

    let pos = -1
    let moved = false
    for (let j = s2; j <= e2; j++) {
      const n2 = c2[j]
      keyToNewIndexMap.set(n2.key, j)
    }
    for (let j = s1; j <= e1; j++) {
      const n1 = c1[j]
      const newIndex = keyToNewIndexMap.get(n1.key)
      if (newIndex != null) {
        if (newIndex > pos) {
          pos = newIndex
        }
        else {
          moved = true
        }
        newIndexToOldIndexMap[newIndex] = j
        patch(n1, c2[newIndex], container)
      }
      else {
        unmount(n1)
      }
    }
    const newIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : []
    const sequenceSet = new Set(newIndexSequence)
    for (let j = e2; j >= s2; j--) {
      const n2 = c2[j]
      const anchor = c2[j + 1]?.el || null
      if (n2.el) {
        if (moved) {
          if (!sequenceSet.has(j)) {
            hostInsert(n2.el, container, anchor)
          }
        }
      }
      else {
        patch(null, n2, container, anchor)
      }
    }
  }
}

总结

通过本章的学习，我们完成了最长递增子序列算法在 Vue diff 中的完整应用。让我们回顾一下核心要点：

1. 算法实现

输入处理：处理新节点在旧节点中的索引映射数组
贪心策略：维护 result 数组记录当前最优解
二分查找：快速定位替换位置，保证 O(n log n) 复杂度
反向追溯：通过前驱关系还原真正的最长递增子序列

2. diff 集成

索引映射：创建 newIndexToOldIndexMap 记录节点位置关系
子序列计算：找出不需要移动的稳定节点
选择性移动：仅移动不在子序列中的节点
倒序插入：确保锚点元素位置正确

3. 性能优化

递增判断：通过 pos 变量判断是否需要移动
条件计算：只在必要时计算最长递增子序列
使用 Set：优化查找性能，从 O(n) 降至 O(1)

4. 优化效果

移动次数对比：

场景	节点变化	乱序 diff	LIS 优化	优化效果
示例1	a,b,c,d,e → a,c,d,b,e	3次移动	1次移动	减少67%
示例2	a,b,c,d,e → a,h,b,c,d,g,e	5次移动	0次移动	减少100%

算法复杂度：

时间复杂度：O(n log n)（最长递增子序列） + O(n)（diff 过程） = O(n log n)
空间复杂度：O(n)（索引映射 + 前驱关系）
优化判断：O(n)（递增检测）

5. 关键技术点

计算对象：操作的是索引而不是值
前驱记录：使用 Map 存储前驱关系
反向追溯：从最后一个元素倒推，还原完整路径
倒序处理：确保锚点元素已就位
条件优化：避免不必要的算法计算

至此，我们完成了 Vue 渲染器 diff 算法的核心优化。这套算法在实际应用中能够显著提升列表更新的性能，特别是在处理大型列表和复杂节点顺序变化时，效果尤为明显。

Renderer 更新 -> 最长递增子序列应用