Vue3快速diff算法的處理過程
一、為什么要使用diff算法
新舊vnode節(jié)點都有一組子節(jié)點的情況下,如果不使用diff算法處理則渲染器的做法是,將舊的子節(jié)點全部卸載,再掛載新的子節(jié)點,并沒有考慮到節(jié)點的復(fù)用情況,比如下面的兩組vnode
const newVnode = { type: 'div', children: [ { type: 'p', children: '1' }, { type: 'p', children: '2' }, { type: 'p', children: '3' }, ] } const oldVnode = { type: 'div', children: [ { type: 'p', children: '4' }, { type: 'p', children: '5' }, { type: 'p', children: '6' } ] }
實際上并不需要去全部卸載然后掛載新的子節(jié)點,只需要替換子節(jié)點中p
標(biāo)簽中的文本內(nèi)容即可。 Vue使用diff算法的原因就是為了避免全量更新子節(jié)點,盡可能的去復(fù)用或者使用較少的操作去完成節(jié)點的更新。
二、如何復(fù)用子節(jié)點
1.判斷是否可復(fù)用:
觀察以下兩個新舊節(jié)點:他們的類型相同都是p
元素,并且其內(nèi)容其實也沒有變化,只是元素的順序發(fā)生了變動,這種情況我們完全可以復(fù)用新舊節(jié)點:
const newVnode = { type: 'div', children: [ { type: 'p', children: '1' }, { type: 'p', children: '2' }, { type: 'p', children: '3' }, ] } const oldVnode = { type: 'div', children: [ { type: 'p', children: '3' }, { type: 'p', children: '2' }, { type: 'p', children: '1' } ] }
為了能夠識別出哪些子節(jié)點是我們可以復(fù)用的,可以給其加上key屬性,當(dāng)新舊節(jié)點的key
值相同時,則證明他們是同一個子節(jié)點,可以復(fù)用。
const newVnode = { type: 'div', children: [ { type: 'p', children: '1', key:1 }, { type: 'p', children: '2', key:2 }, { type: 'p', children: '3', key:3 }, ] } const oldVnode = { type: 'div', children: [ { type: 'p', children: '3', key:3 }, { type: 'p', children: '2', key:2 }, { type: 'p', children: '1', key:1 }, ] }
2.對可復(fù)用節(jié)點的處理:
節(jié)點可復(fù)用并不意味著只需要簡單的處理新舊子節(jié)點的順序變化,子節(jié)點的內(nèi)容可能也會發(fā)生變動,所以在移動之前需要打補(bǔ)丁確保內(nèi)容更新:我們需要對前面處理子節(jié)點更新的patchChildren
進(jìn)行完善,主要處理其中新舊子節(jié)點都是多個的情況,此時我們才需要使用diff算法處理,其中再使用patch
函數(shù)去更新可復(fù)用節(jié)點,具體的處理過程在下文中進(jìn)行描述:
function patchChildren(n1, n2, container) { if (typeof n2.children === 'string') { //省略代碼 } else if (Array.isArray(n2.children)) { //新子節(jié)點是一組節(jié)點 if (Array.isArray(n1.children)) { //舊子節(jié)點也是一組節(jié)點,應(yīng)用diff算法處理 //省略diff算法代碼 //diff中會使用patch去更新可復(fù)用元素 } else if (typeof n1.children === 'string') { //省略代碼 } } }
三、Vue3快速diff算法的處理過程
1.預(yù)處理:處理兩組子節(jié)點中首尾節(jié)點可復(fù)用的情況
比如下面的情況:
有三個節(jié)點key
值相同,可以復(fù)用,并且他們在子節(jié)點中的相對順序也沒有發(fā)生變化,p-1
在最前面,p-2
和p-3
在最后面。所以他們并不需要移動,只需要處理中間的節(jié)點。
處理前置節(jié)點:
設(shè)置一個索引j從0開始使用while循環(huán)尋找相同的前置節(jié)點:如果是key相同的節(jié)點,調(diào)用patch函數(shù)打補(bǔ)丁更新其中的內(nèi)容,直到使用同一個索引取到的新舊子節(jié)點key值不同
處理后置節(jié)點:
拿到新舊子節(jié)點最后一個元素的索引oldEnd
和newEnd
,使用while從兩組節(jié)點尾部往上遍歷,如果是key相同的節(jié)點則調(diào)用patch
函數(shù)打補(bǔ)丁更新其中的內(nèi)容,知道取不到相同key的節(jié)點為止。
我們使用一個patchKeyedChildren
函數(shù)去實現(xiàn)上述過程:
function patchKeyedChildren(n1, n2, container) { const oldChildren = n1.children const newChildren = n2.children //處理前置節(jié)點 let j = 0 let oldVNode = oldChildren[j] let newVNode = newChildren[j] while (oldVNode.key === newVNode.key) { patch(oldVNode, newVNode, container) j++ oldVNode = oldChildren[j] newVNode = newChildren[j] } //處理后置節(jié)點 //將新舊節(jié)點的索引指向最后一個子節(jié)點 let oldEnd = oldChildren.length - 1 let newEnd = newChildren.length - 1 oldVNode = oldChildren[oldEnd] newVNode = newChildren[newEnd] while (oldVNode.key === newVNode.key) { patch(oldVNode, newVNode, container) oldEnd-- newEnd-- oldVNode = oldChildren[oldEnd] newVNode = newChildren[newEnd] } }
2、預(yù)處理之后的兩種情況:需要刪除節(jié)點、需要新增節(jié)點
如何判斷存在需要刪除或者新增的節(jié)點? 在預(yù)處理之后我們可以獲得的信息有:
- 處理前置節(jié)點的時候獲得的索引
j
- 處理后置節(jié)點得到的兩個索引
newEnd
、oldEnd
利用以上索引可以做出判斷:
需要新增節(jié)點的情況:oldEnd < j 以及 newEnd >= j:
需要刪除節(jié)點的情況:oldEnd >= j 以及 newEnd < j:
在前文:
Vuejs 數(shù)據(jù)是如何渲染的?渲染器的簡單實現(xiàn)
Vue 的渲染器是如何對節(jié)點進(jìn)行掛載和更新的中實現(xiàn)的patch和mountElement方法并不能指定位置去掛載節(jié)點,為了能夠處理指定節(jié)點位置插入節(jié)點,我們需要為其增加一個參數(shù)anchor,傳入錨點元素。
function patch(n1, n2, container, anchor) { //...省略代碼 if (typeof type === 'string') { if (!n1) { //在此處傳入錨點以支持新節(jié)點按位置插入 mountElement(n2, container, anchor) } else { patchElement(n1, n2) } } else if (type === Text) { //...省略代碼 } function mountElement(vnode, container, anchor) { //省略代碼 //給insert方法傳遞錨點元素 insert(el, container, anchor) } const renderer = createRenderer({ //...省略代碼 insert(el, parent, anchor = null) { //根據(jù)錨點元素插入節(jié)點 parent.insertBefore(el, anchor) } })
接下來我們需要完善patchKeyedChildren去處理上述兩種情況:
需要新增節(jié)點時:
function patchKeyedChildren(n1, n2, container) { const oldChildren = n1.children const newChildren = n2.children //需要插入新節(jié)點 if (j > oldEnd && j <= newEnd){ //取得錨點索引 const anchorIndex = newEnd + 1 //取得錨點元素 const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null //調(diào)用patch掛載新節(jié)點 while (j <= newEnd) { patch(null, newChildren[j++], container, anchor) } } }
代碼如上,我們首先使用newEnd+1
獲取錨點索引,并且使用newChildren[anchorIndex].el
去獲取到錨點元素,其中還做了一個判斷如果newEnd
是尾部節(jié)點那不需要提供錨點元素直接處理即可。
需要刪除節(jié)點時:
function patchKeyedChildren(n1, n2, container) { const oldChildren = n1.children const newChildren = n2.children //需要插入新節(jié)點 if (j > oldEnd && j <= newEnd){ //...省略新增節(jié)點邏輯 }else if (j > newEnd && j <= oldEnd) { //卸載節(jié)點 while (j <= oldEnd) { unmount(oldChildren[j++]) } } }
如上所示,當(dāng)j<=oldEnd
時循環(huán)使用umount
卸載對應(yīng)的節(jié)點即可。
在實際過程中,很少會有像上述簡單的預(yù)處理即可完成大部分工作的情況,這個時候就需要進(jìn)行進(jìn)一步的判斷: 比如以下情況:
在經(jīng)過預(yù)處理之后,只有首尾兩個節(jié)點被正確更新了,仍然會有多數(shù)節(jié)點沒有被更新。
預(yù)處理之后后續(xù)需要做的是:
- 判斷節(jié)點是否需要移動,移動節(jié)點;
- 如果有需要添加或者移除的節(jié)點進(jìn)行處理;
3.判斷節(jié)點是否需要移動:
1.構(gòu)建source數(shù)組
source數(shù)組需要去存儲新的子節(jié)點對應(yīng)的舊子節(jié)點的位置索引,然后去計算一個最長遞增子序列,通過最長遞增子序列去完成DOM的移動操作
初始化source數(shù)組:
function patchKeyedChildren(n1, n2, container) { const oldChildren = n1.children const newChildren = n2.children //需要插入新節(jié)點 if (j > oldEnd && j <= newEnd){ //...省略新增節(jié)點邏輯 }else if (j > newEnd && j <= oldEnd) { //卸載節(jié)點 while (j <= oldEnd) { unmount(oldChildren[j++]) } //預(yù)處理完畢后 } else{ //初始化source數(shù)組 const count = newEnd - j + 1 const source = new Array(count) source.fill(-1) } }
source數(shù)組的長度等于預(yù)處理之后剩余節(jié)點的長度也就是newEnd - j + 1
,我們使用fill將數(shù)組中的元素填充為-1
初始化其中的值
填充source數(shù)組: 使用新子節(jié)點在舊子節(jié)點中的索引去填充source數(shù)組
如上key為p-3
的新子節(jié)點在舊子節(jié)點中的索引為2
,所以source數(shù)組的第一項需要被填充為2
,key
為p-4
的新子節(jié)點在舊子節(jié)點為3
,所以source數(shù)組的第二項的值為3
,以此類推。 在這個過程中需要嵌套兩個for循環(huán)去遍歷新舊子節(jié)類似下面的過程:
for (let i = oldStart; i <= oldEnd; i++) { const oldVNode = oldChildren[i] // 遍歷新的一組子節(jié)點 for (let k = newStart; k <= newEnd; k++) { const newVNode = newChildren[k] // 找到擁有相同 key 值的可復(fù)用節(jié)點 if (oldVNode.key === newVNode.key) { // 調(diào)用 patch 進(jìn)行更新 patch(oldVNode, newVNode, container) // 最后填充 source 數(shù)組 source[k - newStart] = i } } }
以上做法時間復(fù)雜度為O(n^2)
,在子節(jié)點數(shù)量增加時會存在性能問題。 優(yōu)化的辦法是先遍歷新的一組子節(jié)點,根據(jù)子節(jié)點的位置和key生成一張索引表,然后再遍歷舊的一組子節(jié)點,利用節(jié)點的key在索引表中找到對應(yīng)的新子節(jié)點的位置,以此填充source數(shù)組。
const oldStart = j const newStart = j const keyIndex = {} for(let i = newStart; i <= newEnd; i++) { keyIndex[newChildren[i].key] = i } for(let i = oldStart; i <= oldEnd; i++) { oldVNode = oldChildren[i] const k = keyIndex[oldVNode.key] if (typeof k !== 'undefined') { newVNode = newChildren[k] patch(oldVNode, newVNode, container) source[k - newStart] = i } else { unmount(oldVNode) } }
優(yōu)化后的代碼如上所示:
首先將預(yù)處理之后的j
值作為遍歷新舊節(jié)點開始時的索引,定義一個對象keyIndex
作為索引表,遍歷預(yù)處理之后剩余的一組新子節(jié)點,將新子節(jié)點newChildren[i]
的key值與其位置索引放入索引表中。 遍歷舊子節(jié)點,在遍歷時,我們可以通過當(dāng)前節(jié)點的key
去keyIndex
索引表中獲取從而拿到當(dāng)前遍歷的舊子節(jié)點的oldChildren[i]
對應(yīng)的新節(jié)點的位置keyIndex[oldVNode.key]
,如果位置存在,說明節(jié)點可復(fù)用,使用patch
打補(bǔ)丁,并且使用當(dāng)前舊節(jié)點的索引i
對source數(shù)組進(jìn)行填充。
2.標(biāo)識是否需要移動節(jié)點
需要添加標(biāo)識有:
- 是否需要移動
moved
: 用于標(biāo)識是否有需要移動的節(jié)點, - 當(dāng)前新子節(jié)點的位置
pos
: 用于記錄遍歷舊子節(jié)點中遇到的最大的索引值k
,如果此次遍歷的k
值大于上一次的,說明相對位置正確無需移動, - 已經(jīng)更新過的節(jié)點數(shù)量
patched
:當(dāng)patched
大于source數(shù)組的長度即newEnd - j + 1
時說明所有可復(fù)用節(jié)點已經(jīng)處理完畢,還有一些舊子節(jié)點需要執(zhí)行卸載操作, 代碼如下,我們在每一次更新節(jié)點內(nèi)容后遞增patched++
記錄處理數(shù)量,并對moved
和pos
的值進(jìn)行處理。
const count = newEnd - j + 1 // 新的一組子節(jié)點中剩余未處理節(jié)點的數(shù)量 const source = new Array(count) source.fill(-1) const oldStart = j const newStart = j let moved = false let pos = 0 const keyIndex = {} for(let i = newStart; i <= newEnd; i++) { keyIndex[newChildren[i].key] = i } let patched = 0 for(let i = oldStart; i <= oldEnd; i++) { oldVNode = oldChildren[i] if (patched < count) { const k = keyIndex[oldVNode.key] if (typeof k !== 'undefined') { newVNode = newChildren[k] patch(oldVNode, newVNode, container) patched++ source[k - newStart] = i // 判斷是否需要移動 if (k < pos) { moved = true } else { pos = k } } else { // 沒找到 unmount(oldVNode) } } else { unmount(oldVNode) } }
4.處理節(jié)點的移動:
先前我們使用moved
去標(biāo)記了是否有至少一個子節(jié)點需要移動,當(dāng)moved為true
時,我們需要配合source數(shù)組中的最長遞增子序列去移動節(jié)點,否則直接不用再去使用diff。
1.最長遞增子序列:
什么是最長遞增子序列 遞增子序列就是在一個序列中,從左到右依次找出更大的值所構(gòu)成的序列,在一個序列中可能存在多個遞增子序列,最長遞增子序列就是其中長度最長的那個。 例如 在上面的例子中我們得到的source數(shù)組為[2, 3, 1, -1]
,則其最長遞增子序列為[2,3]
,我們通過處理得到了對應(yīng)的舊子節(jié)點的索引[0, 1]
,即最長遞增子序列對應(yīng)的新子節(jié)點的索引。
如上最長遞增子序列對應(yīng)的舊節(jié)點為key為p-3
、p-4
,對應(yīng)在新子節(jié)點的位置為0
,1
。
最長遞增子序列的意義:通過最長遞增子序列得到的索引可以提示我們哪些元素的相對位置,在子節(jié)點更新后并未發(fā)生變化,我們可以保留這些節(jié)點的相對位置,然后去處理和移動其他位置。如上p-3和p-4的相對位置在更新之后并未發(fā)生變化,即新節(jié)點中的索引為0
和1
的元素不需要移動。這里我們省略求最長遞增子序列的方法,直接將其當(dāng)作函數(shù)lis
處理source數(shù)組
的結(jié)果
const seq = lis(source)
2.根據(jù)最長遞增子序列移動節(jié)點:
創(chuàng)建兩個索引輔助移動:
- 索引 i 指向新的一組子節(jié)點中的最后一個節(jié)點。
- 索引 s 指向最長遞增子序列中的最后一個元素。
我們需要去判斷以下的情況:
source[i] === -1
: 節(jié)點不存在,需要掛載新節(jié)點i!==seq[s]
:節(jié)點需要移動,i===seq[s]
:節(jié)點無需移動,將s遞減并再次進(jìn)行比較
完善patchKeyedChildren
去處理這幾種情況:
function patchKeyedChildren(n1, n2, container) { //省略預(yù)處理和構(gòu)造source數(shù)組代碼 if (moved) { const seq = lis(source) // s 指向最長遞增子序列的最后一個值 let s = seq.length - 1 let i = count - 1 for (i; i >= 0; i--) { if (source[i] === -1) { // 說明索引為 i 的節(jié)點是全新的節(jié)點,應(yīng)該將其掛載 } else if (i !== seq[j]) { // 說明該節(jié)點需要移動 } else { // 當(dāng) i === seq[j] 時,說明該位置的節(jié)點不需要移動 // 并讓 s 指向下一個位置 s-- } } } } }
節(jié)點不存在情況具體處理
if (source[i] === -1) { // 該節(jié)點在新的一組子節(jié)點中的真實位置索引 const pos = i + newStart const newVNode = newChildren[pos] // 該節(jié)點下一個節(jié)點的位置索引 const nextPos = pos + 1 // 錨點 const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null patch(null, newVNode, container, anchor) }
代碼如上所示:當(dāng)新子節(jié)點是新節(jié)點時直接獲取,該節(jié)點的位置,即索引,并且加一獲得錨點用于掛載元素,如果元素本身就是最后一個元素 nextPos < newChildren.length
,則無需錨點。 此時p-7
處理完成,繼續(xù)向上處理p-2
節(jié)點需要移動的情況
if (i !== seq[s]) { // 該節(jié)點在新的一組子節(jié)點中的真實位置索引 const pos = i + newStart const newVNode = newChildren[pos] // 該節(jié)點下一個節(jié)點的位置索引 const nextPos = pos + 1 // 錨點 const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null patch(null, newVNode, container, anchor) }
邏輯和節(jié)點不存在的情況類似,只是移動節(jié)點通過insert
函數(shù)去完成。此時處理的結(jié)果如下
節(jié)點不需要移動的情況 對于p-3
和p-4
來說,source[i] !== -1
,并且i === seq[s]
,即節(jié)點無需移動只需更新s
的值即可
s--
依此類推直到循環(huán)結(jié)束,子節(jié)點全部更新完畢,該過程完整代碼如下:
if (moved) { const seq = lis(source) // s 指向最長遞增子序列的最后一個值 let s = seq.length - 1 let i = count - 1 for (i; i >= 0; i--) { if (source[i] === -1) { // 說明索引為 i 的節(jié)點是全新的節(jié)點,應(yīng)該將其掛載 // 該節(jié)點在新 children 中的真實位置索引 const pos = i + newStart const newVNode = newChildren[pos] // 該節(jié)點下一個節(jié)點的位置索引 const nextPos = pos + 1 // 錨點 const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null // 掛載 patch(null, newVNode, container, anchor) } else if (i !== seq[j]) { // 說明該節(jié)點需要移動 // 該節(jié)點在新的一組子節(jié)點中的真實位置索引 const pos = i + newStart const newVNode = newChildren[pos] // 該節(jié)點下一個節(jié)點的位置索引 const nextPos = pos + 1 // 錨點 const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null // 移動 insert(newVNode.el, container, anchor) } else { // 當(dāng) i === seq[j] 時,說明該位置的節(jié)點不需要移動 // 并讓 s 指向下一個位置 s-- } } } }
總結(jié):
使用
diff
算法的原因:- 傳統(tǒng)的 DOM 更新方法會在有新舊子節(jié)點時卸載舊節(jié)點并掛載新節(jié)點,這種方法沒有考慮到節(jié)點的復(fù)用可能性。
diff
算法通過比較新舊節(jié)點的差異來復(fù)用節(jié)點,從而優(yōu)化性能。
- 傳統(tǒng)的 DOM 更新方法會在有新舊子節(jié)點時卸載舊節(jié)點并掛載新節(jié)點,這種方法沒有考慮到節(jié)點的復(fù)用可能性。
節(jié)點復(fù)用依據(jù):key:
- 節(jié)點復(fù)用是通過比較節(jié)點的
key
和類型
來實現(xiàn)的。相同的key
和類型
表明兩個節(jié)點可以被視為同一個,從而復(fù)用以減少 DOM 操作。
- 節(jié)點復(fù)用是通過比較節(jié)點的
Vue 3 diff算法的過程:
- 預(yù)處理階段:處理首尾節(jié)點,找出新舊兩種子節(jié)點中首尾可復(fù)用的節(jié)點并更新。
- 處理理想情況下新增和刪除節(jié)點:若通過預(yù)處理有一組節(jié)點已經(jīng)更新完畢,證明新的一組子節(jié)點只需新增或刪除部分節(jié)點即可完成更新。
- 構(gòu)造source數(shù)組:通過遍歷新舊兩組子節(jié)點,構(gòu)造一個source數(shù)組,去存儲新的子節(jié)點對應(yīng)的舊子節(jié)點的位置索引,并在此過程中判斷是否需要使用diff算法處理移動。
- 節(jié)點位置移動:根據(jù)最長遞增子序列判斷具體的某個節(jié)點是否需要新增或者移動,在需要時移動節(jié)點以匹配新的子節(jié)點順序。
diff算法帶來的效率提升:
- 算法避免了全量的 DOM 更新,通過巧妙的方法判斷哪些節(jié)點需要更新、移動或重新掛載,從而降低了全量更新的成本和時間。
以上就是Vue3快速diff算法的處理過程的詳細(xì)內(nèi)容,更多關(guān)于Vue3快速diff算法的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
vue3中關(guān)于路由hash與History的設(shè)置
這篇文章主要介紹了vue3中關(guān)于路由hash與History的設(shè)置方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-08-08解決VUEX的mapState/...mapState等取值問題
這篇文章主要介紹了解決VUEX的mapState/...mapState等取值問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-07-07vue利用全局導(dǎo)航守衛(wèi)作登錄后跳轉(zhuǎn)到未登錄前指定頁面的實例代碼
這篇文章主要介紹了vue利用全局導(dǎo)航守衛(wèi)作登錄后跳轉(zhuǎn)到未登錄前指定頁面,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-05-05Vue-Router如何動態(tài)更改當(dāng)前頁url query
這篇文章主要介紹了Vue-Router如何動態(tài)更改當(dāng)前頁url query問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-08-08