精读《Vuejs设计与实现》第 11 章（快速 diff 算法）

我们将探讨第三种用于比较新旧子节点集合的方法：快速Diff算法。这种算法的速度非常快，最早应用于 ivi 和 inferno 框架，DOM 操作方面的性能略优于 Vue.js 2 的双端 Diff 算法，Vue3 也对其进行了借鉴和扩展。

11.1 相同的前置元素和后置元素

快速 Diff 算法包含预处理步骤，这实际上是借鉴了纯文本 Diff 算法的思路。在纯文本 Diff 算法中，需要对两段文本进行预处理。例如，在进行 Diff 之前，可以先进行全等比较：

if (text1 === text2) return

这称为快捷路径。如果两段文本完全相等，就无需进入核心Diff算法步骤。除此之外，预处理过程还会处理两段文本相同的前缀和后缀。假设有如下两段文本：

I use vue for app development
I use react for app development

上面两段文本的头部和尾部分别有一段相同的内容，对于内容相同的问题，是不需要进行核心 Diff 操作的。因此，上面两句话，真正需要进行 Diff 操作的部分是：

vue
react

这实际上是简化问题的一种方式。这样的好处是在特定情况下我们能够轻松地判断文本的插入和删除：

I like you
I like you too

经过预处理，去掉这两段文本中相同的前缀内容和后缀内容之后，它将变成：

too

可以看到，经过预处理后，第一段的内容为空。这说明第二段的内容在第一段的基础上增加了字符串 too。

快速 Diff 算法借鉴了纯文本 Diff 算法中的预处理步骤：观察发现，两组子节点具有相同的前置节点 p-1，以及相同的后置节点 p-2 和 p-3对于相同的前置节点和后置节点，因为它们在新旧子节点组中的相对位置不变，我们无须移动它们，但仍需在它们之间打补丁。对于前置节点，我们可以建立索引 j，其初始值为 0，用于指向两组子节点的开头：然后开启一个 while 循环，让索引 j 递增，直到遇到不相同的节点为止，如下代码所示：

function patchKeyedChildren(n1, n2, container) {
  const newChildren = n2.children
  const oldChildren = n1.children
  // 处理相同的前置节点
  // 索引 j 指向新旧两组子节点的开头
  let j = 0
  let oldVNode = oldChildren[j]
  let newVNode = newChildren[j]
  // while 循环向后遍历，直到遇到拥有不同 key 值的节点为止
  while (oldVNode.key === newVNode.key) {
    // 调用 patch 函数进行更新
    patch(oldVNode, newVNode, container)
    // 更新索引 j，让其递增
    j++
    oldVNode = oldChildren[j]
    newVNode = newChildren[j]
  }
}

当 while 循环终止时，索引 j 的值为 1。这样，我们就完成了对前置节点的更新，如图所示：接下来，我们需要处理相同的后置节点。由于新旧两组子节点的数量可能不同，所以我们需要两个索引 newEnd 和 oldEnd，分别指向新旧两组子节点的最后一个节点，如图所示：然后，再开启一个 while 循环，并从后向前遍历这两组子节点，直到遇到 key 值不同的节点为止：

function patchKeyedChildren(n1, n2, container) {
  const newChildren = n2.children
  const oldChildren = n1.children
  // 更新相同的前置节点
  let j = 0
  let oldVNode = oldChildren[j]
  let newVNode = newChildren[j]
  while (oldVNode.key === newVNode.key) {
    patch(oldVNode, newVNode, container)
    j++
    oldVNode = oldChildren[j]
    newVNode = newChildren[j]
  }

  // 更新相同的后置节点
  // 索引 oldEnd 指向旧的一组子节点的最后一个节点
  let oldEnd = oldChildren.length - 1
  // 索引 newEnd 指向新的一组子节点的最后一个节点
  let newEnd = newChildren.length - 1

  oldVNode = oldChildren[oldEnd]
  newVNode = newChildren[newEnd]

  // while 循环从后向前遍历，直到遇到拥有不同 key 值的节点为止
  while (oldVNode.key === newVNode.key) {
    // 调用 patch 函数进行更新
    patch(oldVNode, newVNode, container)
    // 递减 oldEnd 和 nextEnd
    oldEnd--
    newEnd--
    oldVNode = oldChildren[oldEnd]
    newVNode = newChildren[newEnd]
  }
}

