玩转React系列2:寻找更高效的列表更新算法

本文接着上篇《玩转React系列1:React工作原理》最后提到的React列表更新的问题,来深入探讨下是否有更高效的列表更新方式。

目录

  • 0. 问题描述
  • 1. 寻找更高效的方法
  • 2. benchmark

问题描述

上一篇文章最后提到,React更新算法有一个问题,就是选取的不动子列表S可能不是最长的。比如将S1中的最后一个元素en移动到第一个元素e1前面,变成S2的情况。React选取的不动子列表只包含最后一个元素en,所以需要移动其他n-1个元素。但实际上可以将[e1, …, en-1]作为不动子列表,从而只需要做一次移动操作,也就是将en移动到e1的前面。

本文尝试探索一种新的方法,来减少元素移动的次数。以及做一个基准测试来确定使用新的方法是否更省时。

寻找更高效的方法

为了更清晰的讨论这个问题,我们先做一个合理的假设,假设从列表S1(prevChildren)到列表S2(nextChildren),只是子元素的顺序变了,没有新增和删除子元素。这个假设是合理的,因为不管是哪种更新方式,新增和删除的操作都是一样的,不会影响算法复杂度。另外为了描述方便,假设S1和S2中的元素由该元素在S1中的位置(下标)代替,比如如果S1为d、c、a、b,S2为b、a、d、c。换成下标S1就是0、1、2、3(即d在S1中的位置、c在S1中的位置、a在S1中的位置、b在S1中的位置),S2就是3、2、0、1(即b在S1中的位置、a在S1中的位置、d在S1中的位置、c在S1中的位置)。

首先我们将S2中的n个元素分成k个列表,分的方式是先把S2中第一个元素作为列表的第一个元素,然后顺序判断S2后面的元素,如果遇到的元素小于当前列表的最后一个元素,则将其添加到当前列表后面。S2中的元素全部判断完后,从S2中移除掉在当前列表中的元素。然后进行下一轮同样的操作,直到S2中的元素全部被移除。比如S2为5、1、3、2、0、4,则可以分成3个列表,第一个为5、1、0,第二个为3、2,第三个为4。分的过程如下:

初始S2为 5、1、3、2、0、4
第一轮找到的列表为 5、1、0
移除掉找到的元素后S2为 3、2、4
第二轮找到的列表为 3、2
移除掉找到的元素后S2为 4
第三轮找到的列表为 4

然后就可以从分成的每个列表中找到一个元素,构成我们所要找的最长子列表。找的方式是这样子的:将最后一个列表的第一个元素作为最长子列表的最后一个元素,然后依次往前,在前一个列表中从前往后找到第一个小于这个元素的元素作为当前元素的前一个元素。以上面找到的3个列表为例,过程如下:

第三个列表 4
所以找到的元素为 4(列表中的第一个元素)
第二个列表 3、2
所以找到的元素为 3(列表中第一个小于4的元素)
第一个列表 5、1、0
所找到的元素为 1(列表中第一个小于3的元素)
所要找的最长子列表为 1、3、4(将找到的元素反过来)

有几个点需要证明:

  1. 最长子列表中的元素一定来自于所分成的不同列表,最长子列表的长度一定小于等于k
  2. 按照上面方式找到的最长子列表中元素的先后顺序跟S2中这些元素的先后顺序一致

证明:

  1. 按照定义,分成的每一个列表中元素的先后顺序,跟S2中这些元素的先后顺序一致,但是跟S1中这些元素的先后顺序相反。而最长子列表中元素的先后顺序要满足跟S2和S1中这些元素的先后顺序都一致。如果最长子列表有超过一个元素来自于同一个列表,则来自同一个列表的这几个元素是按照从大到小排列的。但是上面对S1的假设确定了S1中的元素是按照从小往大排列的,矛盾了。所以最长子列表中的元素一定来自于不同的列表,所以最长子列表的长度一定小于等于k。
  2. 根据最长子列表和S2分成的列表的定义,假设找到的某个列表中的元素为a,找到的该列表的上一个列表中的元素为b,则a大于b,所以也就是要证明在S2中a排在b的后面。如果a排在b的前面且a大于b,但是上一个列表中只包含b而不包含a,这说明上一个列表中包含一个小于a但是大于b的元素c,且c排在a的前面。如果是这样的话,那么找到的上一个列表中的元素应该是c而不是b,因为c和b都在上一个列表中且c排在b的前面。所以a只能排在b的后面,因此得到的最长子列表中元素的先后顺序跟S2中这些元素的先后顺序一致。

