react、 vue2 和 vue3 的 diff 方法

1360

virtual+dom.png

辅助方法

// 更新数据
function patch(o, n){
    o.val = n.val
}
// 模拟dom节点移动
function insertBefore(prev, node, container, step = 0){
    if(prev === null){
        remove(node, container)
        container.push(node) 
        return container
    }
    if(prev && prev.key === node.key) return container
    let idx = 0
    for (let i = 0; i < container.length; i++) {
        const n = container[i];
        if(n.key === node.key){
            [ node ] = container.splice(i, 1)
            break
        }
    }
    // console.log(prev, node, container)
    for (let i = 0; i < container.length; i++) {
        const n = container[i];
        if(prev && n.key === prev.key){
            idx = i + step
            break
        }
    }
    // console.log(idx)
    // console.log(container.slice(0, idx))
    // console.log(container.slice(idx))
    return [
        ...container.slice(0, idx),
        node,
        ...container.slice(idx)
    ]
}
// 删除某元素方法
function remove(node, container){
    for (let i = 0; i < container.length; i++) {
        const n = container[i];
        if(node && n.key === node.key){
            container.splice(i, 1)
            break
        }
    }
    return container
}
// 求最长上升子序列
function lis(arr) {
    const p = arr.slice()
    const result = [0]
    let i
    let j
    let u
    let v
    let c
    const len = arr.length
    for (i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            j = result[result.length - 1]
            if (arr[j] < arrI) {
                p[i] = j
                result.push(i)
                continue
            }
            u = 0
            v = result.length - 1
            while (u < v) {
                c = ((u + v) / 2) | 0
                if (arr[result[c]] < arrI) {
                    u = c + 1
                } else {
                    v = c
                }
            }
            if (arrI < arr[result[u]]) {
            if (u > 0) {
                p[i] = result[u - 1]
            }
                result[u] = i
            }
        }
    }
    u = result.length
    v = result[u - 1]
    while (u-- > 0) {
        result[u] = v
        v = p[v]
    }
    return result
}
复制代码

react

算法流程

  1. 遍历 next 取出 nextNode，位置 i
  2. 在 prev 中查找 nextNode.key 一致的节点，如果没找到，则创建后插入到 next[i - 1] 之后
  3. 如果找到节点，位置为 j ，更新节点，判断 j 是否小于 lastIdx（lastIdx = 0），如果不小于，则 lastIdx = j
  4. 如果小于 lastIdx 则将节点插入到 next[i - 1] 之后
  5. 遍历 next 结束后，遍历 prev 如果节点不在 next 中，则删除节点

代码实现

// react
function diff1(prev, next){
    let container = prev.slice()
    let nextIndex = {}
    let prevIndex = {}
    let prevLength = prev.length
    let nextLength = next.length
    let lastIdx = 0
    // 生成映射表，方便查找
    for(let i = 0; i < prevLength; i++) prevIndex[prev[i].key] = i
    for(let i = 0; i < nextLength; i++){
        // 1. 遍历 next 取出 nextNode，位置 i
        let nextNode = next[i]
        nextIndex[nextNode.key] = i
        // 3. 如果找到节点，位置为 j ，更新节点，判断 j 是否小于 lastIdx（lastIdx = 0），如果不小于，则 lastIdx = j
        let j = prevIndex[nextNode.key]
        if(j !== undefined){
            patch(prev[j], nextNode)
            // 4. 如果小于 lastIdx 则将节点插入到 next[i - 1] 之后
            if(j < lastIdx){
                container = insertBefore(next[i - 1], nextNode, container, 1)
            }else{
                lastIdx = j
            }
        }else{
            // 2. 在 prev 中查找 nextNode.key 一致的节点，如果没找到，则创建后插入到 next[i - 1] 之后
            container = insertBefore(next[i - 1], nextNode, container, 1)
        }
    }
    // 5. 遍历 next 结束后，遍历 prev 如果节点不在 next 中，则删除节点
    for(let p of prev){
        if(nextIndex[p.key] === undefined){
            remove(p, container)
        }
    }
    return container
}
复制代码