处理后置节点的方式与处理前置节点一样，在 while 循环内，需要调用 patch 函数进行打补丁，然后递减两个索引 oldEnd、newEnd 的值，处理后如图所示：上图显示，处理完相同的前置和后置节点后，旧子节点组已全部处理，而新子节点组仍有一个未处理的节点 p-4。实际上，节点 p-4 是新增节点。怎么得出节点 p-4 是新增节点结论的呢？我们需要观察索引 j、newEnd 和 oldEnd 之间的关系：

1. oldEnd < j 成立：说明在预处理过程中，所有旧子节点都处理完毕了。
2. newEnd >= j 成立：说明在预处理过后，在新的一组子节点中，仍然有未被处理的节点，而这些遗留的节点将被视作新增节点。

如果上述两个条件同时成立，说明在新的一组子节点中，存在遗留节点，且这些节点都是新增节点。因此我们需要将它们挂载到正确的位置，如图所示：在新子节点组中，需要将索引值处于 j 和 newEnd 之间的所有节点作为新子节点挂载。为了将这些节点挂载到正确的位置，我们需要找到正确的锚点元素。观察上图我们可以知道新增节点应该挂载在节点 p-2 对应的真实 DOM 前面。因此，节点 p-2 对应的真实 DOM 节点就是锚点元素：

function patchKeyedChildren(n1, n2, container) {
  const newChildren = n2.children
  const oldChildren = n1.children
  // 更新相同的前置节点
  // 省略部分代码

  // 更新相同的后置节点
  // 省略部分代码

  // 预处理完毕后，如果满足如下条件，则说明从 j --> newEnd 之间的节点应作为新节点插入
  if (j > oldEnd && j <= newEnd) {
    // 锚点的索引
    const anchorIndex = newEnd + 1
    // 锚点元素
    const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
    // 采用 while 循环，调用 patch 函数逐个挂载新增节点
    while (j <= newEnd) {
      patch(null, newChildren[j++], container, anchor)
    }
  }
}

上述代码，首先计算锚点的索引值（即 anchorIndex） 为 newEnd + 1。如果小于新的一组子节点的数量，则说明锚点元素在新的一组子节点中，所以直接使 newChildren[anchorIndex].el 作为锚点元素。否则说明索引 newEnd 对应的节点已经是尾部节点了，这时无须提供锚点元素。有了 锚点元素之后，我们开启了一个 while 循环，用来遍历索引 j 和索引 newEnd 之间的节点，并调用 patch 函数挂载它们。

我们接下来看看删除节点的情况：我们同样使用索引 j、oldEnd 和 newEnd 进行标记，如图所示：接着，对相同的前置节点进行预处理，处理后的状态如图：然后，对相同的后置节点进行预处理，处理后的状态如图：当前置和后置节点全处理完了，还遗留一个节点 p-2，这说明，应该卸载节点 p-2。实际情况可能会有多个遗留元素，如图：我们需要卸载索引 j 和 oldEnd 之间的所有节点，具体实现如下：

function patchKeyedChildren(n1, n2, container) {
  const newChildren = n2.children
  const oldChildren = n1.children
  // 更新相同的前置节点
  // 省略部分代码

  // 更新相同的后置节点
  // 省略部分代码

  if (j > oldEnd && j <= newEnd) {
    // 省略部分代码
  } else if (j > newEnd && j <= oldEnd) {
    // j -> oldEnd 之间的节点应该被卸载
    while (j <= oldEnd) {
      unmount(oldChildren[j++])
    }
  }
}

