关于vue.js:vue3的diff算法

34次阅读

共计 6584 个字符，预计需要花费 17 分钟才能阅读完成。

一、可能性（常见）：

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: '<div style="color: 'red'"></div>', // 实在 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 d

i = 3  e1 = 2  e2 = 3

2.

 旧的：a b c
新的：d a b c

i = 0  e1 = -1  e2 = 0

3.

 旧的：a b c d
新的：a b c

i = 3  e1 = 3  e2 = 2

4.

 旧的：d a b c
新的：a b c

i = 0  e1 = 0  e2 = -1

5.

 旧的：a b c d e i f g
新的：a b e c d h f g

i = 2  e1 = 5  e2 = 5

扩大：

 旧的：a b c
新的：a b c d e f
i = 3  e1 = 2  e2 = 5

旧的：a b c
新的：a b c
i = 3  e1 = 2  e2 = 2

旧的：e d a b c
新的：a b c
i = 0  e1 = 1  e2 = -1

旧的：c d e  
新的：e c d h
i = 0  e1 = 2  e2 = 3

从下面后果中咱们能够找到法则：

  1. 当 i 大于 e1 时，只需增加新的子节点
  2. 当 i 大于 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++
    }
  }
}
  1. 其它，非凡解决 
// 其它
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
  }
}

第 1 种和第 2 种比较简单，不做过多的解说，咱们来看看第 3 种，以上面为例 

 序号：0 1  2 3 4 5  6 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. 标记旧的中没有的节点，没有就为 0，示意须要创立；有就序号 +1，示意能够复用 
 标记：4+1 2+1 3+1  0
新的：(...)   e   c   d   h (...)
  1. 从后往前循坏，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 1  2 3 4 5  6 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

过程：

  1. 从标记中找到最长的递增子序列
  2. 通过最长的递增子序列找到对应的索引值
  3. 通过索引值找到对应的值

留神 0 示意间接创立，不参加计算

例子：

  1. [3, 1, 2, 5, 6, 0] 的最长的递增子序列为 [1, 2, 5, 6]，
  2. 对应的索引为 [1, 2, 3, 4]，
  3. 而后咱们遍历 e c d f g j，标记中为 0 的，比方 j，间接创立；c d f g 索引别离等于 1 2 3 4，放弃不变；e 等于 0，挪动 
// 须要挪动地位
// 找出最长的递增子序列对应的索引值，如：[5, 3, 4, 0] -> [1, 2]
let increment = getSequence(newIndexToOldIndexMap)
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--
    }
  }
}

最长的递增子序列 

// 最长的递增子序列，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
}

console.log(getSequence([5, 3, 4, 0])) // [1, 2]
console.log(getSequence([3, 1, 2, 5, 6, 0])) // [1, 2, 3, 4]

解说后续补充 …

残缺代码 

// 最长的递增子序列，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)
    // 须要挪动地位
    // 找出最长的递增子序列对应的索引值，如：[5, 3, 4, 0] -> [1, 2]
    let increment = getSequence(newIndexToOldIndexMap)
    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.js
2022-07-13
 0
VuePress-TailwindCss-Netlify-重写个人独立博客
关于vue.js:开源了唱吧-UI-组件库开源了
关于vue.js:vue面试之CompositionAPI响应式包装对象原理
关于vue.js:Vue3实现字符串反转和内容隐藏