Myers 差分算法 (Myers Difference Algorithm) —— DiffUtils 之核心算法（一）

如果使用过 android architecture 中关于 LiveData 部分的朋友，可能对于 DiffUtils 这个玩意儿并不陌生。

在使用 DiffUtils 之前，如果想使用 Adapter 的 notify 系列函数，可能并不是那么方便，我们想象下，需要知道一个列表对于另外一个列表的 difference ，我们想简单的实现一个这种方法，并不是可以一下子写出来的。好在我们发现 Google 提供了这个 工具 类，就是 DiffUtils 。

DiffUtils.java 头部相关的介绍

/*
 * android.support.v7.util.DiffUtils
 *
 * DiffUtil uses Eugene W. Myers's difference algorithm to calculate the minimal number of updates
 * to convert one list into another. Myers's algorithm does not handle items that are moved so
 * DiffUtil runs a second pass on the result to detect items that were moved.
 */

这里告诉我们，DiffUtils 使用了 Eugene W. Myers's difference algorithm 这个算法，我们可以简单的翻译成 Myers 差分算法 ，来计算两个列表最小的更新操作数。在这个类的头部注释的最后，也给出了相关性能的数据：

/*
 * <ul>
 *     <li>100 items and 10 modifications: avg: 0.39 ms, median: 0.35 ms
 *     <li>100 items and 100 modifications: 3.82 ms, median: 3.75 ms
 *     <li>100 items and 100 modifications without moves: 2.09 ms, median: 2.06 ms
 *     <li>1000 items and 50 modifications: avg: 4.67 ms, median: 4.59 ms
 *     <li>1000 items and 50 modifications without moves: avg: 3.59 ms, median: 3.50 ms
 *     <li>1000 items and 200 modifications: 27.07 ms, median: 26.92 ms
 *     <li>1000 items and 200 modifications without moves: 13.54 ms, median: 13.36 ms
 * </ul>
 */

这个性能非常可观呀，如果结合我们的业务实际，这种计算性能，再考虑把计算操作放置到非 UI 线程中操作，那么我们得到的就是一个非常平滑的操作体验了。

Eugene W. Myers's difference algorithm

为了致敬大神，先把大神的论文贴上： http://www.xmailserver.org/diff2.pdf

我结合源码、互联网上的文章，并摒弃一些我看不懂的内容，尽量把这一块讲明白。

首先，我们定义一个事情：

把一个列表从 A 变成 B，事实上就是找出 A 和 B 的 最长公共子序列（LCS） ，然后把 LCS 和 A 比，多出来的删除，和 B 比，少掉的添加进去。

那么，这里的问题就演变成了如何解决这个问题了。先贴上非常重要的图

这张图，我们可以这样理解，纵坐标是序列 A，横坐标是序列 B，我们的目标是从 (0,0) 走到右下角，往下走一步是删除一个 A 里面的元素，往右走一步是添加一个 B 里面的元素，往右下角走是不添加也不删除。那么问题就很简单了，我们尽量走 对角边 让操作变得最少，目的是走到右下角。我们看看对角边的性质，只要 A[i] == B[j] 那么 (i,j) 就可以从 (i-1, j-1) 走过来，否则只能从 (i-1, j) 或者 (i, j-1) 走过来，所以一碰上 A[i] == B[j] 的话，就存在了一条斜边。

显然，在我们画出这幅图之后，我们有两种方式可以解题了，这幅图可以非常简单的抽象成 带权重的有向图 ，解法是：

1. 最短路径算法，假设横向纵向权值为 1，对角权值是 0，那么只要总和权重最低，这就是我们的最优解。
2. 使用贪心算法，分解子问题，子问题的分解如上所述。

三个概念

根据 Myers 的论文，他提出了三个概念：

1. snake : 一条snake代表走一步。例如从(0,0)->(0,1) / (0,0)->(1,0) / (0,1)->(0,2)->(2,4) 这分别为三条snake，走对角线不计入步数。
2. k line: 定义 k = x - y （好吧，我习惯写成 y = x - k，这是相同斜率的平行斜线组成的一个集合)
3. d contour: 走一步算一个 d

上图中，我们的目标点是 （7,6)，那么 k 和 d 的关系就如下图所示了：

这幅图中的坐标自变量是d和k，表示了在不同 d 取值以及不同的 k 取值最终可以到达的坐标，这幅图和上面一幅图结合起来看。

当一步也不走（d = 0）的时候，我们可以“走”到最远的坐标是（0，0）; 当走一步（d = 1）的时候，我们往 k = 1 的方向走，可以走到（1，0），往 k = -1 的方向走，可以走到（0，1）

那么当走两步的时候（d = 2）的时候，我们从 k = -2 出发，起点是（2，4），往下走就到达了（2，5）这时候，发现这个点在对角线上，最终移动到（3，6）。

我们看一下，红色标记的几个方块，就是我们最终到达（7，6）的路径了，这是最优解。

结论

综上所述，我们只要能找到所有斜边，然后找到最短的d，到达我们最远的点即可。

参考文章： https://www.jianshu.com/p/7f1473c2e521