但凡用过UITableView的同学肯定遇到过一个 crash：数据源和操作不匹配的crash。典型情况如，你调用了tableview.insertRows(at:with:)希望插入一个第3行的 row，但是实际你的最新数据源只有两个数据，不会有第三行，这个时候就会发生 crash。有些时候这种问题很容易解决，尤其是开发阶段。但是当这个crash 是发生在测试阶段甚至是线上的时候，就非常难以定位。要解决这类问题，我们需要将数据源的更新和UITableView的 row 操作保持绝对一致。如果修改数据比较少，要做到这点还比较简单，但如果要修改的数据多且复杂的时候，这就不同容易了。于是我们就需要有有一个高效的算法帮我们快速地找到两个数据的变更点，也就是需要有高效的 diff 算法。
那么到底什么 Diff 算法才是最好的呢？
Diff 算法
什么是直观的 Diff
人们对于 Diff 算法最早的需求来源比较两个不同文件的差异。通俗的说，就是求出 A 字符串变化成 B 字符串的最小编辑距离。常见的场景如 Git 的 Diff。而git 为我们生成的 diff 是很直观易懂的，一看就知道我们对文件进行了哪些改动。但是，实际上，diff 生成是一个非常复杂的问题。
举个简单的例子，源文本为 ABCABBA，目标文本为 CBABAC，他们之间的 diff 其实有无穷多种（我们以字符为单位，一般情况下是以行为单位）。比如
1. - A 2. - A 3. + C
- B + C - A
C B B
- A - C - C
B A A
+ A B B
B - B - B
A A A
+ C + C + C
上面三种都是有效的 diff，都可以将源文本变成目标文本，但是第二种和第三种没有第一种看起来“直观”。
所以，我们需要个算法，生成“直观”的 diff，怎么样才叫“直观”呢？
删除后新增，比新增后删除要好，也就是说，上面的例子 2 比例子 3 看起来要直观
-
当修改一块代码时，整块的删除然后新增，比删除新增交叉在一起要好，例如：
Good: - one Bad: - one - two + four - three - two + four + five + five + six + six - three
-
新增或删除的内容应该和代码结构相呼应，例如下面的例子，左边我们可以很直观地看出新增了一个inspect 方法。
Good: class Foo Bad: class Foo def initialize(name) def initialize(name) @name = name @name = name end + end + + + def inspect + def inspect + @name + @name + end end end end
除了直观以外，diff 还需要短，这一点是好理解的，我们希望 diff 反应的是把源文本变成目标文本需要用的最少的操作。
Myers 算法
最早的 Diff 算法是E. Myers发表在1986年的论文: [ An O(ND) Difference Algorithm and Its Variations]。这个算法至今也被广泛使用，比如git 采用的就是这个 Diff 算法。Myers 算法的时间复杂度在 O(ND)，N 是AB 字符串的长度和，D是 AB 字符串差异部分的总长度。
Myers 算法的原理——寻找图的路径
以两个字符串，src=ABCABBA，dst=CBABAC 为例，根据这两个字符串我们可以构造下面一张图，横轴是 src 内容，纵轴是 dst 内容。
那么，图中每一条从左上角到右下角的路径，都表示一个 diff。向右表示“删除”，向下表示”新增“，对角线则表示“原内容保持不动“。
现在比如我们选择下面这条路径：
这条路径代表的 diff 如下。
- A
- B
C
+ B
A
B
- B
A
+ C
现在，“寻找 diff” 这件事，被抽象成了“寻找图的路径”了。那么，“最短的直观的” diff 对应的路径有什么特点呢？
- 路径长度最短（对角线不算长度）
- 先向右，再向下（先删除，后新增）
Mayers 算法的过程
根据 Myers 的论文，他提出了三个概念：
- snake: 一条snake代表走一步。例如从(0,0)->(0,1) / (0,0)->(1,0) / (0,1)->(0,2)->(2,4) 这分别为三条snake，走对角线不计入步数。
- k line: 定义 k = x - y （我们可以写成 y = x - k，是相同斜率的平行斜线组成的一个集合)
- d contour: 走一步算一个d
还是以上图为例，我们模拟一下这个算法的运行过程：
从（0，0）开始，此时 d 为0，k 为0
d 增加 1，也就是这个时候前进一步，此时 d = 1。我们只能选择向右或者向下，于是这时k = 1(终点是
1,0)或者 k=-1(终点是0,1)-
继续前进一步，d = 2。由于在每一步，我们都有向右和向下两种走法，那么这一步我们将会产生 2 * 2 = 4 种走法。但是我们会发现 向右向下 和 向下向右 两种走法抵达的终点是一致的，而根据我们前面说的，优先向右，那么这里我们只取 向右向下 这个解法。
于是这个时候我们可能的状态是：
d = 2, k = 2, 终点 (2,0)
d = 2, k = 0, 终点 (1,1)
d = 2, k = -2, 终点 (0,2)
然后我们继续走下一步了？等等！这时候我们观察路径图，我们会发现以上3个终点都存在对角线路径，而对角线路径是被认定为不占步数的，基于寻找最长路径的需要，我们需要沿着对角线继续往前走直到没有对角线。于是修正后的终点如下：
d = 2, k = 2, 终点 (3,1)
d = 2, k = 0, 终点 (2,2)
d = 2, k = -2, 终点 (2,4)
继续上面的过程，直到我们找到其中一个路径的终点是(7,6)。
以上整个算法的执行中，我们会得到下面这个图：
这个时候，我们知道了 Mayers 算法是典型的动态规划算法，也就是每一个问题的求解依赖于上一个问题的求解。
动态规划存在的一个明显问题，在这个算法也存在，就是空间复杂度高。当用于git 的时候，这个空间消耗就显得完全没法接受了。
实际上 git 采用的是 Mayers 算法的变种。Myers 在他的 论文 中，同时提供了一个算法变种，这个变体需要的空间开销要小得多。但是在某些情况下，变体产生的 diff 会和标准算法有所不同。
前端虚拟 Dom 框架采用的 Diff 算法
这里并没有特指某种Diff 算法，而是分析前端采用的最流行和最高效的 Diff 思路。需要注意的是，前端在虚拟 Dom 的比较中，往往是两颗树的比较，传统算法的时间复杂度是 O(n^3) 。要完整地比较两棵树是非常困难和低效的事情，所以大多框架会采用仅比较同层节点的剪枝优化手段。我们这里仅仅分析同层比较的 Diff 算法。
React 的 Diff 算法
我们以下面两个数组为例子：
A: [a, b, c]
B: [c, a, b]
具体步骤：
-
建立旧数组的索引：
I: { a: 0, b: 1, c: 2 } -
从头遍历新数组，并记录新数组的元素在旧数组的位置(通过第一步建立的索引实现快速查询)。同时用
last记录处理过的元素的最大索引值。last的初始值为0。A: [a, b, c] B: [c, a, b] ------------ P: [., ., .] last: 0 -
在每查询到一个新数组的元素的时候，都将这个 新数组的元素 在 旧数组 的 索引值和
last比较，如果比last小，说明需要移动这个元素，否则不需要移动并更新last的值。A: [a, b, c] B: [c, a, b] ------------ P: [2, ., .] last: 2 (2 > pre_last:0, 所以 c 不需要移动，将 last 更新)A: [a, b, c] B: [c, a, b] ------------ P: [2, 0, .] last: 2 (0 < pre_last:2, 所以 a 需要移动到 c 的后面)A: [a, b, c] B: [c, a, b] ------------ P: [2, 0, 1] last: 2 (1 < pre_last:2, 所以 b 需要移动到 a 的后面) -
最终我们得到的结果是：
先后移动 a b 节点需要注意的是，在 React 中，被移动的是虚拟 Dom 指向的真实 Dom。比如 a 移到 c 的后面的操作，实际上是把 a 指向的真实 Dom 移到 c 指向的真实 Dom 的后面。实际 AB 数组并没有变化。
Neil Fraser 优化
Neil Fraser 在2006提出过一个 Diff 的前置优化。简单的说就是寻找两个数组的最大公共前后缀，并把公共前后缀移除出 Diff 的计算过程。比如：
A: [a, b, c, d]
B: [a, b, d]
通过观察，我们发现 A 和 B 的公共前缀是[a, b]，公共后缀是[d]。那么最后参与 Diff 的仅仅是：
A: [c]
B: []
这个时候我们会发现剩下的元素的 Diff 非常简单，直接就是对c元素做删除操作即可。大量减少了计算过程和空间使用。
移动操作优化（inferno）
回到前面讲 React 的 Diff 算法的例子，我们最终得到的结果是要移动两次。
A: [a, b, c]
B: [c, a, b]
移动 a, 移动 b
但是，有的读者会提出质疑，明明将c移动到最前面一步就够了。于是为了进一步优化 Diff 操作，inferno提出一个新的优化：
-
在 React 的Diff 算法中，遍历完新数据的元素后，我们得到：
A: [a, b, c] B: [c, a, b] ------------ P: [2, 0, 1] -
这个时候，我们需要求出 P 的最长上升子序列(时间复杂度 O(nlogn))：
A: [a, b, c] B: [c, a, b] ------------ P: [2, 0, 1] LIS: [0, 1]LIS 是最长上升子序列对应的索引。
-
我们从尾部同时遍历 P 和 LIS：
遍历的规则是：
↑P每次往前走一步，当↑LIS等于↑P时，↑LIS往前走一步A: [a, b, c] B: [c, a, b] ------------ P: [2, 0, 1] ↑ LIS: [0, 1] ↑值相等，所以不需要执行移动操作，但
↑LIS往前走一步。这里需要注意的是，如果对应的P为-1，也就是说该元素在旧数组不存在，则需要执行插入操作。A: [a, b, c] B: [c, a, b] ------------ P: [2, 0, 1] ↑ LIS: [0, 1] ↑值相等，所以不需要移动操作。
A: [a, b, c] B: [c, a, b] ------------ P: [2, 0, 1] ↑ LIS: [0, 1] ↑ (undefined)由于
↑LIS已经无效，所以将c移动到a前面。如果↑P不等于↑LIS，同样也是执行移动操作。 最终我们得到的操作仅仅只有一个：将
c移动到a前面
Heckel 算法
Heckel 算法是Paul Heckel 在1978年提出的。Heckel 算法是一个非常高效的算法，时间复杂度做到了 O(n)。和上一个算法类似，同样也是采用空间换时间的方式，使用索引来提高 diff 的效率。
Heckel 算法的过程
我们以下面这个例子来分析 Heckel 算法的过程：
A: [a, b, c, b]
B: [b, c, d]
-
首先我们需要遍历 A 数组来建立一个用来跟踪 A 数组元素的哈希表：
A: [a, b, c, d, b] B: [b, d, c, e] //HA 用来记录 A 数组的情况， HA: [ a: U(0), b: D(1,4), c: U(2) d: U(3) ]U(0)表示只有一个, 并且索引是0；D(1,4)表示存在多个，并且索引是1，4 -
其次我们需要遍历 B 数组来建立两个数组，用来跟踪 B数组的元素出现在 A 数组的索引，以及A 数组的元素出现在 B 数组的索引：
//OB 用来记录 B 数组在 A 的索引 OB: [1, 3, 2, .] //OA 用来记录 A 数组在 B 的索引 OA: [., 0, 2, 1, .]b在 A 数组出现过多次，那么我们会依次取其在A 数组的索引。假如 B 数组是[b, b, d, c, d]，那么 OB 就是[1, 4, 3, 2, .]c在 A 数组出现在索引2，所以其对应的值是2e在 A 数组中没有出现过，所以其值为. -
数据记录完毕后，我们准备开始 diff 的过程。我们首先需要找到被删除的元素——OA 中值为
.的值即为被删除的元素：delete: [0, 4]同时我们需要记录删除偏移量和标记 A 数组的元素是否被处理过：
deleteOffset: [0, 1, 1, 1, 1] traced: [1, 0, 0, 0, 1] -
现在我们要找到需要移动的元素。我们从头遍历OB，同时也设置一个指针指向 traced 的第一个未处理的元素：
index: [0, 1, 2, 3, 4] traced: [1, 0, 0, 0, 1] ↑ OB: [1, 3, 2, .] ↑因为当前的 OB 值为1，traced 的索引值也为1，所以说明
b不需要被移动。同时我们需要把traced[OB]的值设为1.继续往后走，同时 trace 指针也指向下一个未处理的元素：
index: [0, 1, 2, 3, 4] traced: [1, 1, 0, 0, 1] ↑ OB: [1, 3, 2, .] ↑因为 OB = 3，index = 2，两者不等，所以需要移动
c，但是应该如何移动呢？A: [a, b, c, d, b] B: [b, d, c, e] deleteOffset: [0, 1, 1, 1, 1] OB: [1, 3, 2, .] ↑OB记录的是 B 数组元素在 A 的位置，OB = 3，意味着
d需要从 3 移到 1 (1是当前的 OB 的索引值)。但等等，在前面的删除操作中，我们已经把a删除了，也就是说这个时候d的原始位置变成了 3 - 1 = 2，其中1是deleteOffset[3]的值。那么最终move增加了一条记录为：move: [(source: 3 - 1, target: 1)]将
traced[OB]设置为1，然后继续执行：index: [0, 1, 2, 3, 4] traced: [1, 1, 0, 1, 1] ↑ OB: [1, 3, 2, .] ↑因为 OB = 2， traced 的 索引值也是2，所以不需要操作，继续执行：
index: [0, 1, 2, 3, 4] traced: [1, 1, 1, 1, 1] ↑ (nil) OB: [1, 3, 2, .] ↑因为此时OB 的值为空，所以执行插入操作。
-
最终我们得到的操作是：
delete: [0, 4] move: [(source: 2, target: 1)] insert: [3]
Heckel 算法的缺陷
在前面我们分析 React 的Diff 算法时，我们发现部分场景下，得到的 Diff 结果并不是最优解。很遗憾 Heckel 算法也存在同样的问题。比如：
A: [a, b, c]
B: [b, c, a]
得到的结果是：
move: [
(source: 1, target: 0),
(source: 2, target: 1)
]
但最优结果其实是：
move: [(source: 0, target: 2)]
所以尽管 Heckel 算法时间复杂度低，但是其得到的结果并不是最优结果。
各种算法的比较
我在前面分享了三种主流 Diff 算法的工作原理，现在想说说我对这三种 Diff 算法的理解：
- Mayers 算法效率相对较低，且不能得到 move 操作，仅能得到 insert / delete 操作。
- 采用了 Inferno 优化的 React Diff算法得到的 Diff 结果最优，并且时间复杂度达到了 O(nlogn)。由于对于渲染器这类框架 Diff 操作是一个相当消耗资源的行为，所以需要最佳的 Diff 结果。
- Heckel 算法虽然得到结果的并不一定是最优的，但是如果对于iOS 的
UITableView刷新等类似的操作来说，更快地获取 Diff 结果可能是更重要的。
DifferenceKit
DifferenceKit 是一个基于 Heckel 算法的 Diff 框架。按照其公布的 benchmark 数据，其超越了其他主流的 iOS Diff框架。
| Base algorithm | Order | |
|---|---|---|
| DifferenceKit | Heckel | O(N) |
| RxDataSources | Heckel | O(N) |
| FlexibleDiff | Heckel | O(N) |
| IGListKit | Heckel | O(N) |
| DeepDiff | Heckel | O(N) |
| Differ | Myers | O(ND) |
| Dwifft | Myers | O(ND) |
| Swift.CollectionDifference | Myers | O(ND) |
5000个数据（删除100，插入1000，移动200）的耗时
| Time(sec) | |
|---|---|
| DifferenceKit | 0.0019 |
| RxDataSources | 0.0074 |
| IGListKit | 0.0346 |
| FlexibleDiff | 0.0161 |
| DeepDiff | 0.0373 |
| Differ | 1.0581 |
| Dwifft | 0.4732 |
| Swift.CollectionDifference | 0.0620 |
100,000个数据（删除10,000，插入10,000，删除2,000）的耗时
| Time(sec) | |
|---|---|
| DifferenceKit | 0.0348 |
| RxDataSources | 0.1024 |
| IGListKit | 0.7002 |
| FlexibleDiff | 0.2189 |
| DeepDiff | 0.5537 |
| Differ | 153.8007 |
| Dwifft | 187.1341 |
| Swift.CollectionDifference | 5.0281 |
可以看到 DifferenceKit 的运行效率要比其他框架好得多。
DifferenceKit 的优化
尽管有好几个框架的采用的是和 DifferenceKit 相同的算法，但是 DifferenceKit 的效率却高上许多，我觉得和其采用的很多优化手段有关：
Swift 的运行效率要比 Objective-C 要高。这个从语言机制就能了解，不细说。
-
使用
ContiguousArray而不是Array大部分情况下，
ContiguousArray和Array类似，但是Array多了一些类型检查，会耗费多一点时间 -
大量使用了
reserveCapacity来指定数组的大小这样的好处是提前申请了一片连续的空间用来存储数据，在 append 的时候避免重新申请空间的情况。
但是需要注意的是，如果多次调用
reserveCapacity，可能导致更严重的性能问题。可以参考这篇文章 -
不拆箱来比较 Optional 的值
通常来说，我们想知道一个变量是不是 nil，可以通过
x == nil来判断。但是通过if case .none = x减少了拆箱的步骤，效率会稍微高一点。
OC版本的 DifferenceKit
尽管现在的大方向是使用 Swift 开发，但是现在仍有很多团队在使用 OC。我将 DifferenceKit 转译成了 OC，地址是DiffKit，欢迎使用。
总结
最初的想法仅仅是分享一下 DifferenceKit 的原理，但在查资料的过程中，让我接触到了更多的 Diff 算法。并且我也发现了这些 Diff 算法有其独到之处。于是这篇文章就变成了主流 Diff 算法的原理探究。期间查阅参考了不少资料和文章，也发现了部分文章的谬误。基于负责的态度，对于我讲述的内容，我采用了多个例子做验证。同时，相比其他文章，我会在关键步骤上讲得更详细些，希望能让读者们更容易理解算法背后的思想。
如果本文对你有帮助，希望能得到你小小的一个赞。