在这段代码中，我们添加了一个 else...if 分支。当满足条件 j > newEnd && j <= oldEnd 时，我们启动一个 while 循环，并通过调用 unmount 函数，逐个卸载这些遗留节点。

11.2 判断是否需要进行 DOM 移动操作

上一节中，新旧两组子节点中总会有一组子节点全部被处理完毕。后续只需要简单的挂载和卸载节点即可，我们来看一下更复杂的情况：新节点组增加了一个节点 p-7，同时减少了一个节点 p-6。在这个例子中，只有 p-1 是相同的前置节点，而 p-5 是相同的后置节点。经过预处理后两组子节点的状态：可以看出，新旧节点组都有部分未处理节点。此时，我们需要进一步处理。所有的 Diff 算法，无论是简单的，双端的，还是本章介绍的快速 Diff 算法，都遵循同样的规则：判断是否有节点需要移动，以及应该如何移动，找出需要被添加或移除的节点。接下来我们的任务就是确定哪些节点需要移动，以及如何移动。在这种非理想的情况下，处理完相同的前置和后置节点后，索引 j、newEnd 和 oldEnd 不满足以下任何一个条件：

1. j > oldEnd && j <= newEnd
2. j > newEnd && j <= oldEnd

因此，我们需要添加一个新的else分支来处理这种情况：

function patchKeyedChildren(n1, n2, container) {
  const newChildren = n2.children
  const oldChildren = n1.children

  // 更新相同的前置节点和后置节点，代码省略

  if (j > oldEnd && j <= newEnd) {
    // 省略部分代码
  } else if (j > newEnd && j <= oldEnd) {
    // 省略部分代码
  } else {
    // 处理非理想情况的新else分支
  }
}

接下来我们将在这个 else 分支内编写后续的处理逻辑。首先，我们需要构造一个数组 source，长度等于新节点组在预处理后剩余未处理节点的数量，每个元素的初始值都是 -1：我们可以通过下面的代码完成 source 数组的构造：

if (j > oldEnd && j <= newEnd) {
  // 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
  // 省略部分代码
} else {
  // 构造 source 数组
  // 新的一组子节点中剩余未处理节点的数量
  const count = newEnd - j + 1
  const source = new Array(count)
  source.fill(-1)
}

source 数组后续将存储新节点组中的节点在旧节点组中的位置索引，后面我们将使用它计算出一个最长递增子序列，并用于协助完成 DOM 移动的操作。上图展示了填充 source 数组的过程，由于 source 数组存储的是新子节点在旧的一组子节点中的位置索引，所以有：

• 新的一组子节点中的节点 p-3 在旧的一组子节点中的索引为 2， 因此 source 数组的第一个元素值为 2。
• 新的一组子节点中的节点 p-4 在旧的一组子节点中的索引为 3， 因此 source 数组的第二个元素值为 3。
• 新的一组子节点中的节点 p-2 在旧的一组子节点中的索引为 1， 因此 source 数组的第三个元素值为 1。
• 新的一组子节点中的节点 p-7 比较特殊，因为在旧的一组子节点中没有与其 key 值相等的节点，所以 source 数组的第四个元素 值保留原来的 -1。

我们可以通过两层 for 循环来完成 source 数组的填充，外层循环遍历旧节点组，内层循环遍历新节点组：

if (j > oldEnd && j <= newEnd) {
  // 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
  // 省略部分代码
} else {
  const count = newEnd - j + 1
  const source = new Array(count)
  source.fill(-1)

  // oldStart 和 newStart 分别为起始索引，即 j
  const oldStart = j
  const newStart = j
  // 遍历旧的一组子节点
  for (let i = oldStart; i <= oldEnd; i++) {
    const oldVNode = oldChildren[i]
    // 遍历新的一组子节点
    for (let k = newStart; k <= newEnd; k++) {
      const newVNode = newChildren[k]
      // 找到拥有相同 key 值的可复用节点
      if (oldVNode.key === newVNode.key) {
        // 调用 patch 进行更新
        patch(oldVNode, newVNode, container)
        // 最后填充 source 数组
        source[k - newStart] = i
      }
    }
  }
}

