背景
在页面更新的过程中，如果能做到只更新需要更新的点，更新的越少越好；如果存在可复用的节点，能复用的越多越好。
传统的diff算法从整棵树进行搜索，去复用那些可复用的节点， 然而算法的时间复杂度为O(n3)，时间带来了性能上巨大的损耗。传统的diff为什么是O(n3)，大家可自行研究。
Vue的diff算法是Snabbdom 进行实现的， 它只对同层级的节点进行比较时间复杂度为O(n)。
思想
1.只进行同层级的比较
2.同层级新旧child比较时使用头尾双指针
主要代码如下
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
var oldStartIdx = 0;
var newStartIdx = 0;
var oldEndIdx = oldCh.length - 1;
var oldStartVnode = oldCh[0];
var oldEndVnode = oldCh[oldEndIdx];
var newEndIdx = newCh.length - 1;
var newStartVnode = newCh[0];
var newEndVnode = newCh[newEndIdx];
var oldKeyToIdx, idxInOld, vnodeToMove, refElm;
// removeOnly is a special flag used only by <transition-group>
// to ensure removed elements stay in correct relative positions
// during leaving transitions
var canMove = !removeOnly;
if (process.env.NODE_ENV !== 'production') {
checkDuplicateKeys(newCh);
}
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
根据key值进行搜索
if (isUndef(oldKeyToIdx)) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); }
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
} else {
vnodeToMove = oldCh[idxInOld];
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
oldCh[idxInOld] = undefined;
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
} else {
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
}
}
newStartVnode = newCh[++newStartIdx];
}
}
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
} else if (newStartIdx > newEndIdx) {
removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}
}
看代码有可能会感到困惑陷入进行， 我们结合示例来进行讲解
示例1
删除最后一个元素
<template>
<div>
<ul>
<li v-for="item in arr" :key="item.id">{{item.text}}</li>
</ul>
<span @click="changeArr">to change Arr</span>
</div>
</template>
<script>
export default {
data() {
return {
arr: [
{id: 'a', text: 'A'},
{id: 'b', text: 'B'},
{id: 'c', text: 'C'},
{id: 'd', text: 'D'}
]
}
},
methods: {
changeArr() {
var newArr = [
{id: 'a', text: 'A'},
{id: 'b', text: 'B'},
{id: 'c', text: 'C'}
]
this.arr = newArr;
}
}
}
</script>
QQ20200407-0.png
示例2
删除第一个元素
<template>
<div>
<ul>
<li v-for="item in arr" :key="item.id">{{item.text}}</li>
</ul>
<span @click="changeArr">to change Arr</span>
</div>
</template>
<script>
export default {
data() {
return {
arr: [
{id: 'a', text: 'A'},
{id: 'b', text: 'B'},
{id: 'c', text: 'C'},
{id: 'd', text: 'D'}
]
}
},
methods: {
changeArr() {
var newArr = [
{id: 'b', text: 'B'},
{id: 'c', text: 'C'},
{id: 'd', text: 'D'}
]
this.arr = newArr;
}
}
}
</script>
QQ20200407-1.png
示例3
采用一种粗暴的方式，仅剩一个元素B，使其命中 根据key值进行搜索的分支
<template>
<div>
<ul>
<li v-for="item in arr" :key="item.id">{{item.text}}</li>
</ul>
<span @click="changeArr">to change Arr</span>
</div>
</template>
<script>
export default {
data() {
return {
arr: [
{id: 'a', text: 'A'},
{id: 'b', text: 'B'},
{id: 'c', text: 'C'},
{id: 'd', text: 'D'}
]
}
},
methods: {
changeArr() {
var newArr = [
{id: 'b', text: 'B'}
]
this.arr = newArr;
}
}
}
</script>
QQ20200407-2.png
大家可以通过增、删、查、改、交换、导致等方式进行diff的分析
这里简单的举这几个例子
sameVnode
如果存在key值且key值相等，或者是tag相同
function sameVnode (a, b) {
return (
a.key === b.key && (
(
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
) || (
isTrue(a.isAsyncPlaceholder) &&
a.asyncFactory === b.asyncFactory &&
isUndef(b.asyncFactory.error)
)
)
)
}
网友评论