快速 Diff 算法

本篇文章我们将讨论第三种用于比较新旧两组子节点的方式:快速 Diff 算法。该算法的实测速度非常快,最早应用与 iviinferno 这两个框架,vue.js 3 借鉴并扩展了它。

关于框架对比可以查看下面这个网站。

网站:https://krausest.github.io/js-framework-benchmark/current.html
github:https://github.com/krausest/js-framework-benchmark

在 DOM 操作的各个方面,iviinferno 所采用的快速 Diff 算法的性能都要优于 vue.js 2 所采用的双端 Diff 算法。既然快速 Diff 算法如此高效,我们就有必要了解它的思路。接下来,我们就着重讨论快速 Diff 算法的实现原理。

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

不同于简单 Diff 算法和双端 Diff 算法,快速 Diff 算法包含预处理步骤,这其实是借鉴了纯文本 Diff 算法的思路。在纯文本 Diff 算法中,存在对两段文本进行预处理的过程。例如,在对两段文本进行 Diff 之前,可以先对它进行全等比较。

if (text1 === text2) return
js

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

TEXT1: I use vue for app development
TEXT2: I use react for app development
js

通过肉眼可以很容易发现,这两段文本的头部和尾部分别一段相同的内容。对于内容相同的问题,是不需要进行核心 Diff 操作的。因此,对于 TEXT1TEXT2 来说,真正需要进行 Diff 操作的部分是:

TEXT1: vue
TEXT2: react
js

这实际上是简化问题的一种方式。这么做的好处是,在特定情况下我们能够轻松地判断文本的插入和删除。例如下面这两个字符串:

TEXT1: I like you
TEXT2: I like you too
js

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

TEXT1: 
TEXT2: too
js

可以看到,经过预处理,TEXT1 的内容为空。这说明 TEXT2TEXT1 的基础上增加了字符串 too。相反,我们还可以将这两段文本的位置互换:

TEXT1: I like you too
TEXT2: I like you
js

这两端文本降火预处理后讲变成:

TEXT1: too
TEXT2: 
js

由此可知,TEXT2 是在 TEXT1 的基础上删除了字符串 too

快速 Diff 算法借鉴了纯文本 Diff 算法中预处理的步骤。以下图为例:

quick_diff01.png

对于相同的前置节点和后置节点,由于它们在新旧两组子节点中的相对位置不变,所以我们无须移动它们,但仍然需要在它们之前打补丁。

对于前置节点,我们可以建议索引 j,其初始值为 0,用来指向两组子节点的开头。

quick_diff02.png

然后开启一个 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]
  }
}
js

在上面这段代码中,我们使用 while 循环查找所有相同的前置节点,并调用 patch 函数进行打补丁,直到遇到 key 值不同的节点为止。这样,我们就完成了对前置节点的更新。在这一步更新操作后,新旧两组子节点的状态如图所示:

quick_diff03.png

这里需要注意的是,当 while 循环终止时,索引 j 的值为 1。接下来,我们需要处理相同的后置节点。由于两组新旧子节点的数量可能不同,所以我们需要两个索引 newEndoldEnd,分别指向新旧两组子节点中的最后一个节点。

quick_diff04.png

然后,在开启一个 while 循环,并从后向前遍历这两组子节点,知道遇到 key 值不同的节点为止。

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]
  }

  // 更新相同的后置节点
  // 索引 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 和 newEnd
    oldEnd--
    newEnd--
    oldVNode = oldChildren[oldEnd]
    newVNode = newChildren[newEnd]
  }
}
js

与处理相同的前置节点一样,在 while 循环内,需要调用 patch 函数进行打补丁,然后递减两个索引 oldEndnewEnd 的值。在这一步更新操作之后,新旧两组子节点的状态如图所示:

quick_diff05.png

由图可知,当相同的前置节点和后置节点被处理完毕后,旧的一组子节点已经全部被处理了,而在新的一组子节点中,还遗留了一个未被处理的节点 p-4。节点 p-4 是一个新增节点。

  • 条件一:oldEnd < j 成立,说明在预处理过程中,所有旧节点都处理完毕了;
  • 条件二:newEnd >= j 成立,说明在预处理过程中,在新的一组子节点中,仍然有未被处理的节点,而这些遗留的节点都被视作新增节点。

我们需要把这些遗留的节点挂载到正确的位置。

