Android学习笔记07-Android列表中的DiffUtils

Posted by panthole on 2021-08-18

一、背景

Android列表使用了v7包下DiffUtils来计算新旧数据集的差异集合,再刷新页面上的指定坑位,以此避免因notifyDataSetChanged带来的掉帧,但我们不能抱着仅仅会用的思想,不能仅仅只知其然不知其所以然。所以写了篇文章来讲解Myers差分异算法

二、Diff的定义

我们先简单定义一下什么是diff:diff就是目标文本和源文本之间的区别,也就是将源文本变成目标文本所需要的操作。

git为我们生成的diff是很直观易懂的,一看就知道我们对文件进行了哪些改动。但是,实际上,diff生成是一个非常复杂的问题

举个简单的例子,源数据集为ABCABBA,目标数据集为CBABAC,他们之间的diff其实有无穷多种,比如

img

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。

img

我们从坐标(0, 0)开始,此时,d=0k=0,然后逐步增加d,计算每个k值下对应的最优坐标。

因为每一步要么向右(x + 1),要么向下(y + 1),要么就是对角线(x和y都+1),所以,当d=1时,k只可能有两个取值,要么是1,要么是-1

d=1k=1时,最优坐标是(1, 0)

d=1k=-1时,最优坐标是(0, 1)

因为d=1时,k要么是1,要么是-1,当d=2时,表示在d=1的基础上再走一步,k只有三个可能的取值,分别是-202

d=2k=-2时,最优坐标是(2, 4)

d=2k=0时,最优坐标是(2, 2)

d=2k=2时,最优坐标是(3, 1)

以此类推,直到我们找到一个dk值,达到最终的目标坐标(7, 6)

四、差分异算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
function myers(stra, strb) {
let n = stra.length
let m = strb.length

//记录的是在k线上 能够走动的最优最表的X值,也能通过该集合推导出,每个最有坐标的x,y,k的值
let v = {
'1': 0
}
//记录的是每走一步,走过的(x,y)坐标的集合
let vs = {
'0': { '1': 0 }
}
let d

loop:
for (d = 0; d <= n + m; d++) {
let tmp = {}

for (let k = -d; k <= d; k += 2) {
//判断是向右走 还是向下走
let down = k == -d || k != d && v[k + 1] > v[k - 1]
//取出上一步对应的k线
let kPrev = down ? k + 1 : k - 1

//取出上一步对应的k线走到的最大值X值
let xStart = v[kPrev]
//取出上一步对应的k线走到的最大值Y值
let yStart = xStart - kPrev

//计算出当前k线的x,y的值
let xMid = down ? xStart : xStart + 1
let yMid = xMid - k

let xEnd = xMid
let yEnd = yMid

//如果当前步数对应的k线下有坐标(xEnd,yEnd)使得两个集合的值相等,说明可以向对角线,那么x,y各加1.
while(xEnd < n && yEnd < m && stra[xEnd] === strb[yEnd]) {
xEnd++
yEnd++
}
//把当前步数线当前k线的最大值更新
v[k] = xEnd
tmp[k] = xEnd

if (xEnd == n && yEnd == m) {
vs[d] = tmp
let snakes = solution(vs, n, m, d)
printRes(snakes, stra, strb)

break loop
}
}

vs[d] = tmp
}
}

function solution(vs, n, m, d) {
let snakes = []
let p = { x: n, y: m }

//倒推开始
for (; d > 0; d--) {
//取出步数为d时所走过的x,y的坐标集合
let v = vs[d]
//取出步数为d-1时所走过的x,y的坐标集合
let vPrev = vs[d-1]
//计算出当前k线值
let k = p.x - p.y

//取出当前步数下 斜线为k时 x的最大坐标
let xEnd = v[k]
//计算出取出当前步数下 斜线为k时 y的值
let yEnd = xEnd - k
//计算当前步,当前k线下 它是从上一步 向右还是向下过来的
let down = k == -d || k != d && vPrev[k + 1] > vPrev[k - 1]
//那么就知道了上一步的k线值
let kPrev = down ? k + 1 : k - 1

//取出当前步数下开始x值
let xStart = vPrev[kPrev]
let yStart = xStart - kPrev

//计算出当前步数下的中间x值
let xMid = down ? xStart : xStart + 1
let yMid = xMid - k

//收集每一步走的线的 开始,中间,终点的X值
snakes.unshift([xStart, xMid, xEnd])

p.x = xStart
p.y = yStart
}

return snakes
}

function printRes(snakes, stra, strb) {
let grayColor = 'color: gray'
let redColor = 'color: red'
let greenColor = 'color: green'
let consoleStr = ''
let args = []
let yOffset = 0

snakes.forEach((snake, index) => {
let s = snake[0]
let m = snake[1]
let e = snake[2]
let large = s

if (index === 0 && s !== 0) {
for (let j = 0; j < s; j++) {
consoleStr += `%c${stra[j]}`
args.push(grayColor)
yOffset++
}
}

// 删除
if (m - s == 1) {
consoleStr += `%c${stra[s]}`
args.push(redColor)
large = m
// 添加
} else {
consoleStr += `%c${strb[yOffset]}`
args.push(greenColor)
yOffset++
}

// 不变
for (let i = 0; i < e - large; i++) {
consoleStr += `%c${stra[large+i]}`
args.push(grayColor)
yOffset++
}
})

console.log(consoleStr, ...args)
}

let s1 = 'ABCABBA'
let s2 = 'CBABAC'
myers(s1, s2)

五、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哪里会有这么大的列表呢,顶多上千,想过万条数据都难,所以数据量也不用担心