现在我们来交叉比较，看有没有相同的。如果OS或OE与NS相同，则移动到NS的位置，如果OS或OE与NE相同，则移动到NE的位置。如果都没有相同的，则在 Real DOM 中找到NS的元素，移动到NS位置。

可见，【A，G】与【D，E】没有相同的，那么就找到D元素，移动到NS的位置。这是第1次操作DOM，此时 Real DOM 为 【D、A、B、C、E、F、G】，NS++，OS++，现在4个指针的指向为：

D A B C E F G?				 ?OS        OE

然后开始第二轮比较，显然OS与NS都是A，相同，不用执行任何移动操作，OS++，NS++，现在4个指针的指向为：

D A B C E F G?			 ?OS      OE

现在开始第三轮比较，显然OE与NS都是G，相同，现在需要把OE移动到NS的位置。这是第2次操作DOM，此时 Real DOM 为 【D、A、G、B、C、E、F】，OE–，NS++，现在4个指针的指向为：

D A G B C E F?		 ?OS    OE

现在开始第四轮比较，显然OE与NS都是F，相同，现在需要把OE移动到NS的位置。这是第3次操作DOM，此时 Real DOM 为 【D、A、G、F、B、C、E】，OE–，NS++，现在4个指针的指向为：

D A G F B C E?	 ?OS  OE

现在开始第五轮比较，显然OE与NE都是E，相同，不用执行任何移动操作，OE–，NE–，现在4个指针的指向为：

D A G F B C E? ?OSOE

现在开始第六轮比较，显然NS（或NE）指向的 K 在 Real DOM 中并不存在，因此我们创建节点K，这是第4次操作DOM，此时 Real DOM 为 【D、A、G、F、K、B、C、E】，NS++，现在4个指针的指向为：

D A G F K B C E? ?OSOE

由于NE<NS，意味着 新序列中已经没有可遍历的元素，因此OS与OE闭区间内的节点都需要被删除，这是第5、6次操作DOM，此时 Real DOM 为 【D、A、G、F、K、E】。

到此为止，我们用了六次DOM操作，与 React 的性能相当。

我们还是总结一下 Vue 的 DOM Diff 算法的关键逻辑：

1. 建立新序列（Virtual DOM）头（NS）尾（NE）、老序列（Real DOM）头（OS）尾（OE）一共4个指针，然后让NS/NE与OS/OE比较；
2. 如果发现有OS或OE的值与NS或NE相同，则把相应节点移动到NS或NE的位置。

说的简单一点，其实 Vue 的这个 DOM Diff 过程就是一个查找排序的过程，遍历 Virtual DOM 的节点，在 Real DOM 中找到对应的节点，并移动到新的位置上。不过这套算法使用了双向遍历的方式，加速了遍历的速度。

从以上原理中我们可以轻易地推导出对该算法最不利的莫过于序列倒序。比如从【A、B、C、D】转换为【D、C、B、A】，算法将执行N-1次移动，与 React 相同，并没有更坏。

那么我们再看一眼对于 React 无法高效处理的例子，【A、B、C、D】转换为【D、A、B、C】，看一下 Vue 的算法表现如何。

在第一轮比较中，Real DOM 的末尾节点D与 Virtual DOM 的首节点D相同，那么就把节点D移动到首位，变成【D、A、B、C】，直接一步到位，高效完成了转换，从这一点上，并没有犯 React 的错。

不过值得说明的是，在匹配不成功的情况下，如何找到NS节点在 Real DOM 的位置，并非是顺序遍历的（否则就会导致 O(N²) 的复杂度），而是预先存储了各个节点的位置，查找映射表即可，所以可以说是用一定的空间复杂度换了时间复杂度。

Inferno

Inferno 虽然在一定程度上兼容 React 语法，但它最大的卖点却是其卓越的算法。如果说 React、Vue 的算法能在一定程度上能节约DOM操作的次数的话， 那么毫无夸张地说，Inferno 的算法就是能把DOM操作的次数降到最低。我们来看一下它是怎么办到的。

下面我们还是用之前的例子来演示这套 DOM Diff 是如何运作的，由【A、B、C、D、E、F、G】转换成【D、A、G、F、K、E】。

首先，我们记录 Virtual DOM 的各个元素在 Real DOM 中的序号：【3、0、6、5、-1、4】，记录为数组maxIncrementSubSeq，其中-1表示在 Real DOM 中并不存在，需要创建。

这个数组能说明什么呢？别着急，现在我们来获取该数组的“最大递归子序列”，当然，仅限非负数。

这个例子有4个子序列都满足需求：【3、5】、【3、4】、【0、5】、【0、4】，具体算法已经很成熟，这里不关心，我们随便取一个【3、5】。

Real DOM 在【3、5】位置上是节点D和节点G。这说明这两个节点是不需要移动位置的，其它都要移动或删除。

从数组 maxIncrementSubSeq 中我们已经能够推断出应该删除的节点是位于位置【1、2】的两个节点B和C，因为【1、2】并未出现在数组 maxIncrementSubSeq 中。这是第1、2次DOM操作，此时 Real DOM 为 【A、D、E、F、G】。

接下来我们从后往前遍历 Virtual DOM：

