这篇文章分为两部分
一：RecyclerView中的DiffUtil
二：Myers差分算法
本文重点介绍Myers差分算法，如果对DiffUtil有一定了解的同学请直接跳到第二批部分。
一：RecyclerView中的DiffUtil
不论是在哪一款App应用中，一旦提到数据集合，展示的方式通常是listview或者gridview，亦或是recyclerview。
DiffUtil就是专门用于RecyclerView中数据有局部变化。使用DiffUtil时会计算出新旧集合中的最长公共子串，之后对数据集合进行增减，再进行局部变化。
为什么要进行局部变化，而不是直接调用adapter.notifyDataSetChanged？
局部更新会有动画。动画。。画。。。
DiffUtil适用于数据频繁变化、需要动态显示增减情况、新旧数据有重合部分的情况，这种情况大力推荐DiffUtil。
当我们使用DiffUtil的时候我们需要重写它的4个方法，分别为：
getOldListSize() //看名字就懂的方法
getNewListSize()
areItemsTheSame() //根据你的需求去判断到底是刷新整个item(viewType不同的情况)，还是该item只有一点点数据的变化，从而去下面的方法判断是否需要刷新.如果返回true，将继续执行下面的方法去判断。
areContentsTheSame():如果返回true，则不刷新该item，如果返回false，则只刷新该item，并且是一个动作非常小的刷新
光看这些概念会比较抽象
old Data A[] = {ABCABBA} 长度（N=7）
new Data B[] = {CBABAC} 长度（M=6）
这里的展示比较简单，只展示出这个字母就行了，如图
那么我的代码应该是这样的
public int getOldListSize() {returnoldData==null?0:oldData.size();}
public int getNewListSize() {returnnewData==null?0:newData.size();}
public boolean areItemsTheSame(intoldItemPosition,intnewItemPosition) {
return oldData.get(oldItemPosition).equals(newData.get(newItemPosition));
}//该方法要返回item身份的唯一标识，例如id，如果相同进入下面方法，如果不同则应该进行增减操作
public boolean areContentsTheSame(intoldItemPosition,intnewItemPosition) {
return oldData.get(oldItemPosition).equals(newData.get(newItemPosition));
}//当id相同时，再判断需要展示的内容是否相同，如果不同，则对item进行update
最终将计算结果展现到recyclerview中的方法如下
DiffUtil.DiffResult diffResult = DiffUtil.calculateDiff(adapter.newItemChangeCallBack(adapter.getData(), datas));
diffResult.dispatchUpdatesTo(adapter);
效果图
好奇心重的小伙伴肯定要问了：如何又快又准确地计算出最大重合部分（最长公共子串）？
二：Myers差分算法
前阵子因为产品需求，我手动实现了对旧数据集合的增量维护，后发现有DiffUtil工具，遂想要查看google的大牛们是如何实现的，就对源码进行了查阅。发现其核心代码就是实现Myers差分算法来达到目的。我们先将part1中的数据填充到一个二维数组中，当两个数据相同时，我们用方向为右下的对角线来表示。得到如下
x轴方向为旧数据，y轴方向为新数据
那么这个算法的核心就成了如何从使用最少的步数从起点（0,0）走到终点（n,m）让这条线中尽可能多地包含对角线。并且我们不走回头路哈。
你现在很可能一头雾水。
先来看看从一个点向下，向右，按对角线走分别代表什么？我们只分析从（0,0）到（1,1）。
要强调一个事情：x轴方向为旧数据，y轴方向为新数据。
向下（0,0）->(0,1) ：新增一个元素 （计1步）
向右（0,0）->(1,0)：删除一个元素 （计1步）
走对角线：相同元素 （不计入步数）
先把上面这三种走法代表的意义想清楚，我们再继续往下看
思考：使用何种算法才能达到目的？
针对这个问题我能想到两种解决方案
1.广搜，同时记录步数，当搜到（n，m）点时即为所求，很基础的一种解决方案，如何记录路径点留给大家做一个思考
2.动态规划。当一个问题（1）依赖于子问题的最优解，（2）子问题重叠，（3）问题存在边界，（4）子问题独立，就可以考虑使用动态规划来解决。该问题中，点（n，m）的最优解依赖于（n，m-1），（n-1，m）两个点所在对角线上所有能够走一步到达（n，m）的点。 ////请理解后继续
下面就要介绍Myers差分算法了。
首先我们再来重复一遍：该问题中，点（n，m）的最优解依赖于（n，m-1），（n-1，m）两个点所在对角线上所有能够走一步到达（n，m）的点。
我们提取出关键词：对角线，一步
在这个基础上，我们提出三个概念
snake : 一条snake代表走一步。例如从(0,0)->(0,1) (0,0)->(1,0) (0,1)->(0,2)->(2,4)这分别为三条snake。上述提到过，走对角线不计入步数。最后一条蛇中的三个点分别为start，mid，end
k line: 定义k = x - y 怎么冒出来的这个k？ 所有k相同的点组成了一条线，他们组成了对角线。并且对于k，我们可以使用一个记录的数组V，用k作为该数组的index，x为value，这样我们可以通过计算求得y坐标
d contour: 这又是什么？ 我认为d可以简单的理解为步数。
那么现在这个问题就成了，如何找到一个最小的d使snakes到达点（n，m）。相信你已经看出来这是最外层的循环了。
接下来我们想想如何到达point（x，y）？ 设 k = x - y，那么能到达点（x，y）的 只能从k-1 或者 k+1两条对角线上到k上。相信你发现这是内侧循环了。
只要这两层循环就够了，内层循环完毕的结果就是，在步数为d，求得对角线k能到达的最远的x坐标。
贴上一张样例的图，然后继续举栗子
黄色的线：k line
深蓝色的线：snake
浅蓝色的线：d contour
红色的线：问题的解
举例：when d = 3 ，k = [ -3 ,-1,1,3] 。 问两个问题
1,：为什么k要从-3开始？
2：[ 2 ， 0 ，-2]呢？
答
1.d表示步数为3步 ， 那么走3步是永远不可能走到k=±4的对角线上的，因为步数不够。只沿x 或者 y轴方向都无法到达。
2.当d为奇数步数时，意味着可以到达点（0 + i + diagonal，0 + j +diagonal） i+j 为奇数 ,diagonal为对角线数量，那么k = x - y = i - j 也一定是个奇数，所以当d为奇数，我们就只考虑k为奇数，当d为偶数，就只考虑d为偶数的情况即可。
我们继续
当k= -3 时，我们可以从k=-2 或者 k=-4到达k=-3，但是我们只可能从k=-2到k=-3（为什么？）。这里只能选走往下走 。这个时候我们只要知道当d=2 k=-2时候的前驱点（2,4）作为起点，往下走一步，到达点（2,5）设改点为mid和end，此时发现在对角线上，则将end移到（3,6）。这是边界情况
当k=-1时，我们有两个选择，从k=0 或者 k=-2 上的点作为前驱。我们当然选择点（2,4）因为它能让我们在k=-1时到达更远的点（3,4）.
k=1 k=3的情况请各位小伙伴自行脑补。
下面就可以列出我们的核心代码了
经过上述两层循环可以找到最快到达点（n，m）的步数
这里有个小问题需要注意，就是初始化的值非常重要，这里用数组V[k] = x 来做记录。在代码的开头V[1] = 0 计算出这个是当 k = 1 时 点（0，-1）作为起点，因为点（0,0）已然属于我们要考虑的范围。但是这个初始化并不是特别好理解。
我们也可以这样做初始化
while(A[ i ] = B[ i ]){ i ++; }
V[ 0 ] = i;
然后d从1开始，这样可能会比较好理解一些。
这段代码则是找出这条路径的方法，看得懂第一段代码，solution部分就不是问题。
以上就是全部内容了。我从思考的角度提出了snake d k 这三个定义，而不是直接提出这三个定义，然后硬往算法上靠。希望我的这种思维方式能够给你带来帮助。
我搜了一下国内并没有搜到Myers diff 算法，不知道是不是我搜的不对。
附国外的链接
https://www.codeproject.com/articles/42279/investigating-myers-diff-algorithm-part-of
和Myers的论文
http://xmailserver.org/diff2.pdf
欢迎各位和我继续探讨细节。
网友评论