Vue3快速diff算法的處理過程
一、為什么要使用diff算法
新舊vnode節(jié)點都有一組子節(jié)點的情況下，如果不使用diff算法處理則渲染器的做法是，將舊的子節(jié)點全部卸載，再掛載新的子節(jié)點，并沒有考慮到節(jié)點的復用情況，比如下面的兩組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標簽中的文本內容即可。 Vue使用diff算法的原因就是為了避免全量更新子節(jié)點，盡可能的去復用或者使用較少的操作去完成節(jié)點的更新。
二、如何復用子節(jié)點
1.判斷是否可復用：
觀察以下兩個新舊節(jié)點：他們的類型相同都是p元素，并且其內容其實也沒有變化，只是元素的順序發(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é)點是我們可以復用的，可以給其加上key屬性，當新舊節(jié)點的key值相同時，則證明他們是同一個子節(jié)點，可以復用。
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.對可復用節(jié)點的處理：
節(jié)點可復用并不意味著只需要簡單的處理新舊子節(jié)點的順序變化，子節(jié)點的內容可能也會發(fā)生變動，所以在移動之前需要打補丁確保內容更新：我們需要對前面處理子節(jié)點更新的patchChildren進行完善，主要處理其中新舊子節(jié)點都是多個的情況，此時我們才需要使用diff算法處理,其中再使用patch函數(shù)去更新可復用節(jié)點,具體的處理過程在下文中進行描述：
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é)點，應用diff算法處理
//省略diff算法代碼
//diff中會使用patch去更新可復用元素
} else if (typeof n1.children === 'string') {
//省略代碼
}
}
}
三、Vue3快速diff算法的處理過程
1.預處理:處理兩組子節(jié)點中首尾節(jié)點可復用的情況
比如下面的情況：
有三個節(jié)點key值相同，可以復用，并且他們在子節(jié)點中的相對順序也沒有發(fā)生變化，p-1在最前面，p-2和p-3在最后面。所以他們并不需要移動，只需要處理中間的節(jié)點。
處理前置節(jié)點：
設置一個索引j從0開始使用while循環(huán)尋找相同的前置節(jié)點：如果是key相同的節(jié)點，調用patch函數(shù)打補丁更新其中的內容，直到使用同一個索引取到的新舊子節(jié)點key值不同
處理后置節(jié)點：
拿到新舊子節(jié)點最后一個元素的索引oldEnd和newEnd，使用while從兩組節(jié)點尾部往上遍歷，如果是key相同的節(jié)點則調用patch函數(shù)打補丁更新其中的內容，知道取不到相同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、預處理之后的兩種情況：需要刪除節(jié)點、需要新增節(jié)點
如何判斷存在需要刪除或者新增的節(jié)點? 在預處理之后我們可以獲得的信息有：
- 處理前置節(jié)點的時候獲得的索引
j - 處理后置節(jié)點得到的兩個索引
newEnd、oldEnd利用以上索引可以做出判斷：
需要新增節(jié)點的情況：oldEnd < j 以及 newEnd >= j：
需要刪除節(jié)點的情況：oldEnd >= j 以及 newEnd < j：
在前文:
Vuejs 數(shù)據(jù)是如何渲染的？渲染器的簡單實現(xiàn)
Vue 的渲染器是如何對節(jié)點進行掛載和更新的中實現(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
//調用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++])
}
}
}
如上所示，當j<=oldEnd時循環(huán)使用umount卸載對應的節(jié)點即可。
在實際過程中，很少會有像上述簡單的預處理即可完成大部分工作的情況，這個時候就需要進行進一步的判斷： 比如以下情況：
在經(jīng)過預處理之后，只有首尾兩個節(jié)點被正確更新了，仍然會有多數(shù)節(jié)點沒有被更新。
預處理之后后續(xù)需要做的是:
- 判斷節(jié)點是否需要移動，移動節(jié)點；
- 如果有需要添加或者移除的節(jié)點進行處理；
3.判斷節(jié)點是否需要移動：
1.構建source數(shù)組
source數(shù)組需要去存儲新的子節(jié)點對應的舊子節(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++])
}
//預處理完畢后
} else{
//初始化source數(shù)組
const count = newEnd - j + 1
const source = new Array(count)
source.fill(-1)
}
}
source數(shù)組的長度等于預處理之后剩余節(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 值的可復用節(jié)點
if (oldVNode.key === newVNode.key) {
// 調用 patch 進行更新
patch(oldVNode, newVNode, container)
// 最后填充 source 數(shù)組
source[k - newStart] = i
}
}
}
以上做法時間復雜度為O(n^2),在子節(jié)點數(shù)量增加時會存在性能問題。 優(yōu)化的辦法是先遍歷新的一組子節(jié)點，根據(jù)子節(jié)點的位置和key生成一張索引表，然后再遍歷舊的一組子節(jié)點，利用節(jié)點的key在索引表中找到對應的新子節(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)化后的代碼如上所示:
首先將預處理之后的j值作為遍歷新舊節(jié)點開始時的索引，定義一個對象keyIndex作為索引表，遍歷預處理之后剩余的一組新子節(jié)點，將新子節(jié)點newChildren[i]的key值與其位置索引放入索引表中。 遍歷舊子節(jié)點，在遍歷時，我們可以通過當前節(jié)點的key去keyIndex索引表中獲取從而拿到當前遍歷的舊子節(jié)點的oldChildren[i]對應的新節(jié)點的位置keyIndex[oldVNode.key],如果位置存在，說明節(jié)點可復用，使用patch打補丁，并且使用當前舊節(jié)點的索引i對source數(shù)組進行填充。
2.標識是否需要移動節(jié)點
需要添加標識有:
- 是否需要移動
moved: 用于標識是否有需要移動的節(jié)點， - 當前新子節(jié)點的位置
pos: 用于記錄遍歷舊子節(jié)點中遇到的最大的索引值k，如果此次遍歷的k值大于上一次的，說明相對位置正確無需移動, - 已經(jīng)更新過的節(jié)點數(shù)量
patched：當patched大于source數(shù)組的長度即newEnd - j + 1時說明所有可復用節(jié)點已經(jīng)處理完畢，還有一些舊子節(jié)點需要執(zhí)行卸載操作， 代碼如下，我們在每一次更新節(jié)點內容后遞增patched++記錄處理數(shù)量，并對moved和pos的值進行處理。
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去標記了是否有至少一個子節(jié)點需要移動，當moved為true時，我們需要配合source數(shù)組中的最長遞增子序列去移動節(jié)點，否則直接不用再去使用diff。
1.最長遞增子序列：
什么是最長遞增子序列 遞增子序列就是在一個序列中，從左到右依次找出更大的值所構成的序列，在一個序列中可能存在多個遞增子序列，最長遞增子序列就是其中長度最長的那個。 例如 在上面的例子中我們得到的source數(shù)組為[2, 3, 1, -1],則其最長遞增子序列為[2,3]，我們通過處理得到了對應的舊子節(jié)點的索引[0, 1],即最長遞增子序列對應的新子節(jié)點的索引。
如上最長遞增子序列對應的舊節(jié)點為key為p-3、p-4，對應在新子節(jié)點的位置為0，1。
最長遞增子序列的意義：通過最長遞增子序列得到的索引可以提示我們哪些元素的相對位置，在子節(jié)點更新后并未發(fā)生變化，我們可以保留這些節(jié)點的相對位置，然后去處理和移動其他位置。如上p-3和p-4的相對位置在更新之后并未發(fā)生變化，即新節(jié)點中的索引為0和1的元素不需要移動。這里我們省略求最長遞增子序列的方法，直接將其當作函數(shù)lis處理source數(shù)組的結果
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遞減并再次進行比較
完善patchKeyedChildren去處理這幾種情況:
function patchKeyedChildren(n1, n2, container) {
//省略預處理和構造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é)點，應該將其掛載
} else if (i !== seq[j]) {
// 說明該節(jié)點需要移動
} else {
// 當 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)
}
代碼如上所示：當新子節(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é)點不需要移動的情況 對于p-3和p-4來說，source[i] !== -1,并且i === seq[s]，即節(jié)點無需移動只需更新s的值即可
s--
依此類推直到循環(huán)結束，子節(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é)點，應該將其掛載
// 該節(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 {
// 當 i === seq[j] 時，說明該位置的節(jié)點不需要移動
// 并讓 s 指向下一個位置
s--
}
}
}
}
總結：
使用
diff算法的原因：- 傳統(tǒng)的 DOM 更新方法會在有新舊子節(jié)點時卸載舊節(jié)點并掛載新節(jié)點，這種方法沒有考慮到節(jié)點的復用可能性。
diff算法通過比較新舊節(jié)點的差異來復用節(jié)點，從而優(yōu)化性能。
- 傳統(tǒng)的 DOM 更新方法會在有新舊子節(jié)點時卸載舊節(jié)點并掛載新節(jié)點，這種方法沒有考慮到節(jié)點的復用可能性。
節(jié)點復用依據(jù):key：
- 節(jié)點復用是通過比較節(jié)點的
key和類型來實現(xiàn)的。相同的key和類型表明兩個節(jié)點可以被視為同一個，從而復用以減少 DOM 操作。
- 節(jié)點復用是通過比較節(jié)點的
Vue 3 diff算法的過程：
- 預處理階段：處理首尾節(jié)點，找出新舊兩種子節(jié)點中首尾可復用的節(jié)點并更新。
- 處理理想情況下新增和刪除節(jié)點：若通過預處理有一組節(jié)點已經(jīng)更新完畢，證明新的一組子節(jié)點只需新增或刪除部分節(jié)點即可完成更新。
- 構造source數(shù)組：通過遍歷新舊兩組子節(jié)點，構造一個source數(shù)組,去存儲新的子節(jié)點對應的舊子節(jié)點的位置索引，并在此過程中判斷是否需要使用diff算法處理移動。
- 節(jié)點位置移動：根據(jù)最長遞增子序列判斷具體的某個節(jié)點是否需要新增或者移動，在需要時移動節(jié)點以匹配新的子節(jié)點順序。
diff算法帶來的效率提升：
- 算法避免了全量的 DOM 更新，通過巧妙的方法判斷哪些節(jié)點需要更新、移動或重新掛載，從而降低了全量更新的成本和時間。
以上就是Vue3快速diff算法的處理過程的詳細內容，更多關于Vue3快速diff算法的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了vue3中關于路由hash與History的設置方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
這篇文章主要介紹了vue-cli-瀏覽器實現(xiàn)熱更新,最常用的是webpack-dev-server，它是一個小型的Node.js?Express服務器，它使用webpack-dev-middleware來服務于webpack的包，本文結合實例代碼介紹的非常詳細，需要的朋友參考下吧2024-03-03
解決VUEX的mapState/...mapState等取值問題
這篇文章主要介紹了解決VUEX的mapState/...mapState等取值問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-07-07
這篇文章主要介紹了vue數(shù)組雙向綁定問題及$set用法說明，具有很好的參考價值，希望大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-09-09
vue利用全局導航守衛(wèi)作登錄后跳轉到未登錄前指定頁面的實例代碼
這篇文章主要介紹了vue利用全局導航守衛(wèi)作登錄后跳轉到未登錄前指定頁面,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-05-05
最近嘗試上手Vue3+TS+Vite,對比起Vue2有些不適應,但還是真香,下面這篇文章主要給大家介紹了關于vue3+ts+vite2項目的相關資料,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2022-09-09
Vue-Router如何動態(tài)更改當前頁url query
這篇文章主要介紹了Vue-Router如何動態(tài)更改當前頁url query問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-08-08
文章介紹了如何在Vue中通過Click方法獲取原事件的參數(shù),包括默認參數(shù)、自定義參數(shù)以及如何同時獲取原生事件和自定義參數(shù)的方法2024-12-12
這篇文章主要介紹了vue跳轉同一個路由參數(shù)不同的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
這篇文章主要介紹了npm install報錯缺少python問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06