Riact开发笔记之Diff算法篇

前言

Riact是最近自己做的一个类React框架，目前只支持Hook形式的开发（个人非常喜欢Hook形式的组件）。框架开发的目的主要是为了学习，对于核心的模块还是打算写几篇总结。虚拟DOM的设计和实现是整个框架的核心，其中又以虚拟DOM的Diff算法最麻烦，所以系列总结还是从这里开始着手。

概述

本文讨论的算法主要是带标记的列表之间的Diff算法（即带key的列表对比），整个树的逐层对比对于大多数同学来说都比较容易理解，这里也就不再讨论。

在Riact开始实现之初，笔者曾经采用过React的虚拟DOM Diff算法，但随着开发的进行，笔者也对对市面上常见框架做了调研和对比，最后发现在这个方向做得最好的应该是Inferno框架。

Inferno框架的虚拟DOM可以说优化到了极致，从编译阶段（定制化编译，对部分JSX进行静态编译）到对比阶段（Diff的节点类型对比直接使用位运算符进行操作）都比一般框架进行了大幅改进，包括在带标记的列表对比也不例外。

Inferno采用了一种基于最长上升子序列的方式算法进行比对，时间复杂度为$\mathrm{O}(n\log n)$，相比React和Vue的$\mathrm{O}(n)$，这种算法可以得到最优解，即能够使真实DOM操作达到最小化。

问题描述

下面我们来看一下该算法的具体实现过程。

假定我们有如下列表需要更新。

1
2
3

// 代码1
const L1 = ['a', 'b', 'c', 'd'];
const L2 = ['d', 'a', 'b', 'c'];

计算出的结果应该是对L1的操作，由于这里的数据量较小，我们可以一眼看出，只需要进行如下操作就能实现我们的目的。

移动d到a的前面。

这样，我们只需要对其进行一次操作即可，但事实是，如果我们进行下面的操作，也可以达到目的。

移动a到d的后面；
移动b到a的后面；
移动c到b的后面。

上述过程逐步执行，如第一步执行完之后，a已经到了d后面去了。

不难发现，这种情况下我们移动了三次，也许有同学会说怎么会有这么笨的算法，明明一次就行，非要三次。事实上，React就是这么干的，Vue虽然可以比较好地解决上述测试用例，但不少情况下也拿到的不是最优解（但它们计算出结果的速度更快）。

输入序列预处理

消除两端相同序列

在进入对比算法的关键过程之前，我们可以通过一些手段来降低关键算法部分的实际复杂度。

假如我们输入的序列如下。

1
2
3

// 代码2
const L1 = ['x', 'a', 'b', 'e', 'c', 'd', 'y'];
const L2 = ['x', 'd', 'a', 'b', 'c', 'y'];

我们注意到两个列表的两端都存在相同的部分，即序列头部的x和序列尾部的y，这种情况下我们没必要让它们进入到后续的对比阶段，因为这个两个序列的对比可以简化为如下所示。

1
2
3

// 代码3
const L1 = ['a', 'b', 'e', 'c', 'd'];
const L2 = ['d', 'a', 'b', 'c'];

所以算法的第一步，就是筛去两端相同的部分。

一个细节：trim掉了两个列表两端相同的节点，所有后续的操作都应该从头部被trim的位置开始，到尾部被trim的位置结束，而不应该新开数组。

删除旧的列表中的元素

在去除了两端相同元素之后，我们可以删掉新序列中不存在的旧序列元素。

这里可以通过一个Map来记录L2中元素的和下标的对应关系。

// 代码4
// 建立下标索引
const IM = new Map();
let i, len;
for (i = 0, len = L2.length; i < len; i++) {
  IM.set(L2[i], i);
}

然后再通过新序列中元素，来确认哪些是需要删除的元素。

// 代码5
// 删除新序列中不存在的旧序列元素
for (i = 0, len = L1.length; i < len; i++) {
  if (!IM.has(L1[i])) {
    // 删除L1[i]
  }
}

