一、背景
Android列表使用了v7包下DiffUtils来计算新旧数据集的差异集合,再刷新页面上的指定坑位,以此避免因notifyDataSetChanged带来的掉帧,但我们不能抱着仅仅会用的思想,不能仅仅只知其然不知其所以然。所以写了篇文章来讲解Myers差分异算法
二、Diff的定义
我们先简单定义一下什么是diff:diff就是目标文本和源文本之间的区别,也就是将源文本变成目标文本所需要的操作。
git为我们生成的diff是很直观易懂的,一看就知道我们对文件进行了哪些改动。但是,实际上,diff生成是一个非常复杂的问题
举个简单的例子,源数据集为ABCABBA
,目标数据集为CBABAC
,他们之间的diff其实有无穷多种,比如
diff定义的总结
- 最小的改动
- 删除优先新增
- 新增或删除的内容应该遵循代码结构
三、寻找最短路径
寻找最短路径的原则:
- 路径长度最短(对角线不算长度)
- 先向右,再向下(先删除,后新增)
名词解释
snake蛇形线—— 一条snake表示 横(竖)向移动一步后接跟着的尽可能多的斜向移动 组成的线
从(0, 1)移动到(0, 2)顺着斜线一直到(2, 4)组成一条snake
k线 ——定义 k = x - y, k相同的点组成一条直线,他们是相互平行的斜
d步长——移动的步长,走过的路
那么,现在的问题就是怎样寻找最短的直观的diff?假设字符串a= 'ABCABBA'
b = 'CBABAC'
a的长度记为N,这里N = 7,b的长度记为M,这里M = 6,图中每个点都可以对应一个坐标(x, y)
那么,图中每一条从左上角到右下角的路径,都表示一个diff。
我们从坐标(0, 0)
开始,此时,d=0
,k=0
,然后逐步增加d
,计算每个k
值下对应的最优坐标。
因为每一步要么向右(x + 1),要么向下(y + 1),要么就是对角线(x和y都+1),所以,当d=1时,k只可能有两个取值,要么是1
,要么是-1
。
当d=1
,k=1
时,最优坐标是(1, 0)
。
当d=1
,k=-1
时,最优坐标是(0, 1)
。
因为d=1时,k要么是1,要么是-1,当d=2时,表示在d=1的基础上再走一步,k只有三个可能的取值,分别是-2
,0
,2
。
当d=2
,k=-2
时,最优坐标是(2, 4)
。
当d=2
,k=0
时,最优坐标是(2, 2)
。
当d=2
,k=2
时,最优坐标是(3, 1)
。
以此类推,直到我们找到一个d
和k
值,达到最终的目标坐标(7, 6)
四、差分异算法代码
1 | function myers(stra, strb) { |
五、DiffUtil提升Android列表性能
DiffUtil计算两个列表之间的差异,并输出将第一个列表转换为第二个列表的更新操作列表,这里主要用于计算RecyclerView适配器的更新,DiffUtil使用Eugene W. Myers的差分算法来计算将一个列表转换为另一个列表的最小更新数。
然后来看看我们平常怎么写一个列表的,首先我们会创建一个RecyclerView,然后创建一个Adapter,然后把数据List塞给adapter,然后调用adapter的notifyDataSetChanged来更新UI,好了,这就是常用的方式,用这个方式倒是没什么问题,就是每次notifyDataSetChanged后会把整个列表刷一次,会把每个未回收的viewholder的onBindViewHolder重新调用一次,也就意味着这个方法里的代码重新执行一次,如果我们只有一个item有变化,这个成本确实稍微有点高,这时DiffUtil就可以站出来解决这个问题,它可以算出这个变化的item,然后只调用一个item的onBindViewHolder方法,如果这个能知道具体的差异,这个方法里面都不需要所有代码都执行,只执行需要变化的部分代码即可,onBindViewHolder其实有两个重载方法,有一个包含payload的方法先执行,这个payload就是差异数据,可以利用它来做局部刷新。
DiffUtil的用法这里不细聊,咱们主要关注一下DiffUtil的ItemCallback,它有几个方法可以重写:
1 | areItemsTheSame(这个方法比较两个item是否相同) |
1 | areContentsTheSame(areItemsTheSame返回true会进入这个方法) |
1 | getChangePayload(areContentsTheSame返回false会进入此方法,这里可以把具体的差异返回) |
如果列表比较简单可以直接使用谷歌的ListAdapter,稍微复杂点的可以自己定义一个Adapter,然后使用谷歌提供的AsyncListDiffer来显示和刷新列表,这个AsyncListDiffer类封装了DiffUtil类,如果这个类还想定制也可以自己写这个类来封装自己的DiffUtil的处理,建议还是自己封装一个adapter类会好点,谷歌提供的类太简单了。
最后看看这个DiffUtil的效率,这边引用谷歌的测试结果(测试机器是Android M的Nexus 5X)
- 100项和10项修改:平均:0.39毫秒,中值:0.35毫秒
- 100项和100项修改:3.82毫秒,中值:3.75毫秒
- 100个项目和100个修改而没有移动:2.09毫秒,中值:2.06毫秒
- 1000项和50项修改:平均:4.67毫秒,中位数:4.59毫秒
- 1000个项目和50个修改而没有移动:平均:3.59毫秒,中值:3.50毫秒
- 1000项和200项修改:27.07毫秒,中位数:26.92毫秒
- 1000个项目和200个修改而没有移动:13.54毫秒,中值:13.36毫秒
这个相当于低端机的机器跑出来都这么低了,现在的手机性能自然是比这个强多了,所以完全不用担心性能,最后提一点这个实现列表大小的限制是2 ^ 26,这个数据量达到了千万级,一般的app哪里会有这么大的列表呢,顶多上千,想过万条数据都难,所以数据量也不用担心