Inferno.js 中的 DOM Diff 算法

发表于 更新于 分类于 Disqus：

已经关注 Inferno.js 有两年的时间，终于在刚刚不久的过去建立起了官网和文档。

值得特别关注的是，Inferno.js 提供了类 React API 的同时，在 DOM Diff 算法上借鉴了 ivijs，取得了更高的效率，从而有较强的性能表现。

优秀的 DOM Diff 算法的核心都是在将一个 DOM 集合转换成另一个 DOM 集合的同时，尽可能地复用已有 DOM 并具有较少的 DOM 移动操作，这是由于 DOM 操作（甚至访问）的成本较高。

Inferno.js 在两个 VDom 之间进行比较，从而避免了频繁访问 DOM 的性能开销。下面我们看一下它实现的 DOM Diff 算法。

我们假设有原始的 DOM 集合A为 “dfibge”，更新后的集合B为 “igfheb”。

首先得到集合B中元素在A中的原始位置，如果在A中不存在则为-1，得到：

1
2
3
var A       = [d, f, i,  b, g, e];
var B       = [i, g, f,  h, e, b];
var sources = [2, 4, 1, -1, 5, 3];

现在我们获取该数组的最大递增子序列的序列位置，为：

1
var seq = [0, 1, 4];// [2, 4, 5]

这个数组的意义在于：“新数组中第0、1、4位置的元素在原始数组中是无需移动的”，这是我们能获取最小移动步数的关键。

一共6个成员，3个无需移动，那么一定有3个需要操作

现在我们从后往前遍历集合B，观察每个成员的位置是否存在于 seq 中，存在则不必操作，不存在则需移动。

首先我们需要先删除B中存在，但A中不存在的元素 d，此时：

1
A=[f, i, b, g, e]

观察B中最后一个元素：

1
2
3
A=[f, i, b, g, e]
B=[i, g, f, h, e, b]
                  ^ pos=5

位置是5，不存在于 seq 中，需要把集合A中的 b 移到最后，此时：

1
A=[f, i, g, e, b] --- (1)

观察B中倒数第二个元素：

1
2
3
A=[f, i, b, g, e]
B=[i, g, f, h, e, b]
               ^ pos=4

位置是4，存在于 seq 中，无需操作。

观察B中倒数第三个元素：

1
2
3
A=[f, i, b, g, e]
B=[i, g, f, h, e, b]
            ^ pos=3

在A中不存在，我们需要创建 h，并放到 e 的前面，此时：

1
A=[f, i, g, h, e, b] --- (2)

观察B中倒数第四个元素：

1
2
3
A=[f, i, g, h, e, b]
B=[i, g, f, h, e, b]
         ^ pos=2

位置是2，不存在于 seq 中，需要把集合A中的 f 移到 h 的前面，此时：

1
A=[i, g, f, h, e, b] --- (3)

观察B中倒数第五个元素：

1
2
3
A=[i, g, f, h, e, b]
B=[i, g, f, h, e, b]
      ^ pos=1

位置是1，存在于 seq 中，无需任何操作。

观察B中倒数第六个元素，也是最后一个元素：

1
2
3
A=[f, i, b, g, e]
B=[i, g, f, h, e, b]
   ^ pos=0

位置是0，存在于seq中，也无需任何操作。

此时，所有操作都已结束，仅需3步，集合A已经转换成了集合B。其中，对 d 的移除和对 h 的创建是不可避免的，除此之外，仅进行了两次DOM移动，也印证了上面提到的 6-3=3 的操作步骤。

我们在移动 DOM 的时候都是执行的“插在XXX之前”，是因为 DOM 中的 insertBefore 方法，如果存在 insertAfter，那么从前往后操作也是等效的。