在新的一组子节点中,索引值处于 j 和 newEnd 之间的任何节点都需要作为新的子节点进行挂载。那么,应该怎样将这些节点挂载到正确位置呢?这就要求我们必须找到正确的锚点元素。观察图中新的一组子节点可知,新增节点应该挂载到节点 p-2 所对应的真实 DOM 前面。所以,节点 p-2 对应的真实 DOM 节点就是挂载操作的锚点元素。有了这些信息,我们就可以给出具体的代码实现。

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

  // 更新相同的后置节点
	// ...
  
  // 预处理完毕后,如果满足如下条件,则说明 j --> nextEnd 之间的节点应作为新节点插入
  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)
    }
  }
}
js

上面的案例展示了新增节点的情况,我们再来看删除节点的情况。

quick_diff06.png

在这个例子中:新旧两组子节点的顺序如下:

  • 旧的一组子节点:p-1、p-2、p-3
  • 新的一组子节点:p-1、p-3

我们同样使用索引 j、oldEndnewEnd 进行标记。

quick_diff07.png

接着,对相同的前置节点进行预处理,处理后的状态如图所示:

quick_diff08.png

然后,对相同的后置节点进行预处理,处理后的状态如图所示:

quick_diff09.png

由上图可知,当相同的前置节点和后置节点全部都被处理完毕后,新的一组子节点已经全部被处理完毕了,而旧的一组子节点中遗留了一个节点 p-2。这说明,应该卸载 p-2。实际上,遗留的节点可能有多个。

索引 j 和索引 oldEnd 之间的任何节点都应该被卸载。

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

  // 更新相同的后置节点
	// ...

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

在上面这段代码中,我们新增了一个 else...if 分支。当满足条件 j > newEnd && j <= oldEnd 时,则开启一个 while 循环,并调用 unmount 函数逐个卸载这些遗留节点。

判断是否需要移动 DOM

上一节中,我们讲解了快速 Diff 算法的预处理过程,即处理相同的前置节点和后置节点。但是,上一节给出的例子比较理想化,当处理完相同的前置节点或后置节点后,新旧两组子节点中总会有一组子节点全部被处理完毕。在这种情况下,只需要简单地挂载、卸载节点即可。但有时情况会比较复杂。

quick_diff10.png

从上图可以看到,与旧的一组子节点相比,新的一组节点多出了一个新节点 p-7,少了一个节点 p-6。这个例子并不向上一节给出的例子那样理想化,我们无法简单地通过与处理过程完成更新。在这个例子中,相同的前置节点只有 p-1,相同的后置节点只有 p-5。

下面是预处理后两组子节点的状态。

quick_diff11.png

可以看到,经过预处理后,无论是新的一组子节点,还是旧的一组子节点,都有部分节点未经处理。这时就需要我们进一步处理。
无论是简单 Diff 算法,还是双端 Diff 算法,或者这次介绍的快速 Diff 算法,它们都遵循同样的处理规则:

  • 判断是否有节点需要移动,以及应该如何移动;
  • 找出那些需要被添加或移除的节点。

所以接下来我们的任务就是,判断哪些节点需要移动,以及应该如何移动。观察上图可知,在这种非理想的情况下,当相同的前置节点和后置节点被处理完毕后,索引 j、newEndoldEnd 不满足下面两个条件中的任何一个:

  • j > oldEnd && j <= newEnd
  • 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 分支处理非理想情况
  }
}
js

后续的处理逻辑我们将会编写在这个 else 分支内。我们需要构造一个数组 source,它的长度等于新的一组子节点中在经过预处理之后剩余未处理节点的数量,并且 source 中每个元素的初始值都是 -1。

quick_diff12.png

我们可以通过下面的代码完成对 source 数组的改造。

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 分支处理非理想情况
    // 新的一组子节点中剩余未处理节点的数量
    const count = newEnd - j + 1
    const source = new Array(count)
    source.fill(-1)
  }
}
js

如代码所示。首先,我们需要计算新的一组子节点中剩余未处理节点的数量,即 newEnd - j + 1,然后创建一个长度与之相同的数组 source ,最后使用 fill 函数完成数组填充。数组 source 用来存储新的一组子节点中的节点在旧的一组子节点中的位置索引,后面将会使用它计算出一个最长递增子序列,并用于辅助完成 DOM 移动的操作。

quick_diff13.png

上图展示了填充数组的过程。由于 source 数组存储的是新子节点在旧的一组子节点中的位置索引,所以:

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

我们可以通过两层 for 循环来完成 source 数组的填充工作,外层循环用于遍历旧的一组节点,内层循环用于遍历新的一组子节点。

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 分支处理非理想情况
    // 新的一组子节点中剩余未处理节点的数量
    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
        }
      }
    }
  }
}
js