注意，因为 source 数组的索引从 0 开始，而未处理节点的索引可能并不从 0 开始，所以在填充数组时，我们使用 k - newStart 作为数组的索引值。外层循环的变量 i 就是当前节点在旧节点组中的位置索引，因此直接将 i 的值赋给 source[k - newStart] 即可。上述代码中用于填充 source 数组的部分采用了双重循环，时间复杂度为 O(n^2)，n1 和 n2 分别代表新旧两组子节点的数量。当新旧两组子节点的数量较多时，这种方法可能会导致性能问题。为了优化性能，我们可以创建一个索引表来映射新子节点的 key 和位置索引，这样可以避免内嵌循环，降低时间复杂度至O(n)。

if (j > oldEnd && j <= newEnd) {
  // 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
  // 省略部分代码
} else {
  const count = newEnd - j + 1
  const source = new Array(count)
  source.fill(-1)

  // oldStart 和 newStart 分别为起始索引，即 j
  const oldStart = j
  const newStart = j
  // 构建索引表
  const keyIndex = {}
  for (let i = newStart; i <= newEnd; i++) {
    keyIndex[newChildren[i].key] = i
  }
  // 遍历旧的一组子节点中剩余未处理的节点
  for (let i = oldStart; i <= oldEnd; i++) {
    oldVNode = oldChildren[i]
    // 通过索引表快速找到新的一组子节点中具有相同 key 值的节点位置
    const k = keyIndex[oldVNode.key]

    if (typeof k !== 'undefined') {
      newVNode = newChildren[k]
      // 调用 patch 函数完成更新
      patch(oldVNode, newVNode, container)
      // 填充 source 数组
      source[k - newStart] = i
    } else {
      // 没找到
      unmount(oldVNode)
    }
  }
}

上述代码，我们首先建立了一个索引表 keyIndex，用来存储节点的 key 和节点位置索引之间的映射。然后在第一个 for 循环中遍历新的子节点并填充索引表。在第二个 for 循环中，我们遍历旧的子节点，并使用索引表快速找到新子节点中对应 key 的节点位置 k，如果 k 存在，就进行 patch 操作并填充 source 数组；如果 k 不存在，就卸载旧的节点。此外，我们还需要判断节点是否需要移动。快速 Diff 算法判断节点是否需要移动的方法与简单 Diff 算法类似：

if (j > oldEnd && j <= newEnd) {
  // 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
  // 省略部分代码
} else {
  // 构造 source 数组
  const count = newEnd - j + 1 // 新的一组子节点中剩余未处理节点的数量
  const source = new Array(count)
  source.fill(-1)

  const oldStart = j
  const newStart = j
  // 新增两个变量，moved 和 pos
  let moved = false
  let pos = 0

  const keyIndex = {}
  for (let i = newStart; i <= newEnd; i++) {
    keyIndex[newChildren[i].key] = i
  }
  for (let i = oldStart; i <= oldEnd; i++) {
    oldVNode = oldChildren[i]
    const k = keyIndex[oldVNode.key]

    if (typeof k !== 'undefined') {
      newVNode = newChildren[k]
      patch(oldVNode, newVNode, container)
      source[k - newStart] = i
      // 判断节点是否需要移动
      if (k < pos) {
        moved = true
      } else {
        pos = k
      }
    } else {
      unmount(oldVNode)
    }
  }
}