执行流程

第 1 行表示模拟 prev 数组 (一份拷贝)，点状表示移动过的节点，虚线表示更新过的节点

第 2 行表示旧的 prev 数组，绿色表示操作过，红色表示当前遍历的值

第 3 行表示新的 next 数组

image.png

按照 react diff 的流程来模拟下步骤

遍历 prev 生成一份 key 与 index 的映射表 prevIndex

image.png

遍历 next 数组，i = 0 lastIdx = 0 通过 prevIndex[key] 得出 j = 1 j 大于 lastIdx，lastIdx = j = 1 只执行更新操作不执行移动

image.png

i = 1 lastIdx = 1 通过 prevIndex[key] 得出 j = 0 j 小于 lastIdx 所以执行更新操作和移动操作，需要把 a 移动到 next[i - 1].next 也就是 c 节点之前

image.png

i = 2 lastIdx = 1 通过 prevIndex[key] 得出 j = 3 j 大于 lastIdx，lastIdx = j = 3 执行更新操作

image.png

i = 3 lastIdx = 3 通过 prevIndex[key] 得出 j = 2 j 小于 lastIdx 所以执行更新操作和移动操作，需要把 c 移动到 next[i - 1].next 也就是 f 节点之前

image.png

i = 4 lastIdx = 3 通过 prevIndex[key] 找不到对应的节点位置，所以这里需要新增一个节点 e，把 e 移动到 next[i - 1].next 也就是 f 节点之前

image.png

遍历完成后，我们需要重新遍历一遍 prev 然后通过 nextIndex 查找得出 f 节点已经不存在于新的节点数组之中，需要执行删除操作移除 f 节点

image.png

vue2

算法流程

  1. 声明4个变量 prevStart，prevEnd，nextStart，nextEnd 取出 prevStartNode， prevEndNode，nextStartNode，nextEndNode
  2. 循环，条件不满足 prevStart <= prevEnd && nextStart <= nextEnd 跳出循环
  3. prevStartNode 或 prevEndNode 是否存在，不存在则 prevStart++，prevEnd--，回到 2
  4. prevStartNode.key == nextStartNode.key，相等则更新节点，prevStart++ nextStart++，回到2
  5. prevEndNode.key == nextEndNode.key，相等则更新节点，prevEnd-- nextEnd--， 回到2
  6. prevStartNode.key == nextEndNode.key，相等则更新节点， 将 prevStartNode 插入到 prevEndNode.next 之前，prevStart++ nextEnd--，回到 2
  7. prevEndNode.key == nextStartNode.key，相等则更新节点，将 prevEndNode 插入到 prevStartNode 之前，prevEnd-- nextStart++，回到 2
  8. 如果全都不相等，查找 prev，看是否存在一个与 nextStartNode.key 相同的节点，有则更新，没有则创建一个新的节点，将其插入到 prevStartNode 之前，nextStart++，prev[j]标记为操作过，回到2
  9. 循环结束后 如果 prevEnd < prevStart 证明存在新节点未处理，从 nextStart 开始 插入节点，直到 newEnd，每次节点都插入在 next[newEnd + 1] 之前
  10. 如果 nextEnd < newStart 证明存在节点被移除，未处理，从 prevStart 开始 移除节点，直到 prevEnd

代码实现

