preface

The double-end comparison algorithm is the DIFF algorithm used by VUe2. X, this article is just a rough analysis of the process of the double-end comparison algorithm, the specific details or Vue source code, Vue source code in this

process

Suppose you have two arrays arr1 and arR2

Let arr2 = [1,2,3,4,5]Copy the code

So it’s a five-step process

  1. Arr1 [0] is compared with ARR2 [0]
  2. Arr1 [arr1.length-1] compares with ARR2 [arr2.length-1]
  3. Arr1 [0] is compared with ARR2 [arr2.length-1]
  4. Arr1 [arR1.length-1] is compared with ARR2 [0]
  5. Each element of ARR2 [0] and ARR1 is compared

Each comparison starts at both ends of the array, with the leading index +1 if the first comparison is equal

If the comparison succeeds at the end, the end index of the comparison is -1. If the opening index is greater than the end index, the comparison is over

Disassembly process

Let arr1 = [1,2,3,4,5] let arr2 = [4,3,5,1] let oldStartIdx = 0 let oldEndIdx = arr1. lenght-1 let newStartIdx = 0 let  newEndIdx = arr2.length -1 let oldStartVNode = arr1[oldStartIdx] let oldEndVNode = arr1[oldEndIdx] let newStartVNode = Arr2 [newStartIdx] let newEndVNode = arr2[newEndIdx] 1. 1 is not equal to 4. 2. 5 is not equal to 4. NewStartIdx++ // after the comparison, use u_1 to indicate the successful element [1,2,3,u_1,5] //arr1 [u_1,3,5,1,2] //arr2 1. 1 is not equal to 3. 2 is not equal to 4. 5 is not equal to 3. //arr1 [u_1,u_2,5,1,2] //arr2 round 3: 1. 1 is not equal to 5. 2. 1 is not equal to 2. Step 4 is successful, enter the next round // after successful, use u_3 to represent successful elements [1,2,u_2,u_1,u_3] //arr1 [u_1,u_2,u_3,1,2] //arr2 round 4: 1. 1 is equal to 1. 1 has been moved from oldStartIdx to newStartIdx,oldStartIdx++,newStartIdx++ 2. Step 1 is more successful, enter the next round 3. Step 1 is more successful, enter the next round 4. 5. The first step is relatively successful, and the next round // after relatively successful, use U_4 to indicate the more successful element [U_4,2, U_2, U_1, U_3] // ARR1 [U_1, U_2, U_3, U_4,2] // ARR2 1. 2 is equal to 2. 1 has been moved from oldStartIdx to newStartIdx,oldStartIdx++,newStartIdx++ 2. Step 1 is more successful, enter the next round 3. Step 1 is more successful, enter the next round 4. 5. The first step is relatively successful, after entering the next round // relatively successful, use U_5 to denote the more successful element [U_4, U_5, U_2, U_1, U_3] // ARR1 [U_1, U_2, U_3, U_4, U_5] // ARR2Copy the code

It’s represented by a GIF

In the code

