【vue设计与实现】双端Diff算法 1-双端比较的原理和优势

前面介绍了简单Diff算法的实现原理，虽然简单Diff算法有很多有点，但是缺陷也很多，这些缺陷可以通过双端Diff算法解决

简单Diff算法的问题在于，对DOM的移动操作并不是最优的，有时理论上只需要移动一次的DOM操作，使用简单Diff算法却移动了两次，而双端Diff算法就可以做到。
顾名思义，双端Diff算法是一种同时对新旧两组子节点的两个端点进行比较的算法，因此需要四个索引值来分别指向新旧两组子节点的端点。分别为newStartIdx,newEndIdx, oldStartIdx, oldEndIdx
用代码来表达四个端点，如下面代码所示：

function patchChildren(n1,n2,container){
	if(typeof n2.children === 'string'){
		// 省略部分代码
	}else if (Array.isArray(n2.children)){
		// 封装patchKeyedChildren函数处理两组子节点
		patchKeyedChildren(n1,n2,container)
	}else{
		// 省略部分代码
	}
}

function patchKeyedChildren(n1,n2,container){
	const oldChildren = n1.children
	const newChildren = n2.children
	// 四个索引值
	let oldStartIdx = 0
	let oldEndIdx = oldChildren.length - 1
	let newStartIdx = 0
	let newEndIdx = newChildren.length - 1
	// 有了这四个索引值就可以找到所指向的虚拟节点了
	let oldStartVNode = oldChildren[oldStartIdx]
	let oldEndVNode = oldChildren[oldEndIdx]
	let newStartVNode = newChildren[newStartIdx]
	let newEndVNode = newChildren[newEndIdx]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

有了这些信息，就可以开始双端比较了，例如下面
旧子节点为： [p1,p2,p3,p4]
新子节点为：[p4,p2,p1,p3]
第一步先比较：oldStartIdx和newStartIdx所分别指向的元素，如果key不相同，不可复用，则什么都不做
第二步比较：oldEndIdx和newEndIdx所分别指向的元素，如果key不相同，不可复用，则什么都不做
第三步比较：oldStartIdx和newEndIdx所分别指向的元素，如果key不相同，不可复用，则什么都不做
第四步比较：oldEndIdx和newStartIdx所分别指向的元素，如果key相同，可复用

对于可复用的DOM节点，只需要通过DOM移动操作完成更新即可。对应代码如下：

function patchKeyedChildren(n1,n2,container){
	const oldChildren = n1.children
	const newChildren = n2.children
	// 四个索引值
	let oldStartIdx = 0
	let oldEndIdx = oldChildren.length - 1
	let newStartIdx = 0
	let newEndIdx = newChildren.length - 1
	// 有了这四个索引值就可以找到所指向的虚拟节点了
	let oldStartVNode = oldChildren[oldStartIdx]
	let oldEndVNode = oldChildren[oldEndIdx]
	let newStartVNode = newChildren[newStartIdx]
	let newEndVNode = newChildren[newEndIdx]
	
	if(oldStartVNode.key === newStartVNode.key){
		
	}else if(oldEndVNode.key === newEndVNode.key){

	}else if(oldStartVNode.key === newEndVNode.key){

	}else if(oldEndVNode.key === newStartVNode.key){
		// 第四步
		// 需要调用patch函数进行补丁
		patch(oldEndVNode, newStartVNode, container)
		// 移动DOM操作
		// oldEndVNode.el移动到oldStartVNode.el前面
		insert(oldEndVNode.el, container, oldStartVNode.el)
	
		// 移动DOM完成后，更新索引值，并指向下一个位置
		oldEndVNode = oldChildren[--oldEndIdx]
		newStartVNode = newChildren[++newStartIdx]
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

这时候的真实DOM节点的顺序是p4,p1,p2,p3，这时候还没更新完，还需要进行下一轮更新，因此要把更新逻辑封装到一个while循环中如下：

while(oldStartIdx<=oldEndIdx && newStartIdx <= newEndIdx){
	if(oldStartVNode.key === newStartVNode.key){
		
	}else if(oldEndVNode.key === newEndVNode.key){

	}else if(oldStartVNode.key === newEndVNode.key){

	}else if(oldEndVNode.key === newStartVNode.key){
		// 第四步
		// 需要调用patch函数进行补丁
		patch(oldEndVNode, newStartVNode, container)
		// 移动DOM操作
		// oldEndVNode.el移动到oldStartVNode.el前面
		insert(oldEndVNode.el, container, oldStartVNode.el)
	
		// 移动DOM完成后，更新索引值，并指向下一个位置
		oldEndVNode = oldChildren[--oldEndIdx]
		newStartVNode = newChildren[++newStartIdx]
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

由于每次更新完成后，都会更新相关的索引，所以while的循环条件是：头部索引值要小于等于尾部索引值

每次进行更新时都要进行比较

第一次更新完成后，进行下一次比较
第一步比较oldStartIdx 和 newStartIdx所指向的节点也就是旧子节点的p1和新节点组的p2，发现key不同，不可复用，什么都不做
第二步比较oldEndIdx 和 newEndIdx所指向的节点，也就是旧子节点的p3和新节点组的p3，发现key值相同，可以复用，另外由于两者都处于尾部，因此不需要对真实DOM进行移动操作，只需要打补丁即可，如下面代码：

while(oldStartIdx<=oldEndIdx && newStartIdx <= newEndIdx){
	if(oldStartVNode.key === newStartVNode.key){
		
	}else if(oldEndVNode.key === newEndVNode.key){
		patch(oldEndVNode, newEndVNode, container)
		// 更新索引值
		oldEndVNode = oldChildren[--oldEndIdx]
		newEndVNode = newChildren[--newEndIdx]
		
	}else if(oldStartVNode.key === newEndVNode.key){
	
	}else if(oldEndVNode.key === newStartVNode.key){
		patch(oldEndVNode, newStartVNode, container)
		insert(oldEndVNode.el, container, oldStartVNode.el)
		oldEndVNode = oldChildren[--oldEndIdx]
		newStartVNode = newChildren[++newStartIdx]
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这是再继续进行比较
第一步：比较旧头部节点p1与新头部节点p2，由于两者key值不同，因此什么都不做
第二步：比较旧尾部节点p2与尾部头部节点p1，由于两者key值不同，因此什么都不做
第二步：比较旧头部节点p1与新尾部节点p1，由于两者key相同，可以复用

这里节点p1原本是头部节点，但在新的顺序中，变成了尾部节点，因此需要把节点p1对应的真实DOM移动到旧的尾部节点p2所对应的真实DOM后面，同时还要更新相应的索引到下一个位置

代码实现如下：

while(oldStartIdx<=oldEndIdx && newStartIdx <= newEndIdx){
	if(oldStartVNode.key === newStartVNode.key){
		
	}else if(oldEndVNode.key === newEndVNode.key){
		patch(oldEndVNode, newEndVNode, container)
		oldEndVNode = oldChildren[--oldEndIdx]
		newEndVNode = newChildren[--newEndIdx]
		
	}else if(oldStartVNode.key === newEndVNode.key){
		// 调用patch在oldStartVNode和newEndVNode之间打补丁
		patch(oldStartVNode, newEndVNode, container)
		// 注意要将oldStartVNode.el移动到oldEndVNode.el的后面
		insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
		oldStartVNode= oldChildren[++oldStartIdx]
		newEndVNode = newChildren[--newEndIdx]
	}else if(oldEndVNode.key === newStartVNode.key){
		patch(oldEndVNode, newStartVNode, container)
		insert(oldEndVNode.el, container, oldStartVNode.el)
		oldEndVNode = oldChildren[--oldEndIdx]
		newStartVNode = newChildren[++newStartIdx]
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最后一次更新，比较旧头部节点p2和新头部节点p2，发现key相同，可以复用，且两者都是头部节点，因此不需要移动，调用patch函数进行打补丁即可

while(oldStartIdx<=oldEndIdx && newStartIdx <= newEndIdx){
	if(oldStartVNode.key === newStartVNode.key){
		patch(oldStartVNode,newStratVNode,container)
		// 更新相关索引，指向下一个位置
		oldStartVNode = oldChildren[++oldStartIdx]
		newStartVNode = newChildren[++newStartIdx]
		
	}else if(oldEndVNode.key === newEndVNode.key){
		patch(oldEndVNode, newEndVNode, container)
		oldEndVNode = oldChildren[--oldEndIdx]
		newEndVNode = newChildren[--newEndIdx]
		
	}else if(oldStartVNode.key === newEndVNode.key){
		// 调用patch在oldStartVNode和newEndVNode之间打补丁
		patch(oldStartVNode, newEndVNode, container)
		// 注意要将oldStartVNode.el移动到oldEndVNode.el的后面
		insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)
		oldStartVNode= oldChildren[++oldStartIdx]
		newEndVNode = newChildren[--newEndIdx]
	}else if(oldEndVNode.key === newStartVNode.key){
		patch(oldEndVNode, newStartVNode, container)
		insert(oldEndVNode.el, container, oldStartVNode.el)
		oldEndVNode = oldChildren[--oldEndIdx]
		newStartVNode = newChildren[++newStartIdx]
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

这时真实DOM节点的顺序和新一组子节点的顺序相同了，此时newStartIdx和oldStartIdx和值都小于newEndIdx和oldEndIdx，所以循环中止，双端Diff算法执行完毕

双端比较的优势

如果用双端比较来跟新下面这个例子
旧子节点
[p1,p2,p3]
新子节点
[p3,p1,p2]

前面使用简单Diff算法时，发生了两次DOM移动操作，如果使用双端Diff算法会发生几次DOM移动操作

使用双端比较来更新
第一步，比较旧子节点的头部节点p1和新子节点的头部节点p3，两者key不同，不可复用
第二步，比较旧子节点的尾部节点p3和新子节点的尾部节点p2，两者key不同，不可复用
第一步，比较旧子节点的头部节点p1和新子节点的尾部节点p2，两者key不同，不可复用
第一步，比较旧子节点的尾部节点p3和新子节点的头部节点p3，发现可以复用

可以看到，在第四步的比较中，找到了可复用的节点p3，该节点原本处于所有子节点的尾部，但在新的一组子节点中处于头部，因此只要让节点p3对应的真实DOM变成新的头部节点即可。

然后双端算法继续进行做新一轮的比较。当索引newStartIdx和oldStartIdx的值比索引newEndIdx和oldEndIdx的值大时，这样使用双端Diff算法只需要一次DOM移动操作就可完成更新