首先，我估计有一部分的同学可能还不知道DiffUtil是什么，说实话，之前我也根本不了解这是什么东西。DiffUtil是我在公司实习的时候了解到的一个类，在那之前，我使用RecyclerView的方式也是大部分的人差不多，就是RecyclerView和它的四大组成部分任意组合。
当时在公司第一次看到这个东西的时候，立即两眼发光，非常好奇这是什么东西，就好像在大街上看到美女一样。后来在非工作时间的时候，我去了解了一下这个类，不过当时也只是简单的了解这个东西。现在在系统的学习RecyclerView的源码，我觉得有必要深入的了解和学习一下这个东西--DiffUtil。
本文参考资料:
本文有一部分的内容来自上文的翻译。我的建议是，各位同学可以直接看上面的文章，大佬的文章已经将DiffUtil的核心算法讲的非常透彻。
本文打算从三个角度来分析DiffUtil
DiffUtil的基本使用Myers差量算法的深入探究DiffUtil的Myers算法实现以及DiffUtil怎么跟Adapter联系起来的
1. 概述
在正式分析DiffUtil之前，我们先来对DiffUtil有一个大概的了解--DiffUtil到底是什么东西。
我们相信大家都遇到一种情况，那就是在一次操作里面可能会同时出现remove、add、change三种操作。像这种情况，我们不能调用notifyItemRemoved、notifyItemInserted或者notifyItemChanged方法，为了视图立即刷新，我们只能通过调用notifyDataSetChanged方法来实现。
而notifyDataSetChanged方法有什么缺点呢？没有动画！对，通过调用notifyDataSetChanged方法来刷新视图，每个操作是没有动画，这就很难受了！
有没有一种方式可以实现既能保留动画，又能刷新动画呢？我们单从解决问题的角度来说，我们可以设计一种算法，来比较变化前后的数据源有哪些变化，这里的变化包括，如上的三种操作。哪些位置进行了change操作，哪些地方进行了add操作，哪些地方进行了remove操作，可以通过这种算法计算出来。
Google爸爸考虑到这个问题大家都能遇到，那我帮你们实现，这样你们就不用自己去实现了，这就是DiffUtil的由来。
2. DiffUtil的基本使用
在正式分析DiffUtil的源码之前，我们先来看看DiffUtil的基本使用，然后我们从基本使用入手，这样看代码的时候才不会迷茫。
我们想要使用DiffUtil时，有一个抽象类Callback是我们必须了解的，我们来看看，了解它的每个方法都都有什么作用。
| 方法名 | 作用 |
|---|---|
| getOldListSize | 原数据源的大小 |
| getNewListSize | 新数据源的大小 |
| areItemsTheSame | 判断给定两个Item的是否同一个Item。给定的是两个Position，分别是原数据源的位置和新数据源的位置。判断两个Item是否是同一个Item，如果是不同的对象（新数据源和旧数据源持有的不是同一批对象，新数据源可能是从旧数据源那里深拷贝过来，也有重新进行网络请求返回的），可以给每个Item设置一个id，如果是同一个对象，可以直接使用==来判断 |
| areContentsTheSame | 判断给定的两个Item内容是否相同。只有areItemsTheSame返回为true，才会回调此方法。也就是说，只能当两个Item是同一个Item，才会调用此方法来判断给定的两个Item内容是否相同。 |
| getChangePayload | 用于局部刷新，回调此方法表示所给定的位置肯定进行change操作，所以这里不需要判断是否为change操作。 |
简单的了解Callback每个方法的作用之后，我们现在来看看DiffUtil是怎么使用的。
我们先来看看ItemCallback是怎么实现的：
public class RecyclerItemCallback extends DiffUtil.Callback {
private List<Bean> mOldDataList;
private List<Bean> mNewDataList;
public RecyclerItemCallback(List<Bean> oldDataList, List<Bean> newDataList) {
this.mOldDataList = oldDataList;
this.mNewDataList = newDataList;
}
@Override
public int getOldListSize() {
return mOldDataList.size();
}
@Override
public int getNewListSize() {
return mNewDataList.size();
}
@Override
public boolean areItemsTheSame(int oldItemPosition, int newItemPosition) {
return Objects.equals(mNewDataList.get(newItemPosition).getId(), mOldDataList.get(oldItemPosition).getId());
}
@Override
public boolean areContentsTheSame(int i, int i1) {
return Objects.equals(mOldDataList.get(i).getContent(), mNewDataList.get(i1).getContent());
}
}
这里，areItemsTheSame方法是通过id来判断两个Item是不是同一个Item，其次areContentsTheSame方法是通过判断content来判断两个Item的内容是否相同。
然后，我们再来看看DiffUtil是怎么使用的：
private void refreshData() {
final List<Bean> oldDataList = new ArrayList<>();
final List<Bean> newDataList = mDataList;
// deep copy
for (int i = 0; i < mDataList.size(); i++) {
oldDataList.add(mDataList.get(i).deepCopy());
}
// change
for (int i = 0; i < newDataList.size(); i++) {
if (i % 5 == 0) {
newDataList.get(i).setContent("change data = " + i);
}
}
// remove
newDataList.remove(0);
newDataList.remove(0);
// add
addData(5, newDataList);
// diffUtil
RecyclerItemCallback recyclerItemCallback = new RecyclerItemCallback(oldDataList, newDataList);
DiffUtil.DiffResult diffResult = DiffUtil.calculateDiff(recyclerItemCallback, false);
diffResult.dispatchUpdatesTo(mRecyclerAdapter);
}
这里我们进行一些操作，来该改变数据源某些数据。请注意的是：所有的操作都必须在Adapter的数据源进行操作，否则这里刷新完全没有意义。正如上面的实现，在变换之前,我先将源数据深拷贝到oldDataList数组，然后所有的变化操作都在mDataList数组(因为它是Adapter的数据源，操作它才有意义)，然后将改变之后的数据称为newDataList。
如下便是DiffUtil的真正使用:
RecyclerItemCallback recyclerItemCallback = new RecyclerItemCallback(oldDataList, newDataList);
DiffUtil.DiffResult diffResult = DiffUtil.calculateDiff(recyclerItemCallback, false);
diffResult.dispatchUpdatesTo(mRecyclerAdapter);
上面便是使用DiffUtil的固定步骤：显示创建ItemCallback的对象，然后通过DiffUtil的calculateDiff方法来进行差量计算，最后就是调用dispatchUpdatesTo方法进行notify操作。
整个过程还是比较简单的，我们来看看展示效果：
了解完DiffUtil是怎么使用，接下来我们将正式
DiffUtil的差量计算算法，如果还有同学不明白DiffUtil怎么使用，可以到我的github下载上面的Demo： DiffUtilDemo。
3. Myers算法
DiffUtil进行差量计算采用的是著名的Myers算法。对于我们这种移动开发的菜逼，很少接触到算法，所以知道这个算法的同学应该比较少，况且还深入了解它。当然大家不要怕，本文会详细的介绍Myers算法，包括它的理论和实现。放心吧，这个算法比较简单，我觉得比看毛片算法还简单。
本部分的大部分内容来自于Investigating Myers' diff algorithm: Part 1 of 2这篇文章，有兴趣的同学可以直接看这篇文章。
(1). 定义概念
我们先来简单分析一下我们需要达到的目的。比如说有A数组和B数组，我们想要达到的目的就是，从A数组变成B数组，分别要进行哪些操作。这些操作里面无非是remove和add（在这里，move操作和change操作我们将拆分为remove和add操作），这里就让我想起来算法题中一道题是编辑距离。编辑距离的意思就是：从A字符串变成B字符串的最小操作步数，这里的操作就是上面的两种操作，有兴趣的可以看我之前的一篇文章：Java 算法-编辑距离(动态规划)。
我们就可以求解从A数组变成B数组的问题转换成为求解从A字符串变成B字符串的问题(其实，字符串就是字符数组)。
我们一步一步的分析这个问题，我们假设A字符串为ABCABBA，B字符串为CBABAC。然后我们可以得到下面的一个二维数组（如下的软件连接：DiffTutorial）。
从上面的图片中，我们可以看出来，我们假设X轴是原字符串，Y轴是新字符串。其中，这个问题的目的就是我们需要从点(0,0)(原点)到点(m,n)（终点）的最短路径，学过基本算法的同学应该都知道，这个就是回溯法的基本操作。
然后我们在来看一张图片：
这张图片相对于上面的图片，就是多了一些对角线。我们知道要想求解从(0,0)到(m,n)的最短路径，我们只能往右或者往下走，因为往上或者往左走都是在绕路。而多了对角线之后，我们还可以走对角线，如果能走对角线，相对于往右或者往下走的话，就更加的近了。那这些对角线的是按照什么规则画出来的呢？
其实非常的简单，我们就从左往右，从上往下扫描整个二维数组，如果当前位置的x表示的字符跟y表示的字符相同的话，就画一条对角线(从左上到右下)。从这里，我们就可以看出来，我们想要的答案就是路径里面尽可能包含多的对角线。
这里，我们简单的定义一下，向右走一个格子或者向下走一个格子表示一步，而走一条对角线不计入步数。
我们假设向右移动一步表示从A字符串中remove删除一个字符，向下移动一步表示向B字符串add一个字符。
在分析寻找路径的算法之前，我们先来定义几个概念：
- snakes:一个snake表示向右或者向下走了一步，这个过程包括n个对角线。
- k lines: k lines表示长的对角线，其中每个k = x - y。假设一个点m(m,n),那么它所在的k line值为m - n。如图：
其中橙色线表示偶数k line，棕色线表示奇数k line。- d contours：每条有效路径(能从(0,0)到(m,n)的路径都称为有效路径)的步数。形象点，一条path有多个snake组成，这里
d contours表示snake的个数。
如上就是我们定义几个概念。其中，如果向右走的话，k会+1，向下走，k会-1。
(2). 算法
我们想要的答案寻找最短的有效路径，那么就是寻找d contours最小的路径。那么我们很容易的能实现一个循环，用来找到最小路径：
for ( int d = 0 ; d <= m + n ; d++ )
我们从0开始遍历，只要能第一次找到有效路径，那么这条路径就是我们需要的答案。那么最大值为什么是m + n呢？假设这个过程没有对角线，只能向下或者向右走，那么最终会有m + n 个snake(向下一步或者向右一步就是一个snake)，所以d的最大值是 m + n。
而在内循环里面，我们需要遍历在每种d值，经过了哪些k lines，所以内循环应该来遍历k lines。这里我先将内循环的代码写出来，然后再解释几个问题。
for ( int k = -d ; k <= d ; k += 2 )
从上面的代码中，我们会有2个问题：
- 为什么 k的范围是[-d, d]？
- 为什么k每次+2，而不是+1？
针对上面的问题，我进行一一的解答。首先来看看第一个问题。
k = -d，全部都向下走，因为一共d步，一共会向下走d步，所以k为-d(向下走，k会-1)；当然，k = d就表示全部都向右走。
再来看看第二个问题吧。
根据我们的观察，如果终点所在的k line是偶数，那么最终的步数d也是偶数，反之亦然。这几句话是什么意思呢？这样来说吧，如果我们经过d步就能到达终点，那么如果d为偶数，终点所在k line也为偶数，奇数也是一样的道理。所以k直接+2就行了，不用加1。
理解了这些的问题，现在我们需要解决的问题是，给定一个k值，怎么来寻找有效路径？
给定的k值，我们从k + 1向下移动一步或者从k - 1向右移动一步，然后我们就可以基于这个规则来解决我们的问题。
这里，我们用一个例子来看一下具体是怎么解决问题的。
A. 假设d = 3
如果d为3，那么k的取值范围是[-3，-1，1，-3] (根据上面的内循环得到的)。为了方便理解，我将所有的snake记录成一张表，如图：
接下来，我们将分情况来讨论不同值的k。
- k = -3：这种情况下，只有当k = -2，d = 2时，向下移动一步(k = -4, d = 2这种情况不存在)。所以，我们可以这么来走，从(2,4)点开始向下走到(2,5),由于(2,5)和(3,6)之间存在一个对角线，可以走到(3,6)。所以着整个snake是：(2,4) -> (2,5) -> (3,6)。
- k = -1：当k = -1时，有两种情况需要来讨论：分别是k = 0，d = 2向下走；k = -2 ，d = 2向右走。
当k = 0，d = 2时，是(2,2)点。所以当从(2,2)点向下走一步，到达(2,3),由于(2,3)没有对角线连接，所以整个snake是：(2,3) -> (2,4)。
当k = -2 ，d = 2时，是(2,4)点。所以当从(2,4)点向右走一步，到达(2,5)，由于(2,5)与(3,6)存在对角线，所以整个snake是：(2,4) -> (2,5) -> (3,6)。
在整个过程中，存在两条snake，我们选择是沿着k line走的最远的snake，所以选择第二条snake。- k = 1：当k = 1时，存在两种可能性，分别是从k = 0向右走一步，或者k = 2向下走一步，我们分别来讨论一下。
当k = 0，d = 2时，是(2,2)点。所以当从(2,2)向右走一步，到达(3,2),由于(3,2)与(5,4)存在对角线，所以整个snake是：(2,2) ->(3,2) ->(5,4)。
当k = 2，d = 2时，是(3,1)点。所以当从(3,1)向下走一步，到达(3,2)。所以这个snake是：(3,1) ->(3,2) ->(5,4)。
在整个过程中，存在两条snake，我们选择起点x值较大的snake，所以是：(3,1) ->(3,2) ->(5,4)。- k = 3：这种情况下，(k = 4， d = 2)是不可能的，所以我们必须在(k = 2，d = 2)时向右移动一步。当k = 2, d = 2时， 是(3,1)点。所以从(3,1)点向右移动一步是(4,1)点。所以整个snake是：(3,1) -> (4,1) -> (5,2).
B. 算法实现
整个过程我们是很明白了，但是怎么用代码来实现整个过程呢？
需要我们知道的是，d(n)的计算基于d(n - 1)的计算，同时对于每个偶数d，我们在偶数k line上面去寻找snake的终点，当然这个寻找过程是基于上一条snake在奇数k line上面的终点(因为k 是从k - 1或者 k + 1,推导出来，如果k为偶数，那么k - 1和k + 1肯定为奇数)。
我们假设一个V数组，其中k作为它的index，x作为它的值，y值可以由x 和k推导出来(k = x - y)。同时给定一个d值，k的范围是 [-d, d],这个可以限制V数组的值的大小。
我们必须从d = 0开始，所以我们假设V[1] = 0,这个表示(k = 1，x = 0),所在点是(0, -1)。我们必须从(0, -1)向下移动，从而保证(0,0)是必经之地。
V[ 1 ] = 0;
for ( int d = 0 ; d <= N + M ; d++ )
{
for ( int k = -d ; k <= d ; k += 2 )
{
// down or right?
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
int kPrev = down ? k + 1 : k - 1;
// start point
int xStart = V[ kPrev ];
int yStart = xStart - kPrev;
// mid point
int xMid = down ? xStart : xStart + 1;
int yMid = xMid - k;
// end point
int xEnd = xMid;
int yEnd = yMid;
// follow diagonal
int snake = 0;
while ( xEnd < N && yEnd < M && A[ xEnd ] == B[ yEnd ] ) { xEnd++; yEnd++; snake++; }
// save end point
V[ k ] = xEnd;
// check for solution
if ( xEnd >= N && yEnd >= M ) /* solution has been found */
}
}
上面的代码寻找一条到达终点的snake。因为V数组里面存储的是在k line最新端点的坐标，所以为了寻找到所有的snake，我们在d的每次循环完毕之后，从d(Solution)遍历到0。如下：
List<int[]> Vs; // saved V's indexed on d
List<Snake> snakes; // list to hold solution
Point p = new Point(n, n); // start at the end
for ( int d = vs.Count - 1 ; p.X > 0 || p.Y > 0 ; d-- )
{
int[] V = Vs[d];
int k = p.X - p.Y;
// end point is in V
int xEnd = V[k];
int yEnd = x - k;
// down or right?
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
int kPrev = down ? k + 1 : k - 1;
// start point
int xStart = V[ kPrev ];
int yStart = xStart - kPrev;
// mid point
int xMid = down ? xStart : xStart + 1;
int yMid = xMid - k;
snakes.Insert( 0, new Snake( /* start, mid and end points */ ) );
p.X = xStart;
p.Y = yStart;
}
Investigating Myers' diff algorithm: Part 1 of 2文章是用C#写的，我这里将它简单改写称为Java。
为什么这里会倒着来遍历，也就是说，为什么从最后一条snake遍历到第一条snake呢？最后一条snake肯定是我们想要的有效路径的必经之路，所以倒着来寻找snake，肯定是找到的snake都是在有效路径上，因为Vs数组里面还有其他情况下的snake。
4. DiffUtil的实现
(1). DiffUtil生成DiffResult
我相信，经过上面的理解，大家在看DiffUtil的算法时，应该都能明白。DiffUtils代码实现主要集中在diffPartial方法里面。
diffPartial方法主要是来寻找一条snake，它的核心也就是Myers算法，这里我们将不分析了。calculateDiff方法是不断的调用diffPartial方法，然后将寻找到的snake放入一个数组里面，最后就是创建一个DiffResult对象，将所有的snake作为参数传递过去。
在DiffResult类的内部，分别有两个数组来存储状态，分别是：mOldItemStatuses,用来的旧Item的状态；mNewItemStatuses,用来存储新Item的状态。那么这两个数组是在哪里被赋值呢？答案就在findMatchingItems方法(在DiffResult的构造方法里面调用)：
private void findMatchingItems() {
int posOld = mOldListSize;
int posNew = mNewListSize;
// traverse the matrix from right bottom to 0,0.
for (int i = mSnakes.size() - 1; i >= 0; i--) {
final Snake snake = mSnakes.get(i);
final int endX = snake.x + snake.size;
final int endY = snake.y + snake.size;
if (mDetectMoves) {
while (posOld > endX) {
// this is a removal. Check remaining snakes to see if this was added before
findAddition(posOld, posNew, i);
posOld--;
}
while (posNew > endY) {
// this is an addition. Check remaining snakes to see if this was removed
// before
findRemoval(posOld, posNew, i);
posNew--;
}
}
for (int j = 0; j < snake.size; j++) {
// matching items. Check if it is changed or not
final int oldItemPos = snake.x + j;
final int newItemPos = snake.y + j;
final boolean theSame = mCallback
.areContentsTheSame(oldItemPos, newItemPos);
final int changeFlag = theSame ? FLAG_NOT_CHANGED : FLAG_CHANGED;
mOldItemStatuses[oldItemPos] = (newItemPos << FLAG_OFFSET) | changeFlag;
mNewItemStatuses[newItemPos] = (oldItemPos << FLAG_OFFSET) | changeFlag;
}
posOld = snake.x;
posNew = snake.y;
}
}
findMatchingItems方法的具体细节这里我们就不讨论了，其中findMatchingItems方法只做一件事情：更新mOldItemStatuses和mNewItemStatuses数组。同时如果mDetectMoves为true，会计算move的操作，通常来说，我们都会设置为true。
当这里我们对DiffUtil生成DiffResult的过程已经了解的差不多了，加下来，我们在讨论一个方法就是dispatchUpdatesTo方法
(2). DiffResult和Adapter
整个DiffResult构造完成之后，就需要将整个变化过程作用于Adapter的更新，也就是dispatchUpdatesTo方法调用。
public void dispatchUpdatesTo(ListUpdateCallback updateCallback) {
final BatchingListUpdateCallback batchingCallback;
if (updateCallback instanceof BatchingListUpdateCallback) {
batchingCallback = (BatchingListUpdateCallback) updateCallback;
} else {
batchingCallback = new BatchingListUpdateCallback(updateCallback);
// replace updateCallback with a batching callback and override references to
// updateCallback so that we don't call it directly by mistake
//noinspection UnusedAssignment
updateCallback = batchingCallback;
}
// These are add/remove ops that are converted to moves. We track their positions until
// their respective update operations are processed.
final List<PostponedUpdate> postponedUpdates = new ArrayList<>();
int posOld = mOldListSize;
int posNew = mNewListSize;
for (int snakeIndex = mSnakes.size() - 1; snakeIndex >= 0; snakeIndex--) {
final Snake snake = mSnakes.get(snakeIndex);
final int snakeSize = snake.size;
final int endX = snake.x + snakeSize;
final int endY = snake.y + snakeSize;
if (endX < posOld) {
dispatchRemovals(postponedUpdates, batchingCallback, endX, posOld - endX, endX);
}
if (endY < posNew) {
dispatchAdditions(postponedUpdates, batchingCallback, endX, posNew - endY,
endY);
}
for (int i = snakeSize - 1; i >= 0; i--) {
if ((mOldItemStatuses[snake.x + i] & FLAG_MASK) == FLAG_CHANGED) {
batchingCallback.onChanged(snake.x + i, 1,
mCallback.getChangePayload(snake.x + i, snake.y + i));
}
}
posOld = snake.x;
posNew = snake.y;
}
batchingCallback.dispatchLastEvent();
}
dispatchUpdatesTo方法看上去比较难，其实表达的意思非常简单，就是根据不同的状态调用Adapter不同的方法。这里不同的就是，没有直接调用Adapter的方法，而是使用了适配器模式，用AdapterListUpdateCallback来包裹了一下Adapter，然后通过AdapterListUpdateCallback的方法来调用Adapter的方法。
这样做有什么好处呢？在DiffUtil看到的不是Adapter，而是ListUpdateCallback接口，所以后面如果Adapter的API有啥变化，可以只改AdapterListUpdateCallback类，而不用更改DiffUtil类。这样做非常的友好，同时我们在这里可以学习到两点：
- 适当的使用适配器模式，将一些操作封装到适配器类里面，当依赖类的API有所改变，我们只需改变适配器类就行，而不用更改那么复杂的类，因为复杂类更改起来非常的麻烦。在这里，依赖类是
Adapter,复杂类是DiffUtil。- 如果使用一个类，但是必须保证这个类实现某个接口。我们不妨使用适配器模式，设计一个适配器类来实现接口，在适配器操作想要使用的那个类。这样能避免每个类去实现没必要的接口，在这里
Adapter就没必要实现ListUpdateCallback的接口，所以可以使用适配器模式来包裹一下Adapter就行了。
5. 总结
到这里，我们对DiffUtil的算法已经有一定的理解了，最后，我再对此进行简单的总结。
DiffUtil应开发者的需求产生，我们应该去使用并且理解它。DiffUtil的差量计算采用的是Myers算法，具体的算法分析可以参考上面的描述。- 适当的使用适配器模式，可以减少一个类去实现一些没必要的接口。
如果不出意外的话，接下来我将分析LayoutManager。
网友评论