vue3 diff算法怎么应用

这篇文章主要介绍“vue3 diff算法怎么应用”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“vue3 diff算法怎么应用”文章能帮助大家解决问题。

一、可能性（常见）：

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 ></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

从上面结果中我们可以找到规律：

• 当i大于e1时，只需添加新的子节点

• 当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++     }   } }

• 其它，特殊处理

// 其它 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)

• 前面a b和后面f g是一样的，会去掉，只剩中间乱序部分

• 以新的节点为参照物，循环旧的节点，从旧的节点中去掉新的没有的节点，如i

• 标记旧的中没有的节点，没有就为0，表示需要创建；有就序号+1，表示可以复用

标记：       4+1 2+1 3+1  0
新的：(...)   e   c   d   h (...)

• 从后往前循坏，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

过程：

• 从标记中找到最长的递增子序列

• 通过最长的递增子序列找到对应的索引值

• 通过索引值找到对应的值

注意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，移动

// 需要移动位置 // 找出最长的递增子序列对应的索引值，如：[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'])

关于“vue3 diff算法怎么应用”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注亿速云行业资讯频道，小编每天都会为大家更新不同的知识点。