Myers 差分算法 —— Android DiffUtils 之实现（二）
Myers 差分算法 —— Android DiffUtils 之实现（二）
专注高级工程师进阶，共同成长，共度寒冬
上一篇看这里：
Myers 差分算法 (Myers Difference Algorithm) —— DiffUtils 之核心算法（一）
我们在上文简单的介绍了下 Myers 差分算法的原理，至少知道了他是怎么一回事，我们知道寻找最远的点方法有两个，一个是采用最短路径或者广度优先搜索算法，另一种是使用动态规划。
我们来看一下 Google 是怎么做的。
DiffUtil 采用的策略
首先，先不看细节，我们从入口开始看起：DiffUtil.calculateDiff，一看见一个栈
final List<Range> stack = new ArrayList<>();
stack.add(new Range(0, oldSize, 0, newSize));
final int max = oldSize + newSize + Math.abs(oldSize - newSize);
// allocate forward and backward k-lines. K lines are diagonal lines in the matrix. (see the
// paper for details)
// These arrays lines keep the max reachable position for each k-line.
final int[] forward = new int[max * 2];
final int[] backward = new int[max * 2];
// We pool the ranges to avoid allocations for each recursive call.
final List<Range> rangePool = new ArrayList<>();
while (!stack.isEmpty()) {
//...
}
此处的栈实际上是把所有和Snake走出去最远的点做一个搜索算法。
这里 Google 采用了前进（Forward）和后退（Backward）两种方式来找到 Snake。
这里我们先看里面的循环 —— diffPartial
diffPartial
diffPartial主要的任务是查找 Snake，函数原型如下：
private static Snake diffPartial(Callback cb, int startOld, int endOld,
int startNew, int endNew, int[] forward, int[] backward, int kOffset)
此处的 Callback 是业务方提供一个 Predicate Callback 供引擎使用。我们在前文（https://geminiwen.com/archives/68/）的图里面，可以看见我们是使用两个坐标轴来表示老的数组和新的数组的，对应这里的old和new，也对应了 x 值和 y 值。此处的forward和backward记录的是从左上和右下，以k为底的x值（因为 k = x + y，记录了 k 和 x，直接能得到 y）。
我们此处要记住一点：
只要 k 一致，如果 forward[k] >= backward[k]，那么意味着相同的 k 值，往相反的方向走的两条步伐已经走到了一起，> 形成了一条通路，他们的轨迹已经重合，那么证明这个路径是通的，这时候，就把这个大问题分解成了两个剩余的小问题：
- 找到这条斜线从原点到斜线左上角中的最优解。
- 找到这条斜线从斜线右下角到终点的最优解。
那么解决小问题的方式就是重新递归刚刚的过程，我们这时候结合代码和图来讲。
何时返回 Snake 对象？
我们注意到，diffPartial有两个返回 Snake 对象的地方：
for (int d = 0; d <= dLimit; d++) {
for (int k = -d; k <= d; k += 2) {
//....
if (checkInFwd && k >= delta - d + 1 && k <= delta + d - 1) {
if (forward[kOffset + k] >= backward[kOffset + k]) {
Snake outSnake = new Snake();
outSnake.x = backward[kOffset + k];
outSnake.y = outSnake.x - k;
outSnake.size = forward[kOffset + k] - backward[kOffset + k];
outSnake.removal = removal;
outSnake.reverse = false;
return outSnake;
}
}
}
for (int k = -d; k <= d; k += 2) {
//...
// find reverse path at k + delta, in reverse
if (!checkInFwd && k + delta >= -d && k + delta <= d) {
if (forward[kOffset + backwardK] >= backward[kOffset + backwardK]) {
Snake outSnake = new Snake();
outSnake.x = backward[kOffset + backwardK];
outSnake.y = outSnake.x - backwardK;
outSnake.size =
forward[kOffset + backwardK] - backward[kOffset + backwardK];
outSnake.removal = removal;
outSnake.reverse = true;
return outSnake;
}
}
}
}
为什么会有两块地方？我们先看内部的判断条件：
forward[kOffset + k] >= backward[kOffset + k]
这里的kOffset是为了后面的k值可以取负，因为数组下标不能为负，所以 hack 了一下。
我们再回忆一下，forward 和 backward 记录的是 x 的值，下标是k，这条判断语句的意思是，在同一条斜线上，如果forward[k]的值比backward[k]大，就为 true。 其实就是从左上往右下走和从右下往左上走交汇了。我们知道，只要是斜线，都有可能交汇，但是这里是一个跟d有关的 for 循环，也就是步数最少的连通斜线。
我们还注意到一个变量checkInFwd，这个变量字面意思是，是否在前进的过程中，检查连通情况。根据的原则是老的数组长度 oldSize 和新数组长度 newSize 的差值是否为奇数，这里应该是一个均分概率的思想，我目前没有找到相关的资料，如果有详细见解的朋友欢迎一起讨论。
返回的 Snake 包含了几个要素：
- x 和 y
- Snake 的长度
- Snake 是否做了 x 方向上的 remove 操作
- Snake 是否从反向方向开始
具体可以参考 Snake 这个类里面的注释。
/**
* Snakes represent a match between two lists. It is optionally prefixed or postfixed with an
* add or remove operation. See the Myers' paper for details.
*/
static class Snake {
/**
* Position in the old list
*/
int x;
/**
* Position in the new list
*/
int y;
/**
* Number of matches. Might be 0.
*/
int size;
/**
* If true, this is a removal from the original list followed by {@code size} matches.
* If false, this is an addition from the new list followed by {@code size} matches.
*/
boolean removal;
/**
* If true, the addition or removal is at the end of the snake.
* If false, the addition or removal is at the beginning of the snake.
*/
boolean reverse;
}
Snake 的使用
Snake 返回后，我们等于找到了两个区域之内的通路，那么通路的两边就变成了两个子问题，类似如图：
A 和 B 是子问题
这样就只用找到从左上角到右下角连起来一块的 Snake 集合即可。
在 DiffUtils 中的就是以DiffResult这个类表示，我们在这里已经收集到了所有 Snake，Snake 中包含了所有文本修改的路径和操作，因此我们可以根据 Snake 里面的定义，对我们的 Adapter 进行一些操作。我们可以看一下 DiffResult 这个类的一些操作，一个最重要的操作是dispatchUpdatesTo，传入的参数是一个 Adapter，我们可以看下这里的操作：
public void dispatchUpdatesTo(final RecyclerView.Adapter adapter) {
dispatchUpdatesTo(new ListUpdateCallback() {
@Override
public void onInserted(int position, int count) {
adapter.notifyItemRangeInserted(position, count);
}
@Override
public void onRemoved(int position, int count) {
adapter.notifyItemRangeRemoved(position, count);
}
@Override
public void onMoved(int fromPosition, int toPosition) {
adapter.notifyItemMoved(fromPosition, toPosition);
}
@Override
public void onChanged(int position, int count, Object payload) {
adapter.notifyItemRangeChanged(position, count, payload);
}
});
}
这里还有个更加复杂点的操作叫DetectMoves，就是检查是不是从老的 List 上删除的数据并不是真的“删除”，而是移动到了 List 中其它的位置，我们在这里就不再赘述。
有了 DiffUtil，我们去调用notifyItemXXX系列函数就变得非常流畅，实现线性补间动画也能和 iOS 一样轻松啦（虽然也做了非常多的工作）。
如果有兴趣的同学，还可以看一下AsyncListDiffer这个类，它实现了在异步线程计算 Diff 然后在主线程通知 UI 更新的功能。里面有一些 Executors 调度器，还有一个版本控制的思路，这个思路非常值得我们在进行异步计算的学习的一种手段。