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

in 开发 with 0 comment

我们在上文简单的介绍了下 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/)的图里面,可以看见我们是使用两个坐标轴来表示老的数组和新的数组的,对应这里的oldnew,也对应了 x 值和 y 值。此处的forwardbackward记录的是从左上右下,以k为底的x值(因为 k = x + y,记录了 k 和 x,直接能得到 y)。

我们此处要记住一点:

只要 k 一致,如果 forward[k] >= backward[k],那么意味着相同的 k 值,往相反的方向走的两条步伐已经走到了一起,> 形成了一条通路,他们的轨迹已经重合,那么证明这个路径是通的,这时候,就把这个大问题分解成了两个剩余的小问题:
  1. 找到这条斜线从原点到斜线左上角中的最优解。
  2. 找到这条斜线从斜线右下角到终点的最优解。

那么解决小问题的方式就是重新递归刚刚的过程,我们这时候结合代码和图来讲。

何时返回 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 包含了几个要素:

  1. x 和 y
  2. Snake 的长度
  3. Snake 是否做了 x 方向上的 remove 操作
  4. 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 调度器,还有一个版本控制的思路,这个思路非常值得我们在进行异步计算的学习的一种手段。

Responses