这里需要注意的是,由于数组 source 的索引是从 0 开始的,而未处理节点的索引未必从 0 开始,所以在填充数组时需要使用表达式 k - newStart 的值作为数组的索引值。外层循环的变量 i 就是当前节点在旧的一组子节点中的位置索引,因此直接将变量 i 的值赋值给 souce[k - newStart] 即可。

现在,source 数组已经填充完毕,我们后面会用到它。在进一步讲解前,我们需要思考一下上面那段用于填充 source 数组的代码存在怎样的问题。这段代码中我们采用了两层嵌套的循环,其时间复杂度为 O(n1 * n2),其中 n1n2 为新旧两组子节点的数量,我们也可以使用 O(n^2) 来表示。当新旧两组子节点的数量较多时,两层嵌套的循环就会带来性能问题。出于优化的目的,我们可以为新的一组子节点构建一张索引表,用来存储节点的 key 和节点位置索引之间的映射。

quick_diff14.png

有了索引表,我们就可以利用它快速地填充 source 数组。

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 分支处理非理想情况
    // 新的一组子节点中剩余未处理节点的数量
    const count = newEnd - j + 1
    const source = new Array(count)
    source.fill(-1)
   
    // oldStart 和 newStart 分别为起始索引,即 j
    const oldStart = j
    const newStart = j
    // 构建索引表
    const keyIndx = {}
    for (let i = newStart; i <= newEnd; i++) {
      keyIndx[newChildren[i].key] = i
    }
    // 遍历旧的一组子节点剩余未处理的节点为止
    for (let i = oldStart; i <= oldEnd; i++) {
      const oldVNode = oldChildren[i]

      // 通过索引表快速找到新的一组子节点中具有相同 key 值的节点位置
      const k = keyIndx[oldVNode.key]

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

在上面这段代码中,同样使用了两个 for 循环,不过它们不再是嵌套的关系,所以能够将代码的时间复杂度降至 O(n) 。其中,第一个 for 循环用来构建索引表,索引表存储的是节点的 key 值与节点在新的一组子节点中位置索引之间的映射,第二个 for 循环用来遍历旧的一组子节点。可以看到,我们拿旧子节点的 key 值去索引表 keyIndex 中查找该节点在新的一组子节点中的位置,并将查找结果存储到变量 k 中。如果 k 存在,说明该节点是可复用的,所以我们调用 patch 函数进行打补丁,并填充 source 数组。否则说明该节点已经不存在与新的一组子节点中,这时我们需要调用 unmount 函数卸载它。

上述流程执行完毕后,source 数组已经填充完毕了。接下来我们应该思考的是,如果判断节点是否需要移动。实际上,快速 Diff 算法判断节点是否需要移动的方法与简单 Diff 算法类似。

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 分支处理非理想情况
    // 新的一组子节点中剩余未处理节点的数量
    const count = newEnd - j + 1
    const source = new Array(count)
    source.fill(-1)
    
    // oldStart 和 newStart 分别为起始索引,即 j
    const oldStart = j
    const newStart = j
    // 新增两个变量,moved 和 pos
    let moved = false
    let pos = 0
    // 构建索引表
    const keyIndx = {}
    for (let i = newStart; i <= newEnd; i++) {
      keyIndx[newChildren[i].key] = i
    }
    // 遍历旧的一组子节点剩余未处理的节点为止
    for (let i = oldStart; i <= oldEnd; i++) {
      const oldVNode = oldChildren[i]

      // 通过索引表快速找到新的一组子节点中具有相同 key 值的节点位置
      const k = keyIndx[oldVNode.key]

      if (typeof k !== 'undefined') {
        newVNode = newChildren[k]
        // 调用 patch 进行更新
        patch(oldVNode, newVNode, container)
        // 最后填充 source 数组
        source[k - newStart] = i
        // 判断节点是否需要移动
        if (k < pos) {
          moved = true
        } else {
          pos = k
        }
      } else {
        // 没找到
        unmount(oldVNode)
      }
    }
  }
}
js

我们新增了两个变量 movedpos。前者的初始值为 false,代表是否需要移动节点,后者的初始值为 0,代表遍历旧的一组子节点中的过程中遇到的最大索引值 k。我们在编写简单 diff 算法时提到,如果在遍历过程中遇到的索引值呈现递增趋势,则说明不需要移动节点,反之则需要。所以在第二个 for 循环内,我们通过比较变量 k 与变量 pos 的值来判断是否需要移动节点。