这样问题就会被进一步简化，两个列表的对比最终变成了一开始代码1中的样子。

接下来我们就可以进入正题了，这里我们需要先学习一个经典的动态规划问题及其解法，这就是最长上升子序列。

最长上升子序列

最长上升子序列的概念

在Inferno采用的Diff算法中，用到了经典的计算最长上升子序列（Longest Increasing Subsequence）的算法。

所谓的最长上升子序列，就是在一个序列中，求长度最长且顺序是升序的子序列。

假设有序列如下：

1 2	// 表1 // 1, 5, 2, 4, 6, 0, 7

那么其最长上升子序列就是

1 2	// 表2 // 1, 2, 4, 6, 7

如果对这个概念理解有问题的同学，可以去看一下参考3。

为什么要使用它

在学习能得出最优解的算法之前，我们必须先弄明白为什么要这么做，这既能帮助我们理解Diff算法，又反过来能帮助我们学习最长上升子序列。

其实对带标记列表的对比并计算操作结果的过程有点类似于计算其编辑距离的过程，但和一般的词汇的编辑距离（只有新增，删除，有的也有替换）不同，DOM中还有移动的操作，我们必须最大化复用当前已经存在的节点，并使尽量多的节点不被移动。

再加上对列表元素的操作过程实际上就是下标的进行操作，例如从['a', 'b', 'c', 'd']到['d', 'a', 'b', 'c']的过程其实就是：

移动下标为3的元素到下标为0的前面。

所以求出新序列中元素在旧序列中对应的下标的最长上升子序列，并保证在最长上升子序列中的元素不被移动，就能保证最多的元素可复用并不被移动了。

这句话可能有点绕，我们还是拿上面的例子讲解。

// 代码6
const L1 = ['a', 'b', 'c', 'd'];
const L2 = ['d', 'a', 'b', 'c'];
const IM = {
    d: 0,
    a: 1,
    b: 2,
    c: 3,
};
const IT = [ 3 ,  0 ,  1 ,  2 ]; // 新序列中元素在旧序列中对应的下标

IT就是在新序列中元素在旧序列中对应的下标，其中d在原数组中下标是3，a在原数组中的下标是0，以此类推。

IT可以直接在代码5的基础上修改得到，如下所示。

// 代码7
// 对代码5进行修改如下
const IT = new Array(L2.length).fill(-1); // 先填充为-1，等循环结束时还是-1的元素，则是新元素。
for (i = 0, len = L1.length; i < len; i++) {
  if (!IM.has(L1[i])) {
    // 删除L1[i]
  } else {
    IT[IM.get(L1[i])] = i;
  }
}

不难看出，IT的最长上升子序列是[0, 1, 2]，根据前文所述，只要保证旧序列中下标在这其中的元素不移动，就能使我们的操作最小化，也就是说['a', 'b', 'c']不移动，即可保证操作最小化，而事实正是如此。

算法思想

对这一步不太感兴趣的同学可以直接跳到后面移动和插入小节

了解了$LIS$的概念和为什么要求$LIS$之后，现在我们来看具体的算法思想。

对于给定的序列，我们将其进行遍历，并记录长度为$n$（$n \in \mathbb{N^*}$）的$LIS$的最后一个元素的最小值，将所有最小值组成的序列记为$M$，同时更新每一个元素作为当前已遍历序列的$LIS$中最后一个元素前一个元素的的下标，并该将下标组成的序列记为$L$。

这句话是我自己总结的，看起来很拗口（实际上也很拗口），但一步一步来，先放在这里，等这一小结结束的时候你可以再回来看几遍。

先来看$M$，长度为$n$的$LIS$最后一个元素的最小值所组成的序列。

假设我们有如下序列。

1
2
3

// 表3
// idx: [0, 1, 2,  3, 4,  5, 6,  7, 8, 9,10, 11,12, 13,14, 15]; // 对应的下标
// seq: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; // 原序列