上述代码，我们新增了两个变量 moved 和 pos。前者的初始值为 false，代表是否需要移动节点，后者的初始值为 0，代表遍历旧的一组子节点的过程中遇到的最大索引值 k。如果在遍历过程中遇到的索引值呈现递增趋势，则说明不需要移动节点，反之则需要。所以在第二个for 循环内，我们通过比较变量 k 与变量 pos 的值来判断是否需要移动节点。除此之外，我们还需要一个数量标识，代表已经更新过的节点数量。我们知道，已经更新过的节点数量应该小于新的一组子节点中需要更新的节点数量。一旦前者超过后者，则说明有多余的节点，我们应该将它们卸载，如下面的代码所示：

if (j > oldEnd && j <= newEnd) {
  // 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
  // 省略部分代码
} else {
  // 构造 source 数组
  const count = newEnd - j + 1
  const source = new Array(count)
  source.fill(-1)

  const oldStart = j
  const newStart = j
  let moved = false
  let pos = 0
  const keyIndex = {}
  for (let i = newStart; i <= newEnd; i++) {
    keyIndex[newChildren[i].key] = i
  }
  // 新增 patched 变量，代表更新过的节点数量
  let patched = 0
  for (let i = oldStart; i <= oldEnd; i++) {
    oldVNode = oldChildren[i]
    // 如果更新过的节点数量小于等于需要更新的节点数量，则执行更新
    if (patched <= count) {
      const k = keyIndex[oldVNode.key]
      if (typeof k !== 'undefined') {
        newVNode = newChildren[k]
        patch(oldVNode, newVNode, container)
        // 每更新一个节点，都将 patched 变量 +1
        patched++
        source[k - newStart] = i
        if (k < pos) {
          moved = true
        } else {
          pos = k
        }
      } else {
        // 没找到
        unmount(oldVNode)
      }
    } else {
      // 如果更新过的节点数量大于需要更新的节点数量，则卸载多余的节点
      unmount(oldVNode)
    }
  }
}

上述代码，我们增加了 patched 变量，其初始值为 0，代表更新过的节点数量。接着，在第二个 for 循环中增加了判断 patched <= count，如果此条件成立，则正常执行更新，并且每次更新后都让变量 patched 自增；否则说明剩余的节点都是多余的，于是调用 unmount 函数将它们卸载。

11.3 如何移动元素

在上一节，我们实现了两个关键步骤：判断是否需要进行 DOM 移动操作，以及构建 source 数组。当变量 moved 为真时，表示需要进行 DOM 移动操作。source 数组则用于存储新子节点在旧子节点中的位置，这会帮助我们计算出一个最长递增子序列，以便进行DOM移动操作。以下代码示例展示了如何进行这种移动：

if (j > oldEnd && j <= newEnd) {
  // 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
  // 省略部分代码
} else {
  // 省略部分代码
  for(let i = oldStart; i <= oldEnd; i++) {
    // 省略部分代码
  }

  if (moved) {
    // 如果 moved 为真，则需要进行 DOM 移动操作
  }
}

在这段代码中，我们在 for 循环后增加了一个if条件判断。如果 moved 为真，则表示需要进行 DOM 移动操作，我们将在此 if 语句编写相关移动的逻辑。要进行 DOM 移动操作，我们首先需要计算 source 数组的最长递增子序列。我们先要搞清楚什么是一个序列的递增子序列。子序列中的元素在原序列中不一定连续。一个序列可能有很多个递增子序列，其中最长的那一个就称为最长递增子序列。举个例子，假设给定数值序列 [ 0, 8, 4, 12 ]，那么它的最长递增子序列就是 [0, 8,12]。当然，对于同一个数值序列来说，它的最长递增子序列可能有多个，例如 [0,4, 12] 也是本例的答案之一。例如，假设 source 数组为 [2, 3, 1, -1]。如图所示：这种情况下，最长递增子序列是 [2, 3]。然后，我们可以用如下的代码来求解这个子序列：