除此之外,我们还需要一个数量标识,代表已经更新过的节点数量。我们知道,已经更新过的节点数量应该小于新的一组子节点中需要更新的节点数量。一旦前者超过后者,则说明有多余的节点,我们应该将它们卸载。

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 分支处理非理想情况
    // 新的一组子节点中剩余未处理节点的数量
    const count = newEnd - j + 1
    const source = new Array(count)
    source.fill(-1)
    
    // oldStart 和 newStart 分别为起始索引,即 j
    const oldStart = j
    const newStart = j
    // 新增两个变量,moved 和 pos
    let moved = false
    let pos = 0
    // 构建索引表
    const keyIndx = {}
    for (let i = newStart; i <= newEnd; i++) {
      keyIndx[newChildren[i].key] = i
    }
    // 新增 patched 变量,代表更新过的节点数量
    let patched = 0
    // 遍历旧的一组子节点剩余未处理的节点为止
    for (let i = oldStart; i <= oldEnd; i++) {
      const oldVNode = oldChildren[i]

      if (patched <= count) {
        // 通过索引表快速找到新的一组子节点中具有相同 key 值的节点位置
        const k = keyIndx[oldVNode.key]

        if (typeof k !== 'undefined') {
          newVNode = newChildren[k]
          // 调用 patch 进行更新
          patch(oldVNode, newVNode, container)
          // 每更新一个节点,将 patched 变量 +1
          patched++
          // 最后填充 source 数组
          source[k - newStart] = i
          // 判断节点是否需要移动
          if (k < pos) {
            moved = true
          } else {
            pos = k
          }
        } else {
          // 没找到
          unmount(oldVNode)
        }
      } else {
        // 如果更新过的节点数量大于需要更新的节点数量,卸载多余的节点
        unmount(oldVNode)
      }
    }
  }
}
js

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

现在,我们通过判断变量 moved 的值,已经能够知道是否需要移动节点,同时也处理了很多边界条件。接下来我们讨论如何移动节点。

如何移动元素

我们已经实现了两个目标:

  • 判断是否需要进行 DOM 移动操作。我们创建了变量 moved 作为标识,当它的值为 true 时,说明需要进行 DOM 移动操作。
  • 构建 source 数组。该数组的长度等于新的的一组子节点去掉相同的前置/后置节点后,升序未处理节点的数量。source 数组中存在这新的一组子节点中的节点在旧的一组子节点中的位置。后面,我们会根据 source 数组计算出一个最长递增子序列,用于 DOM 移动操作。

接下来,我们讨论如何进行 DOM 移动操作。

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 {
    // ...
    
    if (moved) {
      // 如果 moved 为真,需要进行 DOM 移动操作
    }
  }
}
js

我们在 for 循环后增加了一个 if 判断分支。如果变量 moved 的值为 true,则说明需要进行 DOM 移动操作,所以用于 DOM 移动操作的逻辑将编写在该 if 语句块内。

为了进行 DOM 移动操作,我们首先要根据 source 数组计算出它的最长递增子序列。source 数组仍然取用之前的例子。

quick_diff14.png

这个例子中,我们计算出 source 数组为 [2, 3, 1, -1]。那么,该数组的最长递增子序列是什么呢?

简单来说,给定一个数值序列,找到它的一个子序列,并且该子序列中的值是递增的,子序列中的元素在元序列中不一定连续。一个序列可能有多个递增子序列,其中最长的哪一个就称为最长递增子序列。

举个例子,假设给定数值序列 [0, 8, 4, 12],那么它的最长递增子序列就是 [0, 8, 12]。当然,对于同一个数值序列来说,它的最长递增子序列可能有多个,例如 [0, 4, 12] 也是答案之一。

理解什么是最长递增子序列后,接下来我们就可以求解 source 数组的最长递增子序列。

if (moved) {
  // 如果 moved 为真,需要进行 DOM 移动操作
  // 计算最长递增子序列
  const seq = lis(source) // [0, 1]
}
js

在这段代码中,我们使用 lis 函数计算一个数组的最长递增子序列。lis 函数接收 source 数组作为参数,并返回 source 数组的最长递增子序列。

lis 函数返回结果是最长递增子序列中的元素在 source 数组中的位置索引。

因为 source 数组的最长递增子序列是 [2, 3],其中元素 2 在该数组中的索引为 0,而数组 3 在该数组中的索引为 1,所以最终结果为 [0, 1]

有了最长递增子序列的索引信息后,下一步要重新对节点进行编号。

quick_diff15.png