1. 最后一个是节点E，那我们就把节点E移动到最后，这是第3次DOM操作，此时 Real DOM 为 【A、D、F、G、E】；
2. 遍历到节点K，这是一个新节点，我们创建并插入到节点E（上一个遍历到的节点）之前，这是第4次DOM操作，此时 Real DOM 为 【A、D、F、G、K、E】；
3. 遍历到节点F，那我们就把节点F移动到节点K之前，这是第5次DOM操作，此时 Real DOM 为 【A、D、G、F、K、E】；
4. 遍历到节点G，由于节点G位于最大递增子序列中，因此不需要移动；
5. 遍历到节点A，由于节点A也位于最大递增子序列中，因此也不需要移动；
6. 遍历到节点D，那我们就把节点D移动到节点A之前，这是第6次DOM操作，此时 Real DOM 为 【D、A、G、F、K、E】。

同样操作了六次DOM，相比于 Vue、React 好像并没有什么优势，不过这是因为这个例子中的最大递增子序列太短导致的，也就是说，能保持位置不动的元素不够多。

同样再看一眼对于 React 无法高效处理的例子，【A、B、C、D】转换为【D、A、B、C】，看一下 Inferno 的算法表现如何。

显然，最大递增子序列所代表的不需要移动的元素是【A、B、C】，那么从后往前遍历 Virtual DOM，先后经历节点C、B、A都不需要移动，到节点D才需要移动一次，因此对于这种特殊场景，Inferno 也只需要一次 DOM 操作，与 Vue 效率相同。

那么对于序列倒序这种特殊场景，由于最大递增子序列的长度为1，所以也需要N-1次DOM移动操作，与 Vue 相同。

那么有没有能优于 Vue 算法的场景呢？试想将【A、B、C、D、E】转换为【C、D、E、A、B】。

对于 Inferno 而言，由于最大递增子序列【C、D、E】的长度为3，所以只需要5-3=2次DOM操作即可完成重排序。

ABCDEↆ
ACDEBↆ
CDEAB
预览

对于 Vue 而言，则依赖于算法在遇到无匹配的逻辑分支下，是决定补NS指针的节点位置还是补NE指针，如果是后者，则也只需要2次DOM移动操作，如果是前者，则需要3次。从实现代码上来看，是前者。

ABCDEↆ
CABDEↆ
CDABEↆ
CDEAB
预览

因此在一些比较特殊的情况下，Inferno 在节省DOM操作次数的指标上，是可能优于 Vue 的，不过也不多。

现在我们再来回想一下 React 的算法，在上面这个例子中，React 也只需要移动2次就够了。

ABCDEↆ
BCDEAↆ
CDEAB
预览

如果你仔细回味，就会发现，React 的 DOM Diff 算法其实也体现了最大递增子序列的概念，但是它假定这个子序列一定是从第一个位置开始的，一旦不是这样子，算法效率就会恶化，这也是为什么它不能很好地处理末尾节点移动到首位这种场景的，因为子序列长度仅为1。

三、总结

简单阐述了 React、Vue、Inferno 的算法梗概之后，我们统一总结一下：

1. Inferno 利用最大递增子序列的算法达到了移动DOM次数最少的目标；
2. React 假定最大递增子序列从0开始，在末尾节点移动到首位的场景中会恶化；
3. Vue 利用双向遍历排序的方法，有可能不是最优解，但与最优解十分逼近；
4. 三种算法对于倒序这种场景都降级为理论上的最少N-1次。

因此，在实际的业务开发中，序列倒序是最应该被避免的，对于 React 还应注意末尾节点的问题，除此之外，没有什么特别需要担心的，框架都会在足够程度上（虽然可能不是最优的）利用现有DOM而不是重新创建，从而实现性能优化的发挥。

需要特别指出的是，包括但不限于 React、Vue、Inferno 在内的众多框架，在同一层级节点上，都希望业务指定一个key值来判定重渲染前后是否是同一个节点，如果连key值都不同，那么DOM节点是不会被重用的。

在很多“最佳实践”文章中，都认为用数组遍历的序号来做key值是不可取的，不过这也取决于具体场景，典型的是，如果遍历的数据是静态不可变的，那么使用序号来做key并不会有什么问题。

退一步说，如果数组顺序变化，依然用序号做key会有什么问题呢？这个问题需要从两方面来回答。

首先，对于性能来讲，渲染前后对于同一个序号的数据发生了变化，框架依然可能会重用节点，这可能会导致后代节点的大量删除与重建。

其次，对于渲染结果正确性来讲，一般也不会有问题，但有一种场景，就是DOM上的数据并没有同步到框架中，比如 React 中的一个概念，叫做“失控组件（https://reactjs.org/docs/uncontrolled-components.html）”，那么重渲染之后，未同步的数据很可能出现在错误的节点中。

这就是使用序号来做key需要注意的知识点。

对于 Inferno 而言，key值的逻辑并不绝对，对于静态数组或者只是在尾部添加元素的数组，不使用key反倒在性能上更有优势。不过对于使用频率高得多的 React 和 Vue，还是老老实实都添加 key 为好。

最后，还有一个问题需要回答，Inferno 的算法是否解决了将一个数组打乱成另一个数组，中间最少需要几步的问题呢？我看不见得，大家要注意DOM有这样一个操作：insertBefore，它的功能是在一个节点前面插入另一个节点，如果要插入的节点就在这个兄弟节点集合中，那么它还会被自动从原来的位置移除。

数组有这样的特性吗？恐怕没有。数组是顺序存储的，在一个位置插入数据会导致后面的数据全部后移，这是可观的性能开销。

如果换成双向链表，那么我认为应用这几种算法都问题不大。