if (moved) {
  // 计算最长递增子序列
  const seq = lis(sources) // [ 0, 1 ]
}

这段代码中，我们使用了 lis 函数来计算最长递增子序列。这个函数接收 source 数组作为参数，并返回其中的最长递增子序列之一。值得注意的是，返回结果是最长递增子序列元素在 source 数组中的索引，所以没有返回 [2, 3]，。如图所示：有了最长递增子序列的索引信息后，我们可以开始重新对节点进行编号，如图所示：

在编号时，我们忽略了经过预处理的节点 p-1 和 p-5。重新编号是为了让子序列 seq 与新的索引值产生对应关系。最长递增子序列 seq 拥有一个非常重要的意义，以上例来说，子序列 seq 的值为 [0, 1]。它的含义是：在新的一组子节点中，重新编号后索引值为 0 和 1 的这两个节点在更新前后顺序没有发生变化。换句话说，重新编号后，在新的一组子节点中，节点 p-3 的索引为 0，节点 p-4 的索引为 1 不需要移动。所以节点 p-3 和 p-4 所对应的真实 DOM 不需要移动。只有节点 p-2 和 p-7 可能需要移动。为了完成节点的移动，我们还需要创建两个索引值 i 和 s：

• 用索引 i 指向新的一组子节点中的最后一个节点；
• 用索引 s 指向最长递增子序列中的最后一个元素。

接下来，我们将开启一个 for 循环，让变量 i 和 s 按照上图中箭头的方向移动，如下面的代码所示：

if (moved) {
  const seq = lis(sources)

  // s 指向最长递增子序列的最后一个元素
  let s = seq.length - 1
  // i 指向新的一组子节点的最后一个元素
  let i = count - 1
  // for 循环使得 i 递减，即按照图中箭头的方向移动
  for (i; i >= 0; i--) {
    if (i !== seq[s]) {
      // 如果节点的索引 i 不等于 seq[s] 的值，说明该节点需要移动
    } else {
      // 当 i === seq[s] 时，说明该位置的节点不需要移动
      // 只需要让 s 指向下一个位置
      s--
    }
  }
}

上述代码，for 循环用于逐个访问新的节点组的节点，在 for 循环内，判断条件 i !== seq[s]，如果节点的索引 i 不等于 seq[s] 的值，则说明该节点对应的真实 DOM 需要移动，否则说明当前访问的节点不需要移动。按照上述思路执行更新。初始时索引 i 指向节点 p-7。由于节点 p-7对应的 source 数组中相同位置的元素值为 -1，所以我们应该将节点 p-7 作为全新的节点进行挂载，如下面的代码所示：

if (moved) {
  const seq = lis(sources)

  // s 指向最长递增子序列的最后一个元素
  let s = seq.length - 1
  // i 指向新的一组子节点的最后一个元素
  let i = count - 1
  // for 循环使得 i 递减，即按照图 11-24 中箭头的方向移动
  for (i; i >= 0; i--) {
    if (source[i] === -1) {
      // 说明索引为 i 的节点是全新的节点，应该将其挂载
      // 该节点在新 children 中的真实位置索引
      const pos = i + newStart
      const newVNode = newChildren[pos]
      // 该节点的下一个节点的位置索引
      const nextPos = pos + 1
      // 锚点
      const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
      // 挂载
      patch(null, newVNode, container, anchor)
    } else if (i !== seq[s]) {
      // 如果节点的索引 i 不等于 seq[s] 的值，说明该节点需要移动
    } else {
      // 当 i === seq[s] 时，说明该位置的节点不需要移动
      // 只需要让 s 指向下一个位置
      s--
    }
  }
}

上述代码，如果 source[i] 的值为 -1，则说明索引为 i 的节点是全新的节点，于是我们调用patch 函数将其挂载到容器中。这里需要注意的是，由于索引 i 是重新编号后的，因此为了得到真实索引值，我们需要计算表达式 i + newStart 的值。