// vue2
function diff2(prev, next){
    let container = prev.slice()
    // 1. 声明4个变量 prevStart，prevEnd，nextStart，nextEnd 取出 prevStartNode， prevEndNode，nextStartNode，nextEndNode
    let prevStart = 0
    let nextStart = 0
    let prevEnd = prev.length - 1
    let nextEnd = next.length - 1
    let prevStartNode = prev[prevStart]
    let prevEndNode = prev[prevEnd]
    let nextStartNode = next[nextStart]
    let nextEndNode = next[nextEnd]
    let prevIndex = {}
    for(let i = 0; i < prev.length; i++) prevIndex[prev[i].key] = i
    // 2. 循环，条件不满足 prevStart <= prevEnd && nextStart <= nextEnd 跳出循环
    while(prevStart <= prevEnd && nextStart <= nextEnd){
        // 3. prevStartNode 或 prevEndNode 是否存在，不存在则 prevStart++，prevEnd--，回到 2
        if(!prevStartNode){
            prevStartNode = prev[++prevStart]
        }else if(!prevEndNode){
            prevEndNode = prev[--prevEnd]
        }else if(prevStartNode.key === nextStartNode.key){
            // 4. prevStartNode.key == nextStartNode.key，相等则更新节点， prevStart++ nextStart++，回到2
            patch(prevStartNode, nextStartNode)
            prevStartNode = prev[++prevStart]
            nextStartNode = next[++nextStart]
        }else if(prevEndNode.key === nextEndNode.key){
            // 5. prevEndNode.key == nextEndNode.key，相等则更新节点， prevEnd-- nextEnd --， 回到2
            patch(prevEndNode, nextEndNode)
            prevEndNode = prev[--prevEnd]
            nextEndNode = next[--nextEnd]
        }else if(prevStartNode.key === nextEndNode.key){
            // 6. prevStartNode.key == nextEndNode.key，相等则更新节点， 将 prevStartNode 插入到 prevEndNode.next 之前，prevStart++ nextEnd--，回到 2 
            patch(prevStartNode, nextEndNode)
            container = insertBefore(prevEndNode, prevStartNode, container, 1)
            prevStartNode = prev[++prevStart]
            nextEndNode = next[--nextEnd]
        }else if(prevEndNode.key === nextStartNode.key){
            // 7. prevEndNode.key == nextStartNode.key，相等则更新节点，将 prevEndNode 插入到 prevStartNode 之前，prevEnd-- nextStart++，回到 2
            patch(prevEndNode, nextStartNode)
            container = insertBefore(prevStartNode, prevEndNode, container)
            prevEndNode = prev[--prevEnd]
            nextStartNode = next[++nextStart]
        }else{
            // 8. 如果全都不相等，查找 prev，看是否存在一个与 nextStartNode.key相同的节点，有则更新，没有则创建一个新的节点，将其插入到 prevStartNode 之前，nextStart++，prev[j]标记为操作过，回到2
            let j = prevIndex[nextStartNode.key]
            if(j !== undefined){
                patch(prev[j], nextStartNode)
                prev[j] = undefined
            }
            container = insertBefore(prevStartNode, nextStartNode, container)
            nextStartNode = next[++nextStart]
        }
    }
    if(prevEnd < prevStart){
        // 9. 循环结束后 如果 prevEnd < prevStart 证明存在新节点未处理，从 nextStart 开始 插入节点，直到newEnd，每次节点都插入在 next[newEnd + 1]之前
        let ref = next[nextEnd + 1] || null
        while(nextStart <= nextEnd){
            container = insertBefore(ref, next[nextStart++], container)
        }
    }else if(nextEnd < nextStart){
        // 10. 如果 nextEnd < newStart 证明存在节点被移除，未处理，从 prevStart 开始 移除节点，直到 prevEnd
        while(prevStart <= prevEnd){
            remove(prev[prevStart++], container)
        }
    }
    return container
}
复制代码

执行流程

初始化 prevIndex , 此时 prevStart = 0 , prevEnd = 4, nextStart = 0, nextEnd = 4

image.png

通过比较 prevStart 与 nextStart，prevEnd 与 nextEnd，prevStart 与 nextEnd，prevEnd 与 nextStart 得知皆不想等，则通过 prevIndex 获取到 nextStartNode 是可以复用的节点，位置在 j = 1，将 prev[j] 更新后，将其设置为 undefined，并且将 nextStartNode 插入到 prevStartNode 之前，然后 nextStartNode = next[++nextStart]

