diff

参考: 图解 React 的 diff 算法：核心就两个字 —— 复用 - 掘金 (juejin.cn)

同级比较

• 爷爷辈只和爷爷辈比较,孙子辈子和孙子辈比较
• type 变了: 删除旧的dom, 重新创建新dom
• type 没变: 复用旧的dom, 需要跟新它的属性和位置

简单diff

简单diff就是从左往右挨个对比: 比较两个节点的key是否相同

• key不同: 删了重新创建
• key相同: 比较节点类型是否相同
  • type相同: 复用
  • type不同: 删了重新创建

const children1 = [a, b, c]
const children2 = [b, c, a]

children2.forEatch((newFiber, index) => {
    const oldFiber = children1[index]
    if(!oldFiber) // 新增
    if(oldFiber && oldFiber.type === newFiber.type) // 更新
    if(oldFiber && oldFiber.type !== newFiber.type) // 删除旧的, 重新创建
    if(oldFiber) children1.splice(index, 1) // 比对完就从children1中删除, 最后剩下的就是要删除的节点
})

children1.forEatch(item => {
    // 最后剩下的就是要删除的节点
})

简单diff就是没有key的情况下的diff栓法

old	new	effectTag
h1	h2	无法复用,删除h1,创建h2
h3	h3	可以复用,更新旧的节点h3就行了
h4	div	无法复用,删除h4,创建div

有新增的节点

old	new	effectTag
h1	h2	无法复用,删除h1,创建h2
h3	h3	可以复用,更新旧的节点h3就行了
	div	div是新的节点

有需要删除的节点

old	new	effectTag
h1	h2	无法复用,删除h1,创建h2
h3	h3	可以复用,更新旧的节点h3就行了
h4		h4需要被删除

复杂diff

• 利用key进行diff
• 能够精准的更新节点
• 性能比较差
• 所以一般都是, 先进行简单diff,再进行复杂diff,尽量减少复杂diff的工作量

const children1 = [a, b, c]
const children2 = [b, c, a]

// 将children1 放入 map 中, 方便children2查询
const map = new Map()
children1.forEatch(item => map.set(item.key, item))

// children2 到map中查找
children2.forEach(newItem => {
    const oldItem = map.get(newItem.key)
    if(oldItem && oldItem.type === newItem.type) // 更新
    if(oldItem && oldItem.type !== newItem.type) // 删除旧的, 重新创建
    if(!oldItem) // 新增
    if(oldItem) map.delete(newItem.key) // 对比完就将节点从map中删除
})

map.forEach(item => {
    // 如果map中还有剩余, 剩余的这些节点需要被删除
})

React 的 diff

• 第一轮遍历: 掐头, 先从左往右简单diff, 发现key不同后停止
• 第二轮遍历: 掐头后,剩下的节点开始进行复杂diff

第一轮遍历:简单diff

从左往右挨个对比: 比较两个节点的key是否相同

• key不同: 结束简单diff,进入复杂diff
• key相同: 比较节点类型是否相同
  • type相同: 复用
  • type不同: 删了重新创建

第二轮遍历:复杂diff

• 把剩下的老 fiber 节点放到 map 里，然后遍历新的 vdom 节点，从 map 中能找到的话，就是可复用，移动过来打上更新的标记。
• 遍历完之后
  • 剩下的老 fiber 节点删掉，
  • 剩下的新 vdom 新增。

位置跟新

• 由 [a, b, c] 变为 [c, a, b]
• 将 [a, b, c] 放到 new Map()里面
• 依次遍历 c, a, b
• let lastIndex=0
• 遍历到c
  • 不移动: c.index=2 > lastIndex=0
  • lastIndex被修改: lastIndex=2, 需要移动就会更新lastIndex
• 遍历到a
  • 需要移动: a.index=0 < lastIndex=2
  • lastIndex保持不变: lastIndex=2
• 遍历到b
  • 需要移动: b.index=1 < lastIndex=2
  • lastIndex保持不变: lastIndex=2

let lastIndex = 0
let jsx = [c, a, b]

jsx.map(item => {
    if(item.index > lastIndex){
        lastIndex = item.index
    }else{
        item.flags |= 移动
    }
})

vue3 的diff算法

掐头去尾对比法

• 第一轮遍历: 掐头, 先从左往右简单diff, 发现key不同后停止
• 第二轮遍历: 去尾, 先从右往左简单diff, 发现key不同后停止
• 第三轮遍历: 掐头去尾后,剩下的节点开始进行复杂diff

位置更新

• 如下代码
• 在react中 2 不会更新位置, 0和1会更新位置
• 在vue3中, 2 会更新位置, 0和1不会更新位置
• 因为vue3使用了最长子序列算法
• 最长递增子序列是 0, 1
  • 0, 1, 不会移动
  • 2, 会移动

let a = [0,1,2]
let b = [2,0,1]

最长递增子序列算法

• b的最长子序列是 [0, 1]
• 最长递增子序列 对应的节点不会发生位置跟新,所有只有2会发生位置跟新

let a = [0,1,2]
let b = [2,0,1]

什么是最长递增子序列

const a = [9, 1,2,3,4,3] // 的最长子序列是 1,2,3,4
const b = [0, 9, 3, 7, 2] // 最长子序列为0, 3, 7

思路

遍历到2

arr[2, 3, 1, 5, 4]
res = [
    [2]
]

遍历到3

arr[2, 3, 1, 5, 4]
res = [
    [2],
    [2, 3]
]

遍历到1

arr[2, 3, 1, 5, 4]
res = [
    [1],
    [2, 3],
]

遍历到5

arr[2, 3, 1, 5, 4]
res = [
    [1],
    [2, 3],
    [2, 3, 5],
]

遍历到4

arr[2, 3, 1, 5, 4]
res = [
    [1],
    [2, 3],
    [2, 3, 4],
]

实现

const arrInput = [2,3,1,5,6,8,7,9,4]
const res = lengthOfLIS(arrInput)
console.log(res)

function lengthOfLIS(list) {
    const dp = [
        [list[0]]
    ]

    for(let i=1; i<list.length;i++) {
        const num = list[i]
        updateDp(num)
    }

    return dp[dp.length-1]

    function updateDp(num: number) {
        const index = find(num)
        if(index===0) {
            dp[0]=[num]
        }
        else{
            dp[index] = [...dp[index-1], num]
        }
    }
    // 可使用二分查找优化
    function find(num: number) {
        for(let i=0; i<dp.length; i++) {
            const arr = dp[i]
            const n = arr[arr.length-1]
            if(n>=num) return i
        }
        return dp.length
    }

}

vue2 的diff算法

双端交叉算法

• 头->头
• 尾->尾
• 头->尾
• 尾->头
• 挨个找