新节点创建完毕后，for 循环已经执行了一次，此时索引 i 向上移动一步，指向了节点 p-2，如图所示：接着，进行下一轮 for 循环，步骤如下：

1. source[i] 是否等于 -1？很明显，此时索引 i 的值为 2，source[2] 的值等于 1，因此节点 p-2 不是全新的节点，不需要挂载它，进行下一步的判断。
2. i !== seq[s] 是否成立？此时索引 i 的值为 2，索引 s 的值为 1。因此 2!== seq[1] 成立，节点 p-2 所对应的真实 DOM 需要移动。

我们知道了节点 p-2 所对应的真实 DOM 应该移动。实现代码如下：

if (moved) {
  const seq = lis(sources)

  // s 指向最长递增子序列的最后一个元素
  let s = seq.length - 1
  let i = count - 1
  for (i; i >= 0; i--) {
    if (source[i] === -1) {
      // 省略部分代码
    } else if (i !== seq[s]) {
      // 说明该节点需要移动
      // 该节点在新的一组子节点中的真实位置索引
      const pos = i + newStart
      const newVNode = newChildren[pos]
      // 该节点的下一个节点的位置索引
      const nextPos = pos + 1
      // 锚点
      const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
      // 移动
      insert(newVNode.el, container, anchor)
    } else {
      // 当 i === seq[s] 时，说明该位置的节点不需要移动
      // 并让 s 指向下一个位置
      s--
    }
  }
}

移动节点的实现思路类似于挂载全新的节点。不同点在于，移动节点是通过 insert 函数来完成的。接着，进行下一轮的循环。此时索引 i 指向节点 p-4，如图所示：更新过程仍然分为三个步骤：

1. 判断表达式 source[i] 的值是否等于 -1？很明显，此时索引 i 的值为1，表达式 source[1] 的值等于 3，条件不成立。所以节点 p-4 不是全新的节点，不需要挂载它。接着进行下一步判断。
2. 判断表达式 i !== seq[s] 是否成立？此时索引 i 的值为 1，索引 s 的值为 1。这时表达式 1 === seq[1] 为真，所以条件 i !== seq[s] 也不成立。
3. 由于第一步和第二步中的条件都不成立，所以代码会执行最终的 else 分支。这意味着，节点 p-4 所对应的真实 DOM 不需要移动，但我们仍然需要让索引 s 的值递减，即 s--。

经过三步判断之后，我们得出结论：节点 p-4 不需要移动。于是进行下一轮循环，此时的状态如图：此时索引 i 指向节点 p-3。我们继续进行三个步骤的判断：

1. 判断表达式 source[i] 的值是否等于 -1？很明显，此时索引 i 的值为 0，表达式 source[0] 的值等于 2，所以节点 p-3 不是全新的节点，不需要挂载它，接着进行下一步判断。
2. 判断表达式 i !== seq[s] 是否成立？此时索引 i 的值为 0，索引 s 的值也为 0。这时表达式 0 === seq[0] 为真，因此条件也不成立，最终将执行 else 分支的代码，也就是第三步。
3. 到了这里，意味着节点 p-3 所对应的真实 DOM 也不需要移动。

在这一轮更新完成之后，循环将会停止，更新完成。

如下是用于求解给定序列的最长递增子序列的代码，取自 Vue.js 3：

function getSequence(arr) {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      while (u < v) {
        c = ((u + v) / 2) | 0
        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
}

11.4 总结

快速 Diff 算法在实测中性能最优。它借鉴了文本 Diff 中的预处理思路，先处理新旧两组子节点中相同的前置节点和相同的后置节点。当前置节点和后置节点全部处理完毕后，如果无法简单地通过挂载新节点或者卸载已经不存在的节点来完成更新，则需要根据节点的索引关系，构造出一个最长递增子序列。最长递增子序列所指向的节点即为不需要移动的节点。