image.png

此时 prevStart = 0 , prevEnd = 4, nextStart = 1, nextEnd = 4

image.png

满足 prevStartNode.key === nextStartNode.key 此时直接更新 prevStartNode 然后执行 prevStart++ nextStart++

image.png

此时 prevStartNode 是先前处理过的节点，所以直接跳过 prevStart++

image.png

此时 prevStart = 2 , prevEnd = 4, nextStart = 2, nextEnd = 4

image.png

通过比较 prevStart 与 nextStart，prevEnd 与 nextEnd，prevStart 与 nextEnd，prevEnd 与 nextStart 得知皆不想等，则通过 prevIndex 获取到 nextStartNode 是可以复用的节点，位置在 j = 3，将 prev[j] 更新后，将其设置为 undefined，并且将 nextStartNode 插入到 prevStartNode 之前，然后 nextStartNode = next[++nextStart]

image.png

此时 prevStart = 2 , prevEnd = 4, nextStart = 3, nextEnd = 4

image.png

满足 prevStartNode.key === nextStartNode.key 此时直接更新 prevStartNode 然后执行 prevStart++ nextStart++

image.png

此时 prevStartNode 是先前处理过的节点，所以直接跳过 prevStart++

image.png

此时 prevStart = 4 , prevEnd = 4, nextStart = 4, nextEnd = 4

image.png

通过比较 prevStart 与 nextStart，prevEnd 与 nextEnd，prevStart 与 nextEnd，prevEnd 与 nextStart 得知皆不想等，且在 prevIndex 中也没法获取到此节点，证明这个为新增节点，创建节点后插入到 prevNodeStart 之前，执行 nextStartNode = next[++nextStart]

image.png

此时 prevStart = 4 , prevEnd = 4, nextStart = 5, nextEnd = 4，此时已经不满足循环条件了，所以直接跳出

image.png

由判断 prevStart > prevEnd 不成立，但 nextStart > nextEnd 成立，所以存在节点是未删除的，循环删除掉多余的节点，条件为 prevStart <= prevEnd 最后得到

image.png

在看一组巩固

此时 prevStart = 0 , prevEnd = 3, nextStart = 0, nextEnd = 4

image.png

通过比较，得知 prevStartNode 与 nextStartNode 相等，更新后移动指针位置

image.png

通过比较，得知 prevEndNode 与 nextEndNode 相等，更新节点，然后把节点移动到 prevStartNode 之前

image.png

此时 prevStart = 1 , prevEnd = 2, nextStart = 2, nextEnd = 4

image.png

我们发现 prevEndNode 跟 nextStartNode 是相等的，更新节点后移动指针

image.png

此时 prevStart = 1 , prevEnd = 1, nextStart = 2, nextEnd = 3

image.png

我们发现 prevStartNode 跟 nextStartNode 是相等的，更新节点后移动指针

image.png

此时 prevStart = 2 , prevEnd = 1, nextStart = 3, nextEnd = 3 已经不符合循环条件，跳出循环，此时满足 prevEnd < prevStart，证明还有新增节点，循环将新节点插入在 next[nextEnd + 1] 之前

image.png

vue3