function diff(prevChildren, NextChildren) {let oldStartIdx = 0 // old array start index let oldEndIdx = prevchildren. length - 1 // old array end index let newStartIdx = 0 NewEndIdx = nextChildren. length-1 oldStartVNode = prevChildren[oldStartIdx] let oldEndVNode = prevChildren[oldEndIdx] let newStartVNode = nextChildren[newStartIdx] let newEndVNode = nextChildren[newEndIdx] while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (! OldStartVNode = prevChildren[++ oldStarttidx]} else if (! OldEndVNode) {//undefined oldEndVNode = prevChildren[--oldEndIdx]} else if (oldStartVNode.key === newStartVNode.key ) { //1. OldStartVNode = prevChildren[++oldStartIdx] newStartVNode = nextChildren[++newStartIdx]} else if ( oldEndVNode.key === newEndVNode.key ) { //2. OldEndVNode = prevChildren[--oldEndIdx] newEndVNode = nextChildren[--newEndIdx]} else if (oldStartVNode.key === newEndVNode.key ) { //3. Start and End oldStartVNode = prevChildren[++oldStartIdx] newEndVNode = nextChildren[--newEndIdx]} else if (oldEndVNode.key ===  newStartVNode.key ) { //4. OldEndVNode = prevChildren[--oldEndIdx] newStartVNode = nextChildren[++newStartIdx]} else {//5. Const idxInOld = prevChildren.findIndex((node) => {if (node && node.key === newStartVNode.key) { Return true}}) if (idxInOld >= 0) {prevChildren[idxInOld] = undefined else {//newStartVNode is a new element} newStartVNode = NextChildren [+ + newStartIdx]}}} diff ([1, 2, 3, 4, 5], [4,3,5,1,2])Copy the code

We found that the above algorithm after the walk, if the old and new two arrays just change order, it can perfect the diff difference, but if the new array is not add or delete, so we need to find out at the completion of a while loop add or remove elements, how do you know which is the new which is to remove the elements?

In the fifth step of the comparison, the first element of the selected new array is compared with all the elements of the old array one by one. Here we can find out whether the array is new. If the comparison is equal, it is the position transformation, otherwise the current element is new. The condition for the while loop is oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx if

Let arr2 = [1,2,3,4,5] let arr2 = [1,2,3,4,5,6,7]Copy the code

Because of the loop condition, this will end after 5 while, so the 6 and 7 at the end of the array never meet the insert condition of step 5. How do we know that 6 and 7 are new? Let’s look at the index after the while loop ends

// Let arr1 = [1,2,3,4,5] let arr2 = [1,2,3,4,5,6,7] NewEndIdx = 6 // example 2 let arr1 = [1,2,3,4,5] let arr2 = [4,5,6,7,1,3,2] oldEndIdx = 2 newStartIdx = 6, NewEndIdx = 5 // example 3 let arr1 = [1,2,3,4,5] let arr2 = [7,1,3,5,6,4,2] oldEndIdx = 4 newStartIdx = 4, NewEndIdx = 4 // example 4 let arr1 = [1,2,3,4,5] let arr2 = [2,4,1,5,7,3,6] oldEndIdx = 2 newStartIdx = 6, newEndIdx = 6Copy the code

We see that the index of the new element corresponds to newStartIdx and newEndIdx

  • Example 1: newStartIdx is smaller than newEndIdx and is 5 and 6. The new element 6 corresponds to arR2 index 6, and the new element 7 corresponds to ARR2 index 7. Both 6 and 7 are out of the arR1 range
  • Example 2: newStartIdx is greater than newEndIdx, there is no correspondence
  • Example 3: newStartIdx equals newEndIdx, and we find that the element whose ARR2 index is 4 is the new element 6, but 6 times it is not out of the arr1 range, it is just the last element in the array
  • Example 4: newStartIdx equals newEndIdx, and arR2 with index 6 is the new element 6

So the conclusion is, if after the while loop, if newStartIdx is less than or equal to newEndIdx, then the corresponding element between newStartIdx and newEndIdx is the new element, And oldStartIdx is always larger than oldEndIdx

What about deleting elements? See the example

// let arr1 = [4,3,5,6,7,2,1] let arr2 = [1,3,5,4,2] NewStartIdx = 2 // example 2 let arr1 = [7,2,3,5,6,1,4] let arr2 = [5,1,2,3,4] oldEndIdx = 4 newStartIdx = 4, NewStartIdx = 3 // example 3 let arr1 = [1,5,4,2,6,7,3] let arr2 = [4,5,1,2,3] oldEndIdx = 5 newStartIdx = 4, newStartIdx = 3Copy the code

In the same way, newStartIdx is always larger than newStartIdx, and the elements to be deleted are always between oldStartIdx and oldEndIdx, so we just need to delete the elements of oldStartIdx and oldEndIdx. OldStartIdx = oldEndIdx; oldStartIdx = oldEndIdx; oldStartIdx = oldEndIdx; oldStartIdx = oldEndIdx; And the key thing is, if we look at example 2,3, and 5, we see that they all go to step 5 of the two-ended comparison algorithm, and step 5 says

const idxInOld = prevChildren.findIndex((node) => { if (node && node.key === newStartVNode.key) { return true } }) if (idxInOld >= 0) {prevChildren[idxInOld] = undefined} else {//newStartVNode is the new element} newStartVNode = nextChildren[++newStartIdx]Copy the code

If idxInOld>0 is found in the old array, we set preChildren[idxInOld] to undefined, i.e., 2,3, and 5 have been diff replaced with undefined in arR1. Here’s why diff algorithms need to judge in the first place! OldStartVNode and! OldEndVnode, let’s improve the code

function diff(prevChildren, NextChildren) {let oldStartIdx = 0 // old array start index let oldEndIdx = prevchildren. length - 1 // old array end index let newStartIdx = 0 NewEndIdx = nextChildren. length-1 oldStartVNode = prevChildren[oldStartIdx] let oldEndVNode = prevChildren[oldEndIdx] let newStartVNode = nextChildren[newStartIdx] let newEndVNode = nextChildren[newEndIdx] while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (! OldStartVNode = prevChildren[++ oldStarttidx]} else if (! OldEndVNode) {//undefined oldEndVNode = prevChildren[--oldEndIdx]} else if (oldStartVNode.key === newStartVNode.key ) { //1. OldStartVNode = prevChildren[++oldStartIdx] newStartVNode = nextChildren[++newStartIdx]} else if ( oldEndVNode.key === newEndVNode.key ) { //2. OldEndVNode = prevChildren[--oldEndIdx] newEndVNode = nextChildren[--newEndIdx]} else if (oldStartVNode.key === newEndVNode.key ) { //3. Start and End oldStartVNode = prevChildren[++oldStartIdx] newEndVNode = nextChildren[--newEndIdx]} else if (oldEndVNode.key ===  newStartVNode.key ) { //4. OldEndVNode = prevChildren[--oldEndIdx] newStartVNode = nextChildren[++newStartIdx]} else {//5. Const idxInOld = prevChildren.findIndex((node) => {if (node && node.key === newStartVNode.key) { Return true}}) if (idxInOld >= 0) {prevChildren[idxInOld] = undefined else {//newStartVNode is a new element} newStartVNode = nextChildren[++newStartIdx] } } if (oldStartIdx > oldEndIdx) { for (; newStartIdx <= newEndIdx; ++newStartIdx) {let vnode = nextChildren[newStartIdx]}} else if (newStartIdx > newEndIdx) {for (let I = oldStartIdx; i <= oldEndIdx; I++) {/ / delete content}}} diff ([1, 2, 3, 4, 5], [4,3,5,1,2])Copy the code

Let’s use two GIFs to represent the diff process

1. Add elements

2. Reduce elements