遍历序列，第一个元素是0，此时长度为1的最长子序列就是[0]，记录其下标为0，这样$M$的值就如下就是[-1, 0]，长度为0（$M$中下标为0的元素）的最长子序列不存在或没有意义，我们将其记为-1，长度为1（$M$中下标为1的$LIS$元素）。

再来看$L$，$L$的第$i$个元素记录的是原序列中第$i$个元素为结尾的$LIS$的上一个元素的下标，以0为结尾的最长子序列是[0]，其上一个元素的下标不存在，所以记为-1，此时的结果如下所示。

// 表4
// idx: [0, 1, 2,  3, 4,  5, 6,  7, 8, 9,10, 11,12, 13,14, 15]; // 对应的下标
// seq: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; // 原序列
// L:  [-1]
// M:  [-1,
//       0]

接着扫描到了8，通过查找$M$，此时的$LIS$是[0]，那8进入以后最长上升子序列应该是[0, 8]，所以$M$应该是[-1, 0, 1]（注意$M$是记录下标的序列）。

而$L$则进一步更新，将8的上一个元素的下标记录下来，即[-1, 0]

// 表5
// idx: [0, 1, 2,  3, 4,  5, 6,  7, 8, 9,10, 11,12, 13,14, 15]; // 对应的下标
// seq: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; // 原序列
// L:  [-1, 0]
// M:  [-1,
//       0,
//       1]

接下来扫描4，通过查找$M$，我们得知了此时的$LIS$是[0, 8]，而由于当前元素是4，比8小，为了保证$M$的特性（其只存储最小值），所以此时的4可以替换8，$M$变成了[-1, 0, 2]，而从$M$中可以看出，$L$中对应的前继元素还是0。

所以此时的状态如下。

// 表6
// idx: [0, 1, 2,  3, 4,  5, 6,  7, 8, 9,10, 11,12, 13,14, 15]; // 对应的下标
// seq: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; // 原序列
// L:  [-1, 0, 0]
// M:  [-1,
//       0,
//       2]

接下来扫描12，通过查找$M$可知此时的$LIS$是[0, 4]，当前的元素是12，大于4，所以可以将其下标直接接到尾部，即[-1, 0, 2, 3]，查阅此时的$M$可知3的前继是2，所以$L$应为[-1, 0, 0, 2]。

状态如下。

// 表7
// idx: [0, 1, 2,  3, 4,  5, 6,  7, 8, 9,10, 11,12, 13,14, 15]; // 对应的下标
// seq: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; // 原序列
// L:  [-1, 0, 0, 2]
// M:  [-1,
//       0,
//       2,
//       3]

这样一步一步扫描过去，最后可以得到整个$L$和$M$的结果如下。

// 表8
// idx: [0, 1, 2,  3, 4,  5, 6,  7, 8, 9,10, 11,12, 13,14, 15]; // 对应的下标
// seq: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; // 原序列
// L:  [-1, 0, 0,  2, 0,  4, 4,  6, 0, 6, 8,  9, 8,  9,12, 13];
// M:  [-1,
//       0,
//       8,
//       12,
//       14,
//       13,
//       15]

现在我们知道了最终整个序列的$LIS$，长度是6（M.length - 1），我们从$M$的最后一个元素开始找起，顺着$L$，向前回溯，就得到了最后的结果。

整个回溯过程如下。

// 表9
// idx: [0, 1, 2,  3, 4,  5, 6,  7, 8, 9,10, 11,12, 13,14, 15]; // 对应的小标
// seq: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]; // 原序列
// L:  [-1, 0, 0, 2,  0,  4, 4,  6, 0, 6, 8,  9, 8,  9,12, 13];
// M:  [-1,
//       0,
//       8,
//       12,
//       14,
//       13,
//       15]