算法流程

  1. j 表示当前匹配到第几个位置，初始值为0
  2. 从 j 开始匹配相同的元素，如果 prev[j].key == next[j].key，更新后 j++ 如果 j > prevEnd || j > nextEnd 提前跳出
  3. 匹配完前面的相同元素后 j 停在第一个不同点
  4. 从 prevEnd 和 nextEnd 开始从后面查找相同的后缀，更新后 prevEnd-- nextEnd-- 如果 j > prevEnd || j > nextEnd 提前跳出
  5. 此时已经更新完相同的前缀和后缀，需要看 j 处于什么位置
  6. 如果 j > prevEnd && j <= nextEnd ，则 next 在 [j , nextEnd] 新增元素，直接在 next[nextEnd + 1] 前插入新增元素
  7. 如果 j > nextEnd && j <= prevEnd ，则 prev 在 [j , prevEnd] 中元素被删除，直接删除多余元素
  8. 如果都不是上两种情况，则说明在 [j , prevEnd] 段存在乱序的节点，长度为 nextLeft = nextEnd - j + 1
  9. 初始化一个辅助数组 source 长度为 nextLeft 默认值为 -1，patched = 0，move = false，pos = 0
  10. 遍历 next, 从 j 到 nextEnd，生成一个 key - i 的映射表 keyIndex
  11. 遍历 prev ,从 j 到 prevEnd
  12. 如果 patched 大于 nextLeft，则说明相同元素从 prev 中取完，后面均为待删除的元素，直接删除
  13. k = keyIndex[prev[i]]，如果 k 不存在，证明该节点不存在于 next，直接删除
  14. next[k].key == prev[i].key，则更新该节点，patched++，source[k - j] = i，如果 k < pos，则 prev[i] 是需要移动的 move = true，否则 pos = k
  15. 处理完成后判断 move 是否为真
  16. 如果不为真，i = nextLeft - 1 倒序遍历，如果 source[i] == -1 时，pos = j + i，在 next[pos + 1] 前增加节点 next[pos]
  17. 如果为真，则在这段范围内发生乱序 / 新增的情况
  18. 求出最长上升子序列 seq = lis(source) k = seq.length - 1
  19. i = nextLeft - 1 倒序遍历，如果 source[i] == -1 时，pos = j + i，在 next[pos + 1] 前增加节点 next[pos]
  20. 如果 i == seq[j]，则需要移动此节点，pos = j + i，在 next[pos + 1] 前插入节点 next[pos]
  21. 其他情况，k--

代码实现