有了上面的定义,寻找最长子列表的步骤可以分成两步。一是将S2按照上面的分法分成k个列表。二是从这k个列表的最后一个列表开始,从每个列表中取出一个元素,就组成了所要找的最长子列表。

算法实现如下(主要的优化点在如何将S2分成k个列表上面,详情请看注释):

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
function getBestList (S2) {
// 1. 将S2分成k个列表,时间复杂度O(nlogn)
let levelList = [
[S2[0]]
]
for (let i = 1; i < S2.length; i += 1) {
let x = S2[i]

// 二分法查寻找刚好比x大的那个列表,
let start = 0
let end = levelList.length - 1
// 中间位置
let mid = Math.floor((start + end) / 2)
// 中间位置对应的列表
let level = levelList[mid]
// 列表的最小值
let min = level[level.length - 1]
do {
if (x < min) {
// 如果当前元素小于中间列表的最后一个元素,
// 说明x应该添加到start~mid中的某一个列表中
// 所以缩小范围,从start~mid的列表中寻找
end = mid
} else {
// 如果当前元素大于中间列表的最后一个元素,
// 说明x不可能添加到start~mid中的任何一个列表中
// 所以缩小范围,从mid+1~end的列表中寻找
start = mid + 1
}
mid = Math.floor((start + end) / 2)
level = levelList[mid]
min = level[level.length - 1]
} while (start < end)

if (x < min) {
// 如果停留在的那个列表的最后一个元素大于x,则将x添加到这个列表最后
levelList[start].push(x)
} else {
// 如果大于,说明没有合适的列表可以添加x进去,则在后面新增一个列表并添加x
levelList.push([x])
}
}

// 2. 从这k个列表中获取最长子列表,时间复杂度O(n)
let best = [
levelList[levelList.length - 1][0] // 最后一个列表的第一个元素
]
for (let i = levelList.length - 2; i >= 0; i -= 1) {
let level = levelList[i]
for (let j = 0; j < level.length; j += 1) {
let x = level[j]
if (x < best[best.length - 1]) {
// 第一个小于之前找到的元素
best.push(x)
break
}
}
}
// 元素顺序要反转一下
best.reverse()
return best
}

用例:

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
let S1 = [0, 1, 2, 3, 4, 5]
let S2 = [5, 1, 3, 2, 0, 4]
let best = getBestList(S2)

console.log(`S1: ${S1}`)
console.log(`S2: ${S2}`)
console.log(`最长子列表为:${best}`)
console.log(`所以进行${S1.length - best.length}次移动可以将S1转换为S2:`)
let actions = []
for (let i = 0; i < S2.length; i += 1) {
let x = S2[i]
if (best.indexOf(x) === -1) {
if (i === 0) {
moveBefore(x, S2[i + 1], S1)
actions.push(`将S1中的${x}移动到${S2[i + 1]}的前面,S1变为:${S1}`)
} else {
moveAfter(x, S2[i - 1], S1)
actions.push(`将S1中的${x}移动到${S2[i - 1]}的后面,S1变为:${S1}`)
}
} else {
actions.push(`${x}不需要移动,S1为:${S1}`)
}
}
actions.forEach((action) => {
console.log(` ${action}`)
})

运行输出如下:

1
2
3
4
5
6
7
8
9
10
S1: 0,1,2,3,4,5
S2: 5,1,3,2,0,4
最长子列表为:1,3,4
所以进行3次移动可以将S1转换为S2:
将S1中的5移动到1的前面,S1变为:0,5,1,2,3,4
1不需要移动,S1为:0,5,1,2,3,4
3不需要移动,S1为:0,5,1,2,3,4
将S1中的2移动到3的后面,S1变为:0,5,1,3,2,4
将S1中的0移动到2的后面,S1变为:5,1,3,2,0,4
4不需要移动,S1为:5,1,3,2,0,4

benchmark

上面提到的新算法虽然总是能找到最长子列表,但是花在寻找上的时间也更多。所以这里需要做一个benchmark,看看新算法所减少的元素移动时间寻找最长子列表的时间的大小关系。如果前者多于后者,说明新算法性能更好。

测试参数

【需要有一个测试实验结果】