// S用于记录结果，其长度是6，暂时记为[empty * 6]
// 我们先取M的最后一个元素作为回溯L的出发点，M的最后一个元素是15
// 找到seq中下标为15的元素，即15，将其替换S[5]
// 此时S为[empty * 5, 15]，同时发现L[15]等于13

// 找到seq中下标为13的元素，即11，将其替换S[4]
// 此时S为[empty * 4, 11, 15]，同时发现L[11]等于9

// 找到seq中下标为 9的元素，即 9，将其替换S[3]
// 此时S为[empty * 3, 9, 11, 15]，同时发现L[9]等于6

// 找到seq中下标为 6的元素，即 6，将其替换S[2]
// 此时S为[empty * 2, 6, 9, 11, 15]，同时发现L[6]等于4

// 找到seq中下标为 4的元素，即 2，将其替换S[1]
// 此时S为[empty, 2, 6, 9, 11, 15]，同时发现L[2]等于0

// 找到seq中下标为 0的元素，即 0，将其替换S[0]
// 此时S为[0, 2, 6, 9, 11, 15]，同时发现L[0]等于-1

// 回溯结束，最终的得到的LIS为[0, 2, 6, 9, 11, 15]

整个LIS算法的过程就是这样，如果对此理解还有问题，可以先循环观察几遍下面的动图，或者直接查看wikipedia这样有助于理解。

为了方便理解，图中记录的是当前长度为$n$的所有最长子序列。

图1. 最长上升子序列算法过程

代码实现

以下是代码是$LIS$的TypeScript实现，注意下面的for循环中，我们略过了所有负数的处理（为什么会出现负数我们后续会讲到）。

// 代码8
/**
 * calculate longest increasing subsequence (only for positive numbers)
 * @param arr array of number
 */
