1. Possibility (common):
1.
Old: a b c
New: a b c d
2.
Old: a b c
New: d a b c
3.
Old: a b c d
New: a b c
4.
Old: d a b c
New: a b c
5.
Old: a b c d e i f g
New: ab e c d h g
The corresponding real virtual node (for easy understanding, the text uses letters instead):
// vnode objectconst a = {
type: 'div', // Label props: {style: {color: 'red'}}, // Attributes children: [], // Sub-elements key: 'key1', // key
el: '<div style="color: 'red'"></div>', // Real dom node ...
}2. Find rules
Remove the same parts in front and back
// c1 represents the old child node, c2 represents the new child nodeconst patchKeyedChildren = (c1, c2) => {
let i = 0
let e1 = - 1
let e2 = - 1
// Compare from the previous one while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
// Is the tag and key the same // if ( === && === )
if (n1 === n2) {
// Continue to compare its properties and children } else {
break
}
i++
}
// From the back while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
// Is the tag and key the same // if ( === && === )
if (n1 === n2) {
// Continue to compare its properties and children } else {
break
}
e1--
e2--
}
(i, e1, e2)
}
// Call examplepatchKeyedChildren(['a', 'b', 'c', 'd'], ['a', 'b', 'c'])Through this function you can get:
1.
Old: a b c
New: a b c di = 3 e1 = 2 e2 = 3
2.
Old: a b c
New: d a b ci = 0 e1 = -1 e2 = 0
3.
Old: a b c d
New: a b ci = 3 e1 = 3 e2 = 2
4.
Old: d a b c
New: a b ci = 0 e1 = 0 e2 = -1
5.
Old: a b c d e i f g
New: ab e c d h gi = 2 e1 = 5 e2 = 5
Extensions:
Old: a b c
New: a b c d e f
i = 3 e1 = 2 e2 = 5Old: a b c
New: a b c
i = 3 e1 = 2 e2 = 2Old: e d a b c
New: a b c
i = 0 e1 = 1 e2 = -1Old: c d e
New: e c d h
i = 0 e1 = 2 e2 = 3
From the above results we can find the rules:
- When i is greater than e1, just add new child nodes
- When i is greater than e2, just delete the old child node
// When i is greater than e1if (i > e1) {
if (i <= e2) {
while (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < ? c2[nextPos].el : null
// Add new child node c2[i] in front of anchor // todo
i++
}
}
}
// When i is greater than e2else if (i > e2) {
if (i <= e1) {
while (i <= e1) {
// Delete the old child node c1[i] // todo
i++
}
}
}- Other, special treatment
// Otherslet s1 = i
let s2 = i
// Use new child nodes as referenceconst keyToNewIndexMap = new Map()
for (let i = s2; i <= e2; i++) {
// The key of the node is used as the unique value // (c2[i].key, i)
(c2[i], i)
}
// The total number of newconst toBePatched = e2 - s2 + 1
// Record the index of the new child node in the old child nodeconst newIndexToOldIndexMap = new Array(toBePatched).fill(0)
// Loop old child nodesfor (let i = s1; i <= e1; i++) {
const oldChild = c1[i]
// let newIndex = ()
let newIndex = (oldChild)
// does not exist in the new child node if (newIndex === undefined) {
// Delete oldChild // todo
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1 // It will never be equal to 0, so 0 can mean that it needs to be created // Continue to compare its properties and children // todo
}
}
(newIndexToOldIndexMap)
// Need to move the positionfor (let i = toBePatched - 1; i >= 0; i--) {
let index = i + s2
let current = c2[index]
let anchor = index + 1 < ? c2[index + 1].el : null
if (newIndexToOldIndexMap[i] === 0) {
// Insert new node in front of anchor current // todo
} else {
// Insert the corresponding old node.el in front of the anchor, the element is equal to the corresponding old node.el (assigned in other codes) // todo
}
}The first and second types are relatively simple, so don’t explain too much. Let’s take a look at the third type, as follows as an example
Serial number: 0 1 2 3 4 5 6 7
Old: (a b) c d e i (f g)
New: (a b) e c d h (f g)
- The front a b and the back f g are the same, and will be removed, leaving only the middle out of order
- Taking the new node as a reference, looping through the old node and removing the new nodes that do not exist from the old node, such as i
- Mark the node that does not exist in the old one. If it does not exist, it means that it needs to be created; if it has a serial number +1, it means that it can be reused.
Tags: 4+1 2+1 3+1 0
New: (...) e c d h (...)
- From the back to the front, h is 0, create, put it in front of its next f; d is not 0, reuse d in the old, put it in front of h; c is not 0, reuse c in the old, put it in front of d; e is not 0, reuse e in the old, put it in front of c; e is not 0, reuse e in the old, put it in front of c
Up to the purpose, the replacement of new and old elements has been completed, but have you found a problem? Ec d h has moved all four elements once. We can see that if only e is moved and h is created, c and d remain unchanged, the efficiency will be higher.
3. Algorithm optimization
1.
Serial number: 0 1 2 3 4 5 6 7
Old: (a b) c d e i (f g)
New: (a b) e c d h (f g)
The corresponding tag is [5, 3, 4, 0]
2.
Serial number: 0 1 2 3 4 5
Old: cd e i f
New: e c d f g j
The corresponding tag is [3, 1, 2, 5, 6, 0]
From the above two examples, we can see:
The first optimal solution is to find c d, just move e, create h
The second optimal solution is to find c d f g, just move e and create j
process:
- Find the longest incremental subsequence from the tag
- Find the corresponding index value through the longest incremental sub-sequence
- Find the corresponding value by index value
Note that 0 means creation directly and does not participate in calculations.
example:
- The longest incrementer sequence of [3, 1, 2, 5, 6, 0] is [1, 2, 5, 6],
- The corresponding index is [1, 2, 3, 4],
- Then we traverse e c d f g j, the marker is 0, such as j, and create it directly; c d f g indexes are equal to 1 2 3 4, respectively, and remain unchanged; e equals 0, and move
// Need to move the position// Find the index value corresponding to the longest incremental sub-sequence, such as: [5, 3, 4, 0] -> [1, 2]let increment = getSequence(newIndexToOldIndexMap)
(increment)
let j = - 1
for (let i = toBePatched - 1; i >= 0; i--) {
let index = i + s2
let current = c2[index]
let anchor = index + 1 < ? c2[index + 1].el : null
if (newIndexToOldIndexMap[i] === 0) {
// Insert new node in front of anchor current // todo
} else {
if (i !== increment[j]) {
// Insert the corresponding old node.el in front of the anchor, the element is equal to the corresponding old node.el (assigned in other codes) // todo
} else { // Unchanged j--
}
}
}The longest incremental subsequence
// The longest incremental subsequence, /wiki/Longest_increasing_subsequencefunction getSequence(arr) {
const len =
const result = [0] // Use the first item as the basis const p = () // Mark the index, slice to copy a new array as shallow let resultLastIndex
let start
let end
let middle
for (let i = 0; i < len; i++) {
let arrI = arr[i]
if (arrI !== 0) { // vue equals 0, which means that it needs to be created resultLastIndex = result[ - 1]
// Insert to the end if (arr[resultLastIndex] < arrI) {
(i)
p[i] = resultLastIndex // Who is the one in front continue
}
// Incremental sequence, binary search start = 0
end = - 1
while(start < end) {
middle = (start + end) >> 1 // Equivalent to ((start + end)/2) if (arr[result[middle]] < arrI) {
start = middle + 1
} else {
end = middle
}
}
// Find the nearest one that is bigger than it, replace it if (arr[result[end]] > arrI) {
result[end] = i
if (end > 0) {
p[i] = result[end - 1] // Who is the one in front }
}
}
}
let i =
let last = result[i - 1]
while(i-- > 0) {
result[i] = last
last = p[last]
}
return result
}
(getSequence([5, 3, 4, 0])) // [1, 2]
(getSequence([3, 1, 2, 5, 6, 0])) // [ 1, 2, 3, 4 ]Supplements for explanation...
Complete code
// The longest incremental subsequence, /wiki/Longest_increasing_subsequencefunction getSequence(arr) {
const len =
const result = [0] // Use the first item as the basis const p = () // Mark the index, slice to copy a new array as shallow let resultLastIndex
let start
let end
let middle
for (let i = 0; i < len; i++) {
let arrI = arr[i]
if (arrI !== 0) { // vue equals 0, which means that it needs to be created resultLastIndex = result[ - 1]
// Insert to the end if (arr[resultLastIndex] < arrI) {
(i)
p[i] = resultLastIndex // Who is the one in front continue
}
// Incremental sequence, binary search start = 0
end = - 1
while(start < end) {
middle = (start + end) >> 1 // Equivalent to ((start + end)/2) if (arr[result[middle]] < arrI) {
start = middle + 1
} else {
end = middle
}
}
// Find the nearest one that is bigger than it, replace it if (arr[result[end]] > arrI) {
result[end] = i
if (end > 0) {
p[i] = result[end - 1] // Who is the one in front }
}
}
}
let i =
let last = result[i - 1]
while(i-- > 0) {
result[i] = last
last = p[last]
}
return result
}
// c1 represents the old child node, c2 represents the new child nodeconst patchKeyedChildren = (c1, c2) => {
let i = 0
let e1 = - 1
let e2 = - 1
// Compare from the previous one while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
// Is the tag and key the same // if ( === && === )
if (n1 === n2) {
// Continue to compare its properties and children } else {
break
}
i++
}
// From the back while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
// Is the tag and key the same // if ( === && === )
if (n1 === n2) {
// Continue to compare its properties and children } else {
break
}
e1--
e2--
}
(i, e1, e2)
// When i is greater than e1 if (i > e1) {
if (i <= e2) {
while (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < ? c2[nextPos].el : null
// Add child node c2[i] in front of anchor // todo
i++
}
}
}
// When i is greater than e2 else if (i > e2) {
if (i <= e1) {
while (i <= e1) {
// Delete child node c1[i] // todo
i++
}
}
}
// Others else {
let s1 = i
let s2 = i
// Use new child nodes as reference const keyToNewIndexMap = new Map()
for (let i = s2; i <= e2; i++) {
// The key of the node is used as the unique value // (c2[i].key, i)
(c2[i], i)
}
// The total number of new const toBePatched = e2 - s2 + 1
// Record the index of the new child node in the old child node const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
// Loop old child nodes for (let i = s1; i <= e1; i++) {
const oldChild = c1[i]
// let newIndex = ()
let newIndex = (oldChild)
// does not exist in the new child node if (newIndex === undefined) {
// Delete oldChild // todo
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1 // It will never be equal to 0, so 0 can mean that it needs to be created // Continue to compare its properties and children // todo
}
}
(newIndexToOldIndexMap)
// Need to move the position // Find the index value corresponding to the longest incremental sub-sequence, such as: [5, 3, 4, 0] -> [1, 2] let increment = getSequence(newIndexToOldIndexMap)
(increment)
let j = - 1
for (let i = toBePatched - 1; i >= 0; i--) {
let index = i + s2
let current = c2[index]
let anchor = index + 1 < ? c2[index + 1].el : null
if (newIndexToOldIndexMap[i] === 0) {
// Insert new node in front of anchor current // todo
} else {
if (i !== increment[j]) {
// Insert the corresponding old node.el in front of the anchor, the element is equal to the corresponding old node.el (assigned in other codes) // todo
} else { // Unchanged j--
}
}
}
}
}
// Call examplepatchKeyedChildren(['c', 'd', 'e', 'i', 'f', 'g'], ['e', 'c', 'd', 'f', 'g', 'j'])The above is the detailed content of the vue3 diff algorithm example. For more information about the vue3 diff algorithm, please follow my other related articles!