观察上图,在编号时,我们忽略了经过预处理的节点 p-1p-5。所以,索引为 0 的节点是 p-2,而索引为 1 的节点时 p-3。重新编号是为了让子序列 seq 与新的索引值产生对应关系。以上例来说,子序列 seq 的值为 [0, 1] ,它的含义是:**在新的一组子节点中,重新编号后索引值为 0 和 1 的这两个节点在更新前后顺序没有发生变化。**换句话说,重新编号后,索引值为 0 和 1 的节点不需要移动。在新的一组子节点中,节点 p-3 索引为 0,节点 p-4 的索引为 1,所以节点 p-3p-4 所对应的真实 DOM 不需要移动。只有 p-2p-7 可能需要移动。

为了完成节点移动,我们还需要创建两个索引值 i 和 s。

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

quick_diff16.png

为了简化图示,我们去掉了旧的一组子节点以及无关的线条和变量。

if (moved) {
  // 如果 moved 为真,需要进行 DOM 移动操作
  // 计算最长递增子序列
  const seq = lis(source) // [0, 1]

  // 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--
    }
  }
}
js

其中,for 循环从后向前遍历,可以逐个访问新的一组子节点中的节点,这里的变量 i 就是节点的索引。在 for 循环内,判断条件 i !== seq[s],如果节点的索引 i 不等于 seq[s] 的值,则说明该节点对应的真实 DOM 需要移动,否则说明当前访问的节点不需要移动,这时需要递减 s。

接下来我们就按照上述思路执行更新。初始时索引指向节点 p-7。由于 p-7 对应的 source 数组中相同位置的元素值为 -1,所以我们应该将节点 p-7 作为全新的节点进行挂载。

// oldStart 和 newStart 分别为起始索引,即 j
const oldStart = j
const newStart = j

if (moved) {
  // 如果 moved 为真,需要进行 DOM 移动操作
  // 计算最长递增子序列
  const seq = lis(source) // [0, 1]

  // s 指向最长递增子序列的最后一个元素
  let s = seq.length - 1
  // i 指向新的一组子节点中的最后一个元素
  let i = count - 1
  // for 循环使 i 递减
  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--
    }
  }
}
js

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

新节点创建完毕后,for 循环已经执行一次,此时索引 i 向上移动一步,指向节点 p-2。

quick_diff17.png

接着,进行下一轮 for 循环。

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

第二步中,我们知道节点 p-2 所对应的真实 DOM 需要移动。

if (moved) {
    // 如果 moved 为真,需要进行 DOM 移动操作
    // 计算最长递增子序列
    const seq = lis(source) // [0, 1]

    // s 指向最长递增子序列的最后一个元素
    let s = seq.length - 1
    // i 指向新的一组子节点中的最后一个元素
    let i = count - 1
    // for 循环使 i 递减
    for (i; i >= 0; i--) {
      if (source[i] === -1) {
        // 说明索引为 i 的节点是全新的节点,执行挂载操作
        // 该节点在新的一组子节点中的真实位置索引
        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] 的值,说明该节点需要移动
        // 该节点在新的一组子节点中的真实位置索引
        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--
      }
    }
  }
js

移动节点的实现思路类似于挂载全新的节点。不同点在于,移动节点是通过 insert 函数来完成的。

接着进行下一轮的循环。此时索引 i 指向节点 p-4。

quick_diff18.png

更新过程仍然分为三个步骤。

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

节点 p-4 不需要移动,进行下一轮循环。

quick_diff19.png

由上图可知,此时索引 i 指向节点 p-3。我们继续进行三个步骤的判断。

  • 第一步:判断表达式 source[i] 的值是否等于 -1 ? 很明显,此时索引 i 的值为 0,表达式 source[1] 的值为 2,条件不成立。所以,节点 p-3 不是全新节点,不需要挂载。
  • 第二步:判断表达式 i !== seq[s] 是否成立?此时索引 i 的值为 0,索引 s 的值为 1\0,条件不成立。
  • 第三步:到了这里,这意味着节点 p-3 所对应的真实 DOM 也不需要移动。在这一轮更新完成之后,循环将会终止,更新完成。

以下是 Vue.js 3 求解给定序列的最长递增子序列的代码。

// https://github.com/yw0525/core/blob/main/packages/runtime-core/src/renderer.ts
// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr: number[]): number[] {
  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) >> 1
        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
}
js

总结

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

如果你想调试本篇文档案例,可以查看 notes 中仓库中的 books/Vue.js设计与实现/renderer 文件夹,运行 index.html 文件即可。

books/Vue.js设计与实现 目录结构如下:

.
├── browser
├── effect
├── reactivity
├── ref
├── renderer
├── utils
├── vue
│   ├── computed.js
│   ├── effect.js
│   ├── reactive.js
│   ├── ref.js
│   ├── renderer.js
│   ├── util.js
│   └── watch.js
└── README.md