export const calcLis = function(arr: Array<number>): Array<number> {
  const M: Array<number> = [-1];
  const P: Array<number> = [];
  const S: Array<number> = [];
  let i: number;
  let left: number;
  let right: number;
  let mid: number;
  let len: number;
  for (i = 0, len = arr.length; i < len; i++) {
    // skip negative numbers
    if (arr[i] < 0) {
      continue;
    }
    left = 1;
    right = M.length;
    while (left < right) {
      mid = Math.floor((left + right) / 2);
      if (arr[M[mid]] < arr[i]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    M[left] = i;
    P[i] = M[left - 1];
  }

  len = M.length - 1;
  i = M[len];
  while (i !== -1) {
    S[len-- - 1] = arr[i];
    i = P[i];
  }
  return S;
};

时间复杂度分析

显然我们需要对整个序列进行遍历，而为了保证$M$中存储的永远是以当前元素为$LIS$结尾的最小值，我们每次都需要对$M$进行有序序列的查询（和替换，或者在尾部追加的）操作，这里我们使用时间复杂度为$\mathrm{O}(\log n)$的二分查找，所以整个算法最终的时间复杂度为$\mathrm{O}(n\log n)$。

移动和插入

移动

计算$LIS$的目的就是为了移动操作，因为我们的最终目的就是为了实现在$LIS$中的元素全部都可以不被移动，以达到最小移动操作的结果。

但是如何实现呢？现在让我们再次回到代码1。

// 代码9
const L1 = ['a', 'b', 'c', 'd'];
const L2 = ['d', 'a', 'b', 'c'];
const IT = [ 3 ,  0 ,  1 ,  2 ]; // 新序列中元素在旧序列中对应的下标
const LIS =      [0 ,  1 ,  2 ]; // 求得的最长上升子序列

接下来我们将IT和LIS从尾部进行对比，为了知道我们移动到的目标位置，对比的步骤如下。

从后向前遍历IT和LIS；
如果当前IT元素和LIS元素相同，则不做任何操作，继续遍历两个表的前一个元素；
当前访问的IT元素不等于LIS元素或者LIS元素已经不存在，则记录如下移动操作（将当前IT元素移动到当前LIS元素之前），继续遍历下一个IT元素，当前$LIS$元素不变；
直到IT元素全部遍历结束。

伪码描述如下。

// 代码10
j = LIS - 1, last = IT.length, patches = []
for i in range IT.length to 0:
  if (IT[i] == LIS[j] && LIS[j] != NULL):
    last = j
    j -= 1
  else:
    patches.push('move ' + IT[i] + ' before ' + LIS[last])

插入

好了，到这里为止我们已经将算法的核心思想全部都介绍完了，但是有同学肯定注意到了，我们虽然讲了一堆，但是还有一个核心操作没有提到。我们有了删除，有了移动，但没有插入。

再坚持一下，就差最后一步就结束了。

假设两个列表的输入如下。

// 代码11
const L1 = ['a', 'b', 'c', 'd'];
const L2 = ['d', 'a', 'e', 'b', 'c'];
const IT = [ 3 ,  0 ,  -1,  1 ,  2 ]; // 新序列中元素在旧序列中对应的下标
const LIS =            [0,  1 ,  2 ]; // 求得的最长上升子序列

此时我们多了一个L1中没有的元素e，所以旧序列下标对应表中找不到该元素的下标，这里就用-1表示，这也就是为什么前文我们再$LIS$的计算过程中跳过对负数处理的原因，因为新元素不在我们不希望移动的元素之中，我们希望计算出来的$LIS$仍然是[0, 1, 2]，也就是['a', 'b', 'c']三个元素依然不需要被移动。

那对于负数我们在移动的过程中怎么处理呢？为了得知插入的位置，这里我们需要记录上一个访问过的IT表中的非-1元素，这里需要引入一个last变量来记录它。

过程如下。

从后向前遍历IT和LIS；
如果IT元素非-1，则记录其下标为last；
1. 如果当前IT元素和LIS元素相同，之后遍历两个表的前一个元素；
2. 当前访问的IT元素不等于LIS元素或者LIS元素已经不存在，则记录如下移动操作（将当前IT元素移动到last元素之前），继续遍历下一个IT元素；
否则记录如下插入操作：将当前L2中下标为当前IT元素的项插入到L1中下标为IT[last]之前；
直到IT元素全部遍历结束。

伪代码如下。

// 代码10
j = LIS - 1, last = IT.length, patches = []
for i in range IT.length to 0:
  if IT[i] == -1:
    patches.push('insert ' + L2[i] + ' before ' + L1[IT[last]]);
  else:
    if IT[i] == LIS[j] && LIS[j] != NULL:
      j -= 1
    else:
      patches.push('move ' + IT[i] + ' before ' + LIS[j])
  last = IT[i] == -1 ? last : j

这样，加上一开始我们得到的删除操作，我们就拿到了所有的删除，移动，和插入操作了。整个带标记列表的对比算法到这里也就结束了。

其实还有一个更新相同标记的节点的操作，该操作在发现新列表的中存在相同节点的时候就已经做了。

总结

本文详细记述了InfernoJS中实现的带标记列表的对比算法，相比React和Vue等框架，它牺牲了一定的时间复杂度并得出了最优解，但React和Vue之所采取现行的方式实现，是因为它们在时间复杂度和最优解之间做了权衡，从实际应用场景来考虑这些算法并没有绝对的对错，而Riact作为一个以学习为目的的项目，还是选择了实现难度略高一些的算法。

整个算法的实现在Riact中都可以找到，（放心，项目文件目录很简单，从文件的名字你就能很快找到你想要的），同时这里还给出了一版和框架无关的实现（不确定是否需要翻墙）。

整个算法的大体过程虽然已经给出了，但是实际上我们还是隐去了很多细节（上面的patches中只是用了一句话来描述算法的移动和插入操作），尤其是算法得出的结果到底以一种怎样的方式存储，旧的列表又怎样去应用这些结果，使其成为新的列表，这些内容我们将放到以后的文章中去讨论。

最后留个悬念。显然，我们是不能用JavaScript中数组的shift，unshift，以及splice之类的方法的来操作这两个列表的。