// vue3
function diff3(prev, next){
    let container = prev.slice()
    // 1. j 表示当前匹配到第几个位置，初始值为0
    let j = 0
    let prevEnd = prev.length - 1
    let nextEnd = next.length - 1
    let prevNode = prev[j]
    let nextNode = next[j]
    // 2. 从 j 开始匹配相同的元素，如果 prev[j].key == next[j].key，更新后 j++ 如果 j > prevEnd || j > nextEnd 提前跳出
    while(prevNode && nextNode && prevNode.key === nextNode.key){
        patch(prevNode, nextNode)
        j++
        if(j > prevEnd || j > nextEnd) break
        prevNode = prev[j]
        nextNode = next[j]
    }
    // 3. 匹配完前面的相同元素后 j 停在第一个不同点
    prevNode = prev[prevEnd]
    nextNode = next[nextEnd]
    // 4. 从 prevEnd 和 nextEnd 开始从后面查找相同的后缀，更新后 prevEnd-- nextEnd-- 如果 j > prevEnd || j > nextEnd提前跳出
    while(prevNode && nextNode && prevNode.key === nextNode.key){
        patch(prevNode, nextNode)
        prevEnd--
        nextEnd--
        if(j > prevEnd || j > nextEnd) break
        prevNode = prev[prevEnd]
        nextNode = next[nextEnd]
    }
    // 5. 此时已经更新完相同的前缀和后缀，需要看 j 处于什么位置
    if(j > prevEnd && j <= nextEnd){
        // 6. 如果 j > prevEnd && j <= nextEnd ，则 next 在[ j , nextEnd]  新增元素，直接在next[nextEnd + 1] 前插入新增元素
        let ref = next[nextEnd + 1] || null
        while(j <= nextEnd){
            container = insertBefore(ref, next[j++], container)
        }
    }else if(j > nextEnd && j <= prevEnd){
        // 7. 如果 j > nextEnd && j  <= prevEnd ，则 prev 在 [j , prevEnd]  中元素被删除，直接删除多余元素
        while(j <= prevEnd){
            remove(prev[j++], container)
        }
    }else if(j <= nextEnd){
        // 8. 如果都不是上两种情况，则说明在 [j , prevEnd] 段存在乱序的节点，长度为 nextLeft = nextEnd - j + 1
        let nextLeft = nextEnd - j + 1
        // 9. 初始化一个辅助数组  source 长度为 nextLeft 默认值为 -1，patched = 0，move = false， pos = 0
        let source = new Array(nextLeft).fill(-1)
        let pos = 0
        let patched = 0
        let move = false
        let keyIndex = {}
        // 10. 遍历 next, 从 j 到 nextEnd，生成一个 key - i 的映射表 keyIndex
        for(let i = j; i <= nextEnd; i++) keyIndex[next[i].key] = i
        // 11. 遍历 prev ,从 j 到 prevEnd 
        for (let i = j; i <= prevEnd; i++) {
            let prevNode = prev[i]
            // 12. 如果 patched 大于 nextLeft，则说明相同元素从 prev 中取完，后面均为待删除的元素，直接删除
            if(patched < nextLeft){
                let k = keyIndex[prevNode.key]
                // 13. k = keyIndex[prev[i]]，如果 k 不存在，证明该节点不存在于 next，直接删除
                if(k !== undefined){
                    // 14. next[k].key == prev[i].key，则更新该节点，patched++，source[k - j] = i，如果 k < pos，则prev[i] 是需要移动的 move = true，否则 pos = k
                    patch(prevNode, next[k])
                    source[k - j] = i
                    patched++
                    if(k < pos){
                        move = true
                    }else{
                        pos = k
                    }
                }else{
                    remove(prevNode, container)
                }
            }else{
                remove(prevNode, container)
            }
        }
        // 15. 处理完成后判断 move 是否为真
        if(move){
            // 17. 如果为真，则在这段范围内发生乱序 / 新增的情况
            // 18. 求出最长上升子序列 seq = lis(source) j = seq.length - 1
            let seq = lis(source)
            let k = seq.length - 1
            for(let i = nextLeft - 1; i >= 0; i--){
                if(source[i] === -1 || i !== seq[k]){
                    // 19. i = nextLeft - 1 倒序遍历，如果 source[i] == -1 时，pos = j + i，在 next[pos + 1]前增加节点next[pos]
                    // 20. 如果 i == seq[j]，则需要移动此节点，pos = j + i，将 prev 中的 next[pos]插入到 prev 中的 next[pos + 1] 之前
                    let pos = j + i
                    container = insertBefore(next[pos + 1] || null, next[pos], container)
                }else{
                    // 21. 其他情况，j-- 
                    k--
                }
            }
        }else{
            // 16. 如果不为真，i = nextLeft - 1 倒序遍历，如果 source[i] == -1 时，pos = j + i，在 next[pos + 1]前增加节点 next[pos]
            for(let i = nextLeft - 1; i >= 0; i--){
                if(source[i] === -1){
                    let pos = j + i
                    container = insertBefore(next[pos + 1] || null, next[pos], container)
                }
            }
        }
    }
    return container
}
复制代码

执行流程

首先比较前缀节点 j = 0 prevEnd = 3 nextEnd = 4 prevNode = prev[j] nextNode = next[j]

image.png

满足循环条件，执行到第一个不同点，即 j = 1 prevNode = prev[j] nextNode = next[j]

image.png

开始比对后缀节点，另 prevNode = prev[prevEnd] nextNode = next[nextEnd]，如果满足循环条件则开始循环

image.png

更新后缀节点直到不满足循环条件

image.png

此时 j = 1 prevEnd = 2 nextEnd = 3，条件 j > prevEnd && j <= nextEnd 与 j > nextEnd && j <= prevEnd 没有被满足，j <= nextEnd 满足，证明 [j, nextEnd] 区间存在乱序或新增的情况

image.png

我们计算 nextLeft = nextEnd - j + 1 = 3 得出乱序区间大小为 3，source = [-1, -1, -1]，从 j 到 nextEnd 遍历 next 数组，得到 keyIndex，然后从 j 到 prevEnd 遍历 prev 数组 初始化 pos = 0 patched = 0 move = false

