Vue3 diff算法的簡單解刨
上篇我們介紹瞭vue2中的雙端diff算法的優勢（相比於簡單算法相同場景下移動DOM次數更少）。如今Vue3的勢頭正盛，在diff算法方面也做瞭相應的變化，利用到瞭最長遞增子序列把性能又提升瞭一個檔次。對於技術棧使用Vue的同學來說又是必須要學習的一部分。
性能比較
此圖借鑒瞭《Vuejs設計與實現》這本書
ivi和inferno所采用的快速diff算法的性能要稍優於Vue2的雙端diff算法。既然快速diff算法這麼高效，我們當然有必要瞭解它咯。
前置與後置的預處理
這裡有兩組子節點，c1表示老的子節點，c2表示新的子節點。首先將從c1和c2的頭部節點開始對比，如果節點相同則通過patch更新節點的內容。e1表示老的子節點的尾部索引，e2表示新的子節點的尾部索引。
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
// 如果節點相同 則進行遞歸執行patch更新節點
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else {
// 如果節點不相同，則直接退出
break
}
i++
}
然後將索引遞增，發現c1中節點B和c2中節點D不是同一節點，則循環退出。接著將從c1和c2的尾部節點開始對比，如果節點相同則通過patch更新節點的內容。
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = (c2[e2] = optimized
? cloneIfMounted(c2[e2] as VNode)
: normalizeVNode(c2[e2]))
// 如果是相同節點 則遞歸執行patch
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else {
// 如果節點不相同 則退出
break
}
e1--
e2--
}
此過程經歷瞭c1的節點C和c2的節點C對比，c1的節點B和c2的節點B對比,節點相同則通過patch更新節點的內容,每次循環e1 e2向前推進。當循環到瞭c1中節點B和c2中節點D不是同一節點，則循環退出
此時當新節點中還有剩餘，則需要添加新節點。 相反的，如果舊節點有剩餘需要刪除舊節點
if (i > e1) {
// 當索引大於老節點的尾部
if (i <= e2) {
// 當索引小於新節點的尾部 需要將剩餘的節點添加
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch(
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
i++
}
}
}
else if (i > e2) {
// 當索引i大於尾部索引e2 則直接刪除舊子樹從索引i開始到e1部分的節點
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
上面的情況是有序的，下面我們看下無序的情況
節點無序
上圖是經過上面的兩層循環之後的結果。我們首先看下代碼,由於節點無序情況的代碼比較長，我們一段段的解刨
const s1 = i // prev starting index 舊子序列開始索引 從i開始記錄
const s2 = i // next starting index 新子序列開始索引 從i開始記錄
// 5.1 build key:index map for newChildren
// 根據key 建立新子序列的索引圖
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
// 獲取新節點
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
if (nextChild.key != null) {
if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
warn(
`Duplicate keys found during update:`,
JSON.stringify(nextChild.key),
`Make sure keys are unique.`
)
}
// 根據新節點的key 和 對應的索引做映射關系
// <key, index>
keyToNewIndexMap.set(nextChild.key, i)
}
}
let j
// 新子序列已經更新的節點數量
let patched = 0
// 新子序列待更新節點的數量，等於新子序列的長度
const toBePatched = e2 - s2 + 1
// 是否存在需要移動的節點
let moved = false
// 用於跟蹤判斷是否有節點需要移動的節點
let maxNewIndexSoFar = 0
// 這個數組存儲新子序列中的元素在舊子序列節點出的索引，用於確定最長遞增子序列
const newIndexToOldIndexMap = new Array(toBePatched)
// 初始化數組 為0
// 0是一個特殊的值，如果遍歷之後仍有元素的值為0，則說明這個新節點沒有對應的舊節點
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
s1表示舊子節點開始遍歷的索引，從i開始記錄，s2表示新子節點開始遍歷的索引，也從i開始記錄。根據新子節點的key建立新子序列的索引圖keyToNewIndexMap。patched表示新子序列已經更新的節點數量，toBePatched表示新子序列待更新節點的數量，等於新子序列的長度。moved表示是否存在需要移動的節點。maxNewIndexSoFar用於跟蹤判斷是否有節點需要移動的節點。newIndexToOldIndexMap存儲新子序列中的節點在舊子序列節點的索引，用於確定最長遞增子序列，初始化全部為0，0是一個特殊的值，如果遍歷之後仍有元素的值為0，則說明這個新節點沒有對應的舊節點。我們在圖中表示一下
然後正序遍歷舊子序列
// 正序遍歷舊子序列
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
if (patched >= toBePatched) {
// 所有新的子序列節點都已經更新，刪除剩餘的節點
// all new children have been patched so this can only be a removal
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
if (prevChild.key != null) {
// 查找舊子序列中的節點在新子序列中的索引
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// key-less node, try to locate a key-less node of the same type
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
newIndex = j
break
}
}
}
if (newIndex === undefined) {
// 找不到說明舊子序列需要刪除
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
// 更新新子序列中的元素在舊子序列中的索引，這裡 +1 偏移是為瞭避免i為0的特殊情況 影響後面最長遞增子序列的求解
newIndexToOldIndexMap[newIndex - s2] = i + 1
//maxNewIndexSoFar 存儲的是上次舊值的newIndex 如果不是一直遞增 則說明有移動
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized處
)
patched++
}
}
每次遍歷拿到舊子節點的值prevChild，如果patched >= toBePatched也就是說新子序列已經更新的節點數量大於等於待更新的節點數量，說明新子序列的所有節點更新完畢，舊子序列中剩餘的節點刪除即可。
如果每次循環拿到的舊子節點的值的key存在，則查找舊子序列中的節點在新子序列中的索引標記為newIndex。如果key不存在，則遍歷新子序列待更新的節點，如果prevChild和遍歷新子序列待更新的節點有相同的節點，則將索引賦值給newIndex。接著判斷newIndex是否存在，如果不存在，則說明新子序列中找不到舊子序列中的這個節點，則直接刪除。如果存在，則更新新子序列中的元素在舊子序列中的索引，這裡 ‘+1’ 偏移是為瞭避免i為0的特殊情況，影響後面最長遞增子序列的求解，因為我們現在規定的newIndexToOldIndexMap中的元素為0說明這個元素沒有對應的老節點，如果不'+1'我們避免不瞭i為0的情況，這樣就影響瞭最長遞增子序列的求解。我們看下newIndexToOldIndexMap重新賦值之後的結果
maxNewIndexSoFar存儲的是上次舊值的newIndex,如果不是一直遞增 則說明有移動，則moved設置為ture。然後將newIndex對應的新節點和prevChild老節點進行patch，然後patched++記錄更新的次數。
我們繼續看下面的代碼
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// 倒序遍歷 以便使用更新的節點作為錨點
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
// 錨點指向上一個更新的節點， 如果nextIndex超過新節點的長度，則指向parentAnchor
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
if (newIndexToOldIndexMap[i] === 0) {
// mount new
// 掛載新節點
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else if (moved) {
// 沒有最長遞增子序列或者當前節點索引不在最長遞增子序列中， 需要移動
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
首先判斷是否需要移動，如果需要移動怎麼才能以移動最少的步數完成更新呢？這就需要用到最長遞增子序列（getSequence這個方法代碼我們貼到文章最後)。我們得到瞭最長遞增子序列的索引值的集合increasingNewIndexSequence，我們看下結果。
根據結果我們發現在newIndexToOldIndexMap中隻有索引為0和1的節點是遞增的，所以隻有這兩個對應的舊的子序列的節點是不需要移動的，其他的則需要移動。
倒序遍歷。為什麼要倒序遍歷呢？因為我們將節點插入到已經更新的節點前面(從後往前遍歷可以始終保持當前遍歷的節點的下一個節點是更新過的)這裡使用的是insertBefore。
比如這個例子節點‘G’就要插入到節點‘E’的前面，節點‘E’是已經更新過的瞭。
繼續往前推進，節點‘B’不在最長遞增子序列increasingNewIndexSequence中，所以需要移動。然後拿到節點‘B’對應的el插入到節點‘G’的前面。這個節點‘B’的el我們從節點‘B’的Vnode上面就可以獲取到瞭。因為當兩個新舊節點進行對比的時候會進行下面的操作
以上就是我們要介紹的Vue3的diff算法的核心內容
總結
有序的情況比較簡單，我們就直接說無序的情況。
1.根據key建立新子序列的索引圖 keyToNewIndexMap
通過遍歷新子序列的節點 將key和index映射
2.根據新子序列中待更新節點的數量toBePatched創建數組newIndexToOldIndexMap數組初始化為0
這個數組就是保存新子序列中的節點在舊子序列中的索引位置。
3.遍歷舊子節點 拿舊的子節點去keyToNewIndexMap中找對應新子節點的位置
- 如果找不到 則說明這個節點在新的子節點中沒有則刪除
- 找到瞭之後則更新
newIndexToOldIndexMap,數組中的元素被重新賦值為新子序列中的節點在舊子序列中的索引位置，為0的元素說明這個節點是新增的。 - 將新舊子節點對比更新
4.通過最長遞增子序列找到那些節點是需要移動的，哪些節點是不需要的移動的
最長遞增子序列
// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr: number[]): number[] {
const p = arr.slice()
const result = [0]
let i, j, u, v, c
const len = arr.length
for (i = 0; i < len; i++) {
// arrI 為當前順序取出的元素
const arrI = arr[i]
// 排除0的情況
if (arrI !== 0) {
// result 存儲的是長度為i的遞增子序列最小末尾值的索引
j = result[result.length - 1]
// arr[j]為末位置，如果滿足arr[j]<arrI 那麼直接在當前遞增子序列後面添加
if (arr[j] < arrI) {
// 存儲result更新前的最後一個索引的值
p[i] = j
// 存儲元素對應的索引值
result.push(i)
continue
}
// 不滿足 則執行二分搜索
u = 0
v = result.length - 1
// 查找第一個比arrI小的節點，更新result的值
while (u < v) {
// c記錄中間的位置
c = (u + v) >> 1
if (arr[result[c]] < arrI) {
// 若中間的值小於arrI 則在後邊 更新下沿
u = c + 1
} else {
// 更新下沿
v = c
}
}
// 找到第一個比arrI小的位置u，插入它
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]
}
result[u] = i
}
}
}
u = result.length
v = result[u - 1]
while (u-- > 0) {
result[u] = v
v = p[v]
}
return result
}
以上就是Vue3 diff算法的簡單解刨的詳細內容，更多關於Vue3 diff算法的資料請關註WalkonNet其它相關文章！
推薦閱讀：
- Vue3 源碼解讀之 Teleport 組件使用示例
- 一文詳解Vue 的雙端 diff 算法
- vue3.x源碼剖析之數據響應式的深入講解
- Vue源碼分析之虛擬DOM詳解
- 淺談Vue3中key的作用和工作原理