Vue3 diff算法的簡單解刨
上篇我們介紹了vue2中的雙端diff算法的優(yōu)勢(相比于簡單算法相同場景下移動DOM次數(shù)更少)。如今Vue3的勢頭正盛,在diff算法方面也做了相應(yīng)的變化,利用到了最長遞增子序列把性能又提升了一個檔次。對于技術(shù)棧使用Vue的同學來說又是必須要學習的一部分。
性能比較
此圖借鑒了《Vuejs設(shè)計與實現(xiàn)》這本書
ivi
和inferno
所采用的快速diff算法的性能要稍優(yōu)于Vue2的雙端diff算法。既然快速diff算法這么高效,我們當然有必要了解它咯。
前置與后置的預(yù)處理
這里有兩組子節(jié)點,c1
表示老的子節(jié)點,c2
表示新的子節(jié)點。首先將從c1
和c2
的頭部節(jié)點開始對比,如果節(jié)點相同則通過patch更新節(jié)點的內(nèi)容。e1
表示老的子節(jié)點的尾部索引,e2
表示新的子節(jié)點的尾部索引。
while (i <= e1 && i <= e2) { const n1 = c1[i] const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i])) // 如果節(jié)點相同 則進行遞歸執(zhí)行patch更新節(jié)點 if (isSameVNodeType(n1, n2)) { patch( n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) } else { // 如果節(jié)點不相同,則直接退出 break } i++ }
然后將索引遞增,發(fā)現(xiàn)c1
中節(jié)點B和c2
中節(jié)點D不是同一節(jié)點,則循環(huán)退出。接著將從c1
和c2
的尾部節(jié)點開始對比,如果節(jié)點相同則通過patch更新節(jié)點的內(nèi)容。
while (i <= e1 && i <= e2) { const n1 = c1[e1] const n2 = (c2[e2] = optimized ? cloneIfMounted(c2[e2] as VNode) : normalizeVNode(c2[e2])) // 如果是相同節(jié)點 則遞歸執(zhí)行patch if (isSameVNodeType(n1, n2)) { patch( n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) } else { // 如果節(jié)點不相同 則退出 break } e1-- e2-- }
此過程經(jīng)歷了c1
的節(jié)點C和c2
的節(jié)點C對比,c1
的節(jié)點B和c2
的節(jié)點B對比,節(jié)點相同則通過patch更新節(jié)點的內(nèi)容,每次循環(huán)e1
e2
向前推進。當循環(huán)到了c1
中節(jié)點B和c2
中節(jié)點D不是同一節(jié)點,則循環(huán)退出
此時當新節(jié)點中還有剩余,則需要添加新節(jié)點。 相反的,如果舊節(jié)點有剩余需要刪除舊節(jié)點
if (i > e1) { // 當索引大于老節(jié)點的尾部 if (i <= e2) { // 當索引小于新節(jié)點的尾部 需要將剩余的節(jié)點添加 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部分的節(jié)點 while (i <= e1) { unmount(c1[i], parentComponent, parentSuspense, true) i++ } }
上面的情況是有序的,下面我們看下無序的情況
節(jié)點無序
上圖是經(jīng)過上面的兩層循環(huán)之后的結(jié)果。我們首先看下代碼,由于節(jié)點無序情況的代碼比較長,我們一段段的解刨
const s1 = i // prev starting index 舊子序列開始索引 從i開始記錄 const s2 = i // next starting index 新子序列開始索引 從i開始記錄 // 5.1 build key:index map for newChildren // 根據(jù)key 建立新子序列的索引圖 const keyToNewIndexMap: Map<string | number | symbol, number> = new Map() for (i = s2; i <= e2; i++) { // 獲取新節(jié)點 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.` ) } // 根據(jù)新節(jié)點的key 和 對應(yīng)的索引做映射關(guān)系 // <key, index> keyToNewIndexMap.set(nextChild.key, i) } } let j // 新子序列已經(jīng)更新的節(jié)點數(shù)量 let patched = 0 // 新子序列待更新節(jié)點的數(shù)量,等于新子序列的長度 const toBePatched = e2 - s2 + 1 // 是否存在需要移動的節(jié)點 let moved = false // 用于跟蹤判斷是否有節(jié)點需要移動的節(jié)點 let maxNewIndexSoFar = 0 // 這個數(shù)組存儲新子序列中的元素在舊子序列節(jié)點出的索引,用于確定最長遞增子序列 const newIndexToOldIndexMap = new Array(toBePatched) // 初始化數(shù)組 為0 // 0是一個特殊的值,如果遍歷之后仍有元素的值為0,則說明這個新節(jié)點沒有對應(yīng)的舊節(jié)點 for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
s1
表示舊子節(jié)點開始遍歷的索引,從i
開始記錄,s2
表示新子節(jié)點開始遍歷的索引,也從i
開始記錄。根據(jù)新子節(jié)點的key建立新子序列的索引圖keyToNewIndexMap
。patched
表示新子序列已經(jīng)更新的節(jié)點數(shù)量,toBePatched
表示新子序列待更新節(jié)點的數(shù)量,等于新子序列的長度。moved
表示是否存在需要移動的節(jié)點。maxNewIndexSoFar
用于跟蹤判斷是否有節(jié)點需要移動的節(jié)點。newIndexToOldIndexMap
存儲新子序列中的節(jié)點在舊子序列節(jié)點的索引,用于確定最長遞增子序列,初始化全部為0,0是一個特殊的值,如果遍歷之后仍有元素的值為0,則說明這個新節(jié)點沒有對應(yīng)的舊節(jié)點。我們在圖中表示一下
然后正序遍歷舊子序列
// 正序遍歷舊子序列 for (i = s1; i <= e1; i++) { const prevChild = c1[i] if (patched >= toBePatched) { // 所有新的子序列節(jié)點都已經(jīng)更新,刪除剩余的節(jié)點 // 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) { // 查找舊子序列中的節(jié)點在新子序列中的索引 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++ } }
每次遍歷拿到舊子節(jié)點的值prevChild
,如果patched >= toBePatched
也就是說新子序列已經(jīng)更新的節(jié)點數(shù)量大于等于待更新的節(jié)點數(shù)量,說明新子序列的所有節(jié)點更新完畢,舊子序列中剩余的節(jié)點刪除即可。
如果每次循環(huán)拿到的舊子節(jié)點的值的key
存在,則查找舊子序列中的節(jié)點在新子序列中的索引標記為newIndex
。如果key
不存在,則遍歷新子序列待更新的節(jié)點,如果prevChild
和遍歷新子序列待更新的節(jié)點有相同的節(jié)點,則將索引賦值給newIndex
。接著判斷newIndex
是否存在,如果不存在,則說明新子序列中找不到舊子序列中的這個節(jié)點,則直接刪除。如果存在,則更新新子序列中的元素在舊子序列中的索引,這里 ‘+1’ 偏移是為了避免i為0的特殊情況,影響后面最長遞增子序列的求解,因為我們現(xiàn)在規(guī)定的newIndexToOldIndexMap
中的元素為0說明這個元素沒有對應(yīng)的老節(jié)點,如果不'+1'我們避免不了i
為0的情況,這樣就影響了最長遞增子序列的求解。我們看下newIndexToOldIndexMap
重新賦值之后的結(jié)果
maxNewIndexSoFar
存儲的是上次舊值的newIndex,如果不是一直遞增 則說明有移動,則moved
設(shè)置為ture
。然后將newIndex
對應(yīng)的新節(jié)點和prevChild
老節(jié)點進行patch
,然后patched++
記錄更新的次數(shù)。
我們繼續(xù)看下面的代碼
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : EMPTY_ARR j = increasingNewIndexSequence.length - 1 // 倒序遍歷 以便使用更新的節(jié)點作為錨點 for (i = toBePatched - 1; i >= 0; i--) { const nextIndex = s2 + i const nextChild = c2[nextIndex] as VNode // 錨點指向上一個更新的節(jié)點, 如果nextIndex超過新節(jié)點的長度,則指向parentAnchor const anchor = nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor if (newIndexToOldIndexMap[i] === 0) { // mount new // 掛載新節(jié)點 patch( null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) } else if (moved) { // 沒有最長遞增子序列或者當前節(jié)點索引不在最長遞增子序列中, 需要移動 if (j < 0 || i !== increasingNewIndexSequence[j]) { move(nextChild, container, anchor, MoveType.REORDER) } else { j-- } } }
首先判斷是否需要移動,如果需要移動怎么才能以移動最少的步數(shù)完成更新呢?這就需要用到最長遞增子序列(getSequence
這個方法代碼我們貼到文章最后)。我們得到了最長遞增子序列的索引值的集合increasingNewIndexSequence
,我們看下結(jié)果。
根據(jù)結(jié)果我們發(fā)現(xiàn)在newIndexToOldIndexMap
中只有索引為0和1的節(jié)點是遞增的,所以只有這兩個對應(yīng)的舊的子序列的節(jié)點是不需要移動的,其他的則需要移動。
倒序遍歷。為什么要倒序遍歷呢?因為我們將節(jié)點插入到已經(jīng)更新的節(jié)點前面(從后往前遍歷可以始終保持當前遍歷的節(jié)點的下一個節(jié)點是更新過的)這里使用的是insertBefore
。
比如這個例子節(jié)點‘G’就要插入到節(jié)點‘E’的前面,節(jié)點‘E’是已經(jīng)更新過的了。
繼續(xù)往前推進,節(jié)點‘B’不在最長遞增子序列increasingNewIndexSequence
中,所以需要移動。然后拿到節(jié)點‘B’對應(yīng)的el插入到節(jié)點‘G’的前面。這個節(jié)點‘B’的el我們從節(jié)點‘B’的Vnode
上面就可以獲取到了。因為當兩個新舊節(jié)點進行對比的時候會進行下面的操作
以上就是我們要介紹的Vue3的diff算法的核心內(nèi)容
總結(jié)
有序的情況比較簡單,我們就直接說無序的情況。
1.根據(jù)key
建立新子序列的索引圖 keyToNewIndexMap
通過遍歷新子序列的節(jié)點 將key
和index
映射
2.根據(jù)新子序列中待更新節(jié)點的數(shù)量toBePatched
創(chuàng)建數(shù)組newIndexToOldIndexMap
數(shù)組初始化為0
這個數(shù)組就是保存新子序列中的節(jié)點在舊子序列中的索引位置。
3.遍歷舊子節(jié)點 拿舊的子節(jié)點去keyToNewIndexMap
中找對應(yīng)新子節(jié)點的位置
- 如果找不到 則說明這個節(jié)點在新的子節(jié)點中沒有則刪除
- 找到了之后則更新
newIndexToOldIndexMap
,數(shù)組中的元素被重新賦值為新子序列中的節(jié)點在舊子序列中的索引位置,為0的元素說明這個節(jié)點是新增的。 - 將新舊子節(jié)點對比更新
4.通過最長遞增子序列找到那些節(jié)點是需要移動的,哪些節(jié)點是不需要的移動的
最長遞增子序列
// 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 // 存儲元素對應(yīng)的索引值 result.push(i) continue } // 不滿足 則執(zhí)行二分搜索 u = 0 v = result.length - 1 // 查找第一個比arrI小的節(jié)點,更新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算法的簡單解刨的詳細內(nèi)容,更多關(guān)于Vue3 diff算法的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
vue中v-for和v-if一起使用之使用compute的示例代碼
這篇文章主要介紹了vue中v-for和v-if一起使用之使用compute的相關(guān)知識,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-05-05vue template中slot-scope/scope的使用方法
今天小編就為大家分享一篇vue template中slot-scope/scope的使用方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-09-09VUE搭建分布式醫(yī)療掛號系統(tǒng)后臺管理頁面示例步驟
這篇文章主要為大家介紹了分布式醫(yī)療掛號系統(tǒng)之搭建后臺管理系統(tǒng)頁面,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-04-04vue3獲取ref實例結(jié)合ts的InstanceType問題
這篇文章主要介紹了vue3獲取ref實例結(jié)合ts的InstanceType問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2023-03-03