一、可能性(常见):
1.
旧的:a b c
新的:a b c d
2.
旧的:a b c
新的:d a b c
3.
旧的:a b c d
新的:a b c
4.
旧的:d a b c
新的:a b c
5.
旧的:a b c d e i f g
新的:a b e c d h f g
对应的真实虚拟节点(为方便理解,文中用字母代替):
// vnode对象
const a = {
type: 'div', // 标签
props: {style: {color: 'red'}}, // 属性
children: [], // 子元素
key: 'key1', // key
el: '', // 真实dom节点
...
}
二、找规律
去掉前面和后面相同的部分
// c1表示旧的子节点,c2表示新的子节点
const patchKeyedChildren = (c1, c2) => {
let i = 0
let e1 = c1.length - 1
let e2 = c2.length - 1// 从前面比
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
// 标签和key是否相同
// if (n1.type === n2.type && n1.key === n2.key)
if (n1 === n2) {
// 继续对比其属性和子节点
} else {
break
}
i++
}
// 从后面比
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
// 标签和key是否相同
// if (n1.type === n2.type && n1.key === n2.key)
if (n1 === n2) {
// 继续对比其属性和子节点
} else {
break
}
e1--
e2--
}
console.log(i, e1, e2)
}
// 调用示例
patchKeyedChildren(['a', 'b', 'c', 'd'], ['a', 'b', 'c'])
通过这个函数可以得到:
1.
旧的:a b c
新的:a b c di = 3e1 = 2e2 = 3
2.
旧的:a b c
新的:d a b ci = 0e1 = -1e2 = 0
3.
旧的:a b c d
新的:a b ci = 3e1 = 3e2 = 2
4.
旧的:d a b c
新的:a b ci = 0e1 = 0e2 = -1
5.
旧的:a b c d e i f g
新的:a b e c d h f gi = 2e1 = 5e2 = 5
扩展:
旧的:a b c
新的:a b c d e f
i = 3e1 = 2e2 = 5旧的:a b c
新的:a b c
i = 3e1 = 2e2 = 2旧的:e d a b c
新的:a b c
i = 0e1 = 1e2 = -1旧的:c d e
新的:e c d h
i = 0e1 = 2e2 = 3
从上面结果中我们可以找到规律:
- 当i大于e1时,只需添加新的子节点
- 当i大于e2时,只需删除旧的子节点
- 其它,特殊处理
// c1表示旧的子节点,c2表示新的子节点
const patchKeyedChildren = (c1, c2) => {
let i = 0
let e1 = c1.length - 1
let e2 = c2.length - 1// 从前面比
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
// 标签和key是否相同
// if (n1.type === n2.type && n1.key === n2.key)
if (n1 === n2) {
// 继续对比其属性和子节点
} else {
break
}
i++
}
// 从后面比
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
// 标签和key是否相同
// if (n1.type === n2.type && n1.key === n2.key)
if (n1 === n2) {
// 继续对比其属性和子节点
} else {
break
}
e1--
e2--
}
console.log(i, e1, e2)// 当i大于e1时
if (i > e1) {
if (i <= e2) {
while (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < c2.length ? c2[nextPos].el : null
// 添加子节点c2[i]在anchor的前面
// todo
i++
}
}
}
// 当i大于e2时
else if (i > e2) {
if (i <= e1) {
while (i <= e1) {
// 删除子节点c1[i]
// todo
i++
}
}
}
// 其它
else {
let s1 = i
let s2 = i
// 以新的子节点作为参照物
const keyToNewIndexMap = new Map()
for (let i = s2;
i <= e2;
i++) {
// 节点的key做为唯一值
// keyToNewIndexMap.set(c2[i].key, i)
keyToNewIndexMap.set(c2[i], i)
}
// 新的总个数
const toBePatched = e2 - s2 + 1
// 记录新子节点在旧子节点中的索引
const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
// 循环老的子节点
for (let i = s1;
i <= e1;
i++) {
const oldChild = c1[i]
// let newIndex = keyToNewIndexMap.get(oldChild.key)
let newIndex = keyToNewIndexMap.get(oldChild)
// 在新子节点中不存在
if (newIndex === undefined) {
// 删除oldChild
// todo
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1 // 永远不会等于0, 这样0就可以表示需要创建了
// 继续对比其属性和子节点
// todo
}
}console.log(newIndexToOldIndexMap)
// 需要移动位置
for (let i = toBePatched - 1;
i >= 0;
i--) {
let index = i + s2
let current = c2[index]
let anchor = index + 1 < c2.length ? c2[index + 1].el : null
if (newIndexToOldIndexMap[i] === 0) {
// 在anchor前面插入新的节点current
// todo
} else {
// 在anchor前面插入对应旧节点.el,current.el元素等于对应的旧节点.el(在其它代码中赋值了)
// todo
}
}
}}
// 调用示例
patchKeyedChildren(['a', 'b', 'c', 'd', 'e', 'i', 'f', 'g'], ['a', 'b', 'e', 'c', 'd', 'h', 'f', 'g'])
【vue3的diff算法】第1种和第2种比较简单,不做过多的讲解,我们来看看第3种,以下面为例
序号: 0 12 3 4 56 7
旧的:(a b) c d e i (f g)
新的:(a b) e c d h (f g)
1.前面a b和后面f g是一样的,会去掉,只剩中间乱序部分
2.以新的节点为参照物,循环旧的节点,从旧的节点中去掉新的没有的节点i
3.标记旧的中没有的节点(有就序号+1),0表示这个节点没有需要创建,为什么这里不用true或者false标记?算法优化
4+1 2+1 3+10
新的:(...)ecdh (...)
4.从后往前循坏,h为0,创建,放在在它下一个f前面;d不为0,复用旧的中的d,放在h前面;c不为0,复用旧的中的c,放在d前面;e不为0,复用旧的中的e,放在c前面
到目的为止,新旧元素的更替已经全部完成,但大家有没有发现一个问题,e c d h四个元素都移动了一次,我们可以看出如果只移动e和创建h,c和d保持不变,效率会更高
三、算法优化
1.
序号: 0 12 3 4 56 7
旧的:(a b) c d e i (f g)
新的:(a b) e c d h (f g)
对应的标记是[5, 3, 4, 0]2.
序号:0 1 2 3 4 5
旧的:c d e i f g
新的:e c d f g j对应的标记是[3, 1, 2, 5, 6, 0]
从上面两个例子中可以看出:
1的最优解是找到c d,只变化e h
2的最优解是找到c d f g,只变化e j
也就是从标记中我们要找到最长的递增子序列,然后通过最长的递增子序列找到对应的索引值,再通过索引值找到对应的值,注意0表示直接创建,不参与计算
如:[3, 1, 2, 5, 6, 0]的最长的递增子序列为[1, 2, 5, 6],对应的索引为[1, 2, 3, 4],然后我们遍历e c d f g j,标记中为0的,比如j,直接创建;c d f g索引分别等于1 2 3 4,保持不变;e等于0,移动
// 最长的递增子序列,https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr) {
const len = arr.length
const result = [0] // 以第一项为基准
const p = arr.slice() // 标记索引,slice为浅复制一个新的数组
let resultLastIndex
let start
let end
let middle
for (let i = 0;
i < len;
i++) {
let arrI = arr[i]
if (arrI !== 0) { // vue中等于0,表示需要创建
resultLastIndex = result[result.length - 1]
// 插到末尾
if (arr[resultLastIndex] < arrI) {
result.push(i)
p[i] = resultLastIndex // 前面的那个是谁
continue
}
// 递增序列,二分类查找
start = 0
end = result.length - 1
while(start < end) {
middle = (start + end) >> 1 // 相当于Math.floor((start + end)/2)
if (arr[result[middle]] < arrI) {
start = middle + 1
} else{
end = middle
}
}
// 找到最近的哪一项比它大的,替换
if (arr[result[end]] > arrI) {
result[end] = i
if (end > 0) {
p[i] = result[end - 1] // 前面的那个是谁
}
}
}
}let i = result.length
let last = result[i - 1]
while(i-- > 0) {
result[i] = last
last = p[last]
}return result
}// c1表示旧的子节点,c2表示新的子节点
const patchKeyedChildren = (c1, c2) => {
let i = 0
let e1 = c1.length - 1
let e2 = c2.length - 1// 从前面比
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
// 标签和key是否相同
// if (n1.type === n2.type && n1.key === n2.key)
if (n1 === n2) {
// 继续对比其属性和子节点
} else {
break
}
i++
}
// 从后面比
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
// 标签和key是否相同
// if (n1.type === n2.type && n1.key === n2.key)
if (n1 === n2) {
// 继续对比其属性和子节点
} else {
break
}
e1--
e2--
}
console.log(i, e1, e2)// 当i大于e1时
if (i > e1) {
if (i <= e2) {
while (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < c2.length ? c2[nextPos].el : null
// 添加子节点c2[i]在anchor的前面
// todo
i++
}
}
}
// 当i大于e2时
else if (i > e2) {
if (i <= e1) {
while (i <= e1) {
// 删除子节点c1[i]
// todo
i++
}
}
}
// 其它
else {
let s1 = i
let s2 = i
// 以新的子节点作为参照物
const keyToNewIndexMap = new Map()
for (let i = s2;
i <= e2;
i++) {
// 节点的key做为唯一值
// keyToNewIndexMap.set(c2[i].key, i)
keyToNewIndexMap.set(c2[i], i)
}
// 新的总个数
const toBePatched = e2 - s2 + 1
// 记录新子节点在旧子节点中的索引
const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
// 循环老的子节点
for (let i = s1;
i <= e1;
i++) {
const oldChild = c1[i]
// let newIndex = keyToNewIndexMap.get(oldChild.key)
let newIndex = keyToNewIndexMap.get(oldChild)
// 在新子节点中不存在
if (newIndex === undefined) {
// 删除oldChild
// todo
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1 // 永远不会等于0, 这样0就可以表示需要创建了
// 继续对比其属性和子节点
// todo
}
}console.log(newIndexToOldIndexMap)
// 需要移动位置
let increment = getSequence(newIndexToOldIndexMap)// 找出最长序列 [5, 3, 4, 0] -> [1, 2]
console.log(increment)
let j = increment.length - 1
for (let i = toBePatched - 1;
i >= 0;
i--) {
let index = i + s2
let current = c2[index]
let anchor = index + 1 < c2.length ? c2[index + 1].el : null
if (newIndexToOldIndexMap[i] === 0) {
// 在anchor前面插入新的节点current
// todo
} else {
if (i !== increment[j]) {
// 在anchor前面插入对应旧节点.el,current.el元素等于对应的旧节点.el(在其它代码中赋值了)
// todo
} else { // 不变
j--
}}
}
}}
// 调用示例
patchKeyedChildren(['c', 'd', 'e', 'i', 'f', 'g'], ['e', 'c', 'd', 'f', 'g', 'j'])
最长的递增子序列 后续补充
推荐阅读
- vue.js|毕业实习:Vue+Springboot+MySQL实现的订餐系统
- vue3|vue3学习7(props以及验证)
- vue|Vue安装及环境配置、开发工具
- vue|图文详解vue.js devtools插件使用方法
- 数据结构与算法|数据结构之什么是算法()
- vue常见问题|src的别名vue中配置jsconfig.json文件实现
- Node.js|前端如何让跨编辑器开发的项目保持相同的编码风格()
- 前端|Vue的开发路程
- 前端|Vue前端框架