我们在上文简单的介绍了下 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）和后退（Forward）两种方式来找到 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。我们在前文（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 调度器，还有一个版本控制的思路，这个思路非常值得我们在进行异步计算的学习的一种手段。

本文由 Gemini Wen 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Dec 19, 2020 at 10:27 am

Myers 差分算法 (Myers Difference Algorithm) —— Android DiffUtils 之实现（二）

DiffUtil 采用的策略

diffPartial

何时返回 Snake 对象？

Snake 的使用