image.png

当 i = j = 1，pos = 0``patched = 0``nextLeft = 3 且 patched < nextLeft 则查找 keyIndex 看 next 中是否存在节点下标 k = 2，如果找到，更新节点，patched++， 令 source[k - j] = i 则 source = [-1, 1, -1]，判断 k < pos，如果小于则是需要移动，move = true， 这里明显不成立，所以令 pos = k = 2

image.png

当 i = 2，pos = 2``patched = 1，查找 keyIndex 得到 k = 1，更新节点，patched++ 令 source[k - j] = i 则 source = [2, 1, -1]，因为 k < pos 所以这个节点是需要移动的，所以 move = true

image.png

因为需要移动所以需要通过lis(最长上升子序列)来确定最少移动的次数，seq = lis(source) = [2], k = seq.length - 1 = 1 然后我们从nextLeft - 1往前遍历，直到 0

image.png

i = 2时，通过 source[i] = -1，-1 表明此节点我们未曾处理过，必然是一个新增的节点，所以我们需要新增这个节点到数组中，由于我们上面得出的 source 是一个相对坐标，逆推可以得到当前节点在 next 中的坐标为 pos = j + i = 3 则它需要插入在 next[pos + 1] 节点的前方

image.png

i = 1时，由于 source[i] != -1，则我们接着判断 i !== seq[k]，由于不相等，这个节点是一个需要移动的节点，则我们将此节点移动到 next[pos + 1] 之前。

image.png

i = 0是，判断都不成立，所以 k--，接着就循环结束了，完成匹配

image.png

再来一遍执行流程加强下理解

这里直接跳过了前缀跟后缀的处理流程，也没啥好说的，此时 j = 0 prevEnd = 5 nextEnd = 5，条件 j > prevEnd && j <= nextEnd 与 j > nextEnd && j <= prevEnd 没有被满足，j <= nextEnd 满足，证明 [j, nextEnd] = [0, 5] 区间存在乱序或新增的情况

image.png

根据上面的流程，我们求出 keyIndex, nextLeft = nextEnd - j + 1 = 5, source = [-1, -1, -1, -1, -1]，从 j 遍历到 prevEnd

image.png

当 i = j = 0， patched = 0, pos = 0, move = false，通过 keyIndex 可查找出 a 节点位于 next 中下标为 1 的位置，更新后，记录位置更新变量，patched++, pos = 1, move = false, source[k - j] = source[1] = 0

image.png

当 i = 1，patched = 1, pos = 1, move = false，通过 keyIndex 查找出 k = 0 由于 k < pos 所以节点 b 是需要移动的，更新后，记录位置，更新变量，patched++, pos = 1, move = true, source[k - j] = source[0] = 1

image.png

当 i = 2，patched = 2, pos = 1, move = true，通过 keyIndex 查找出 k = 2 由于 k > pos 所以 pos = k = 2，更新后，记录位置，更新变量，patched++, pos = 2, source[k - j] = source[2] = 2

image.png

当 i = 3，patched = 3, pos = 2，通过 keyIndex 查找出 k = 5 由于 k > pos 所以 pos = k = 5，更新后，记录位置，更新变量，patched++, pos = 5, source[k - j] = source[5] = 3

image.png

当 i = 4，patched = 4, pos = 5，通过 keyIndex 查找出 k = 4 由于 k < pos 所以 pos = 5，更新后，记录位置，更新变量，patched++, pos = 5, source[k - j] = source[4] = 4

image.png

当 i = 5，patched = 5, pos = 5，通过 keyIndex 查找出 k = 3 由于 k < pos 所以 pos = 5，更新后，记录位置，更新变量，patched++, pos = 5, source[k - j] = source[3] = 5

image.png

遍历结束，此时 source = [ 1, 0, 2, 5, 4, 3 ], move = true 通过 seq = lis(source) = [0, 2, 5], k = seq.length - 1 = 3 从 nextLeft - 1 开始遍历

当 i = 5，source[5] !== -1 但 i === seq[k] 所以不做处理，k--

image.png

当 i = 4，source[4] !== -1 由于 i !== seq[k] 所以要移动该节点，pos = j + i = 4 next[pos] 需要插入在 next[pos + 1] 之前

image.png

当 i = 3，source[4] !== -1 由于 i !== seq[k] 所以要移动该节点，pos = j + i = 3 next[pos] 需要插入在 next[pos + 1] 之前

image.png

当 i = 2，source[5] !== -1 但 i === seq[k] 所以不做处理，k--

image.png

当 i = 1，source[4] !== -1 由于 i !== seq[k] 所以要移动该节点，pos = j + i = 1 next[pos] 需要插入在 next[pos + 1] 之前

image.png

当 i = 0，source[5] !== -1 但 i === seq[k] 所以不做处理，k--

image.png

测试代码


const check = (diff) => {
    var count = 100
    var changeCount = 100
    for(let i = 0; i < count; i++){
        var random = 0 + Math.floor(10 * Math.random())
        var prev = new Array(random).fill(0).map((item, index) => {
            return {
                key: 'key-' + index,
                val: index
            }
        })
        for(let j = 0; j < changeCount; j++){
            var ran = random + (Math.floor(5 * Math.random()) * ( Math.random() > 0.5 ? 1 : -1))
            ran = ran > 0 ? ran : 0
            var next = new Array(ran).fill(0).map((item, index) => {
                return {
                    key: 'key-' + index,
                    val: index * random
                }
            })
            shuff(next)
            var res = diff(prev, next)
            if(!eq(res, next)){
                console.log(prev, next)
            }
            prev = res
        }
    }
};

function shuff(arr){
    let len = arr.length - 1
    for(let i = 0; i < len; i++){
        let rand = i + Math.floor((len - i) * Math.random())
        swap(arr, rand, i)
    }
}

function swap(arr, i, j){
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

console.log('random test')
console.time('diff1')
check(diff1)
console.timeEnd('diff1')

console.time('diff2')
check(diff2)
console.timeEnd('diff2')

console.time('diff3')
check(diff3)
console.timeEnd('diff3')

let size = 5000
let next = new Array(size).fill(0).map((item, index) => {
    return {
        key: 'key-' + index,
        val: index
    }
})
let prev = JSON.stringify(next)
shuff(next)
next = JSON.stringify(next)

console.log('test')
console.time('diff1')
eq(diff1(JSON.parse(prev), JSON.parse(next)), next)
console.timeEnd('diff1')

console.time('diff2')
eq(diff2(JSON.parse(prev), JSON.parse(next)), next)
console.timeEnd('diff2')

console.time('diff3')
eq(diff3(JSON.parse(prev), JSON.parse(next)), next)
console.timeEnd('diff3')
复制代码

执行结果

image.png

© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
前端
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4202
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3895
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3842
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3406
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
相关推荐
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
手摸手教你实现vue的动态路由（addRoute版）-一一网
手摸手教你实现vue的动态路由（addRoute版）
手摸手教你实现vue的动态路由（addRoute版）
4年前 3118
Unity实用功能之使用TextMeshPro组件-一一网
Unity实用功能之使用TextMeshPro组件
Unity实用功能之使用TextMeshPro组件
4年前 3062
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …-一一网
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …...
4年前 2847
Windi CSS 在 Vue3 + Vite 项目中的使用-一一网
Windi CSS 在 Vue3 + Vite 项目中的使用
Windi CSS 在 Vue3 + Vite 项目中的使用
3年前 2728
vue3 使用 qrcode.vue 生成二维码-一一网
vue3 使用 qrcode.vue 生成二维码
vue3 使用 qrcode.vue 生成二维码
4年前 2621
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.7W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云