DIff 算法 -帶圖-,請收藏-
前言
面試官:" 你瞭解虛擬DOM(Virtual DOM)
跟Diff算法
嗎, 請描述一下它們 ";
我:"額,... 鵝, 那個", 完了😰, 突然智商不在線, 沒組織好語言沒答好或者壓根就答不出來;
所以這次我總結一下相關的知識點, 讓你可以有一個清晰的認知之餘也會讓你在今後遇到這種情況可以坦然自若, 應付自如, 遊刃有餘:
相關知識點:
-
虛擬 DOM(Virtual DOM):
-
什麼是虛擬 dom
-
爲什麼要使用虛擬 dom
-
虛擬 DOM 庫
-
DIFF 算法:
-
init 函數
-
h 函數
-
patch 函數
-
patchVnode 函數
-
updateChildren 函數
-
snabbDom 源碼
虛擬 DOM(Virtual DOM)
什麼是虛擬 DOM
一句話總結虛擬 DOM 就是一個用來描述真實 DOM 的 javaScript 對象, 這樣說可能不夠形象, 那我們來舉個🌰: 分別用代碼來描述真實 DOM 以及虛擬 DOM
真實 DOM:
對應的虛擬 DOM:
控制檯打印出來的 Vnode:
h 函數生成的虛擬 DOM 這個 JS 對象 (Vnode) 的源碼:
補充:
上面的 h 函數大家可能有點熟悉的感覺但是一時間也沒想起來, 沒關係我來幫大夥回憶;
開發中常見的現實場景, render 函數渲染:
爲什麼要使用虛擬 DOM
-
MVVM 框架解決視圖和狀態同步問題
-
模板引擎可以簡化視圖操作, 沒辦法跟蹤狀態
-
虛擬 DOM 跟蹤狀態變化
-
參考 github 上 virtual-dom 的動機描述
-
虛擬 DOM 可以維護程序的狀態, 跟蹤上一次的狀態
-
通過比較前後兩次狀態差異更新真實 DOM
-
跨平臺使用
-
瀏覽器平臺渲染 DOM
-
服務端渲染 SSR(Nuxt.js/Next.js), 前端是 vue 向, 後者是 react 向
-
原生應用 (Weex/React Native)
-
小程序 (mpvue/uni-app) 等
-
真實 DOM 的屬性很多,創建 DOM 節點開銷很大
-
虛擬 DOM 只是普通 JavaScript 對象,描述屬性並不需要很多,創建開銷很小
-
複雜視圖情況下提升渲染性能 (操作 dom 性能消耗大, 減少操作 dom 的範圍可以提升性能)
靈魂發問: 使用了虛擬 DOM 就一定會比直接渲染真實 DOM 快嗎? 答案當然是否定
的, 且聽我說:
舉例: 當一個節點變更時 DOMA->DOMB
上述情況:示例1
是創建一個DOMB
然後替換掉DOMA
;示例2
去創建虛擬DOM+DIFF算法
比對發現DOMB
跟DOMA
不是相同的節點, 最後還是創建一個DOMB
然後替換掉DOMA
; 可以明顯看出 1 是更快的, 同樣的結果, 2 還要去創建虛擬 DOM+DIFF 算啊對比 所以說使用虛擬 DOM 比直接操作真實 DOM 就一定要快這個說法是錯誤的,不嚴謹的
舉例: 當 DOM 樹裏面的某個子節點的內容變更時:
當一些複雜的節點, 比如說一個父節點裏面有多個子節點, 當只是一個子節點的內容發生了改變, 那麼我們沒有必要像示例1
重新去渲染這個DOM樹
, 這個時候虛擬DOM+DIFF算法
就能夠得到很好的體現, 我們通過示例2
使用虛擬DOM+Diff算法
去找出改變了的子節點更新它的內容就可以了
總結: 複雜視圖情況下提升渲染性能, 因爲虛擬DOM+Diff算法
可以精準找到 DOM 樹變更的地方, 減少 DOM 的操作 (重排重繪)
虛擬 dom 庫
-
Snabbdom
-
Vue.js2.x 內部使用的虛擬 DOM 就是改造的 Snabbdom
-
大約 200SLOC(single line of code)
-
通過模塊可擴展
-
源碼使用 TypeScript 開發
-
最快的 Virtual DOM 之一
-
virtual-dom
Diff 算法
在看完上述的文章之後相信大家已經對 Diff 算法有一個初步的概念, 沒錯, Diff 算法其實就是找出兩者之間的差異;
diff 算法首先要明確一個概念就是 Diff 的對象是虛擬 DOM(virtual dom),更新真實 DOM 是 Diff 算法的結果。
下面我將會手撕snabbdom
源碼核心部分爲大家打開Diff
的心, 給點耐心, 別關網頁, 我知道你們都是這樣:
snabbdom 的核心
-
init()
設置模塊. 創建patch()
函數 -
使用
h()
函數創建 JavaScript 對象(Vnode)
描述真實DOM
-
patch()
比較新舊兩個Vnode
-
把變化的內容更新到
真實DOM樹
init 函數
init 函數時設置模塊, 然後創建 patch() 函數, 我們先通過場景案例來有一個直觀的體現:
當 init 使用了導入的模塊就能夠在 h 函數中用這些模塊提供的 api 去創建虛擬DOM(Vnode)對象
; 在上文中就使用了樣式模塊
以及事件模塊
讓創建的這個虛擬 DOM 具備樣式屬性以及事件屬性, 最終通過patch函數
對比兩個虛擬dom
(會先把 app 轉換成虛擬 dom), 更新視圖;
我們再簡單看看 init 的源碼部分:
h 函數
些地方也會用createElement
來命名, 它們是一樣的東西, 都是創建虛擬DOM
的, 在上述文章中相信大夥已經對 h 函數有一個初步的瞭解並且已經聯想了使用場景, 就不作場景案例介紹了, 直接上源碼部分:
總結:h函數
先生成一個vnode
函數, 然後vnode
函數再生成一個Vnode
對象 (虛擬 DOM 對象)
補充:
在 h 函數源碼部分涉及一個函數重載
的概念, 簡單說明一下:
-
參數個數或參數類型不同的函數 ()
-
JavaScript 中沒有重載的概念
-
TypeScript 中有重載, 不過重載的實現還是通過代碼調整參數
重載這個概念個參數相關, 和返回值無關
- 實例 1(函數重載 - 參數個數)
- 實例 2(函數重載 - 參數類型)
patch 函數 (核心)
要是看完前面的鋪墊, 看到這裏你可能走神了,醒醒啊,這是核心啊,上高地了兄弟
;
-
pactch(oldVnode,newVnode)
-
把新節點中變化的內容渲染到真實 DOM, 最後返回新節點作爲下一次處理的舊節點 (核心)
-
對比新舊
VNode
是否相同節點 (節點的 key 和 sel 相同) -
如果不是相同節點, 刪除之前的內容, 重新渲染
-
如果是相同節點, 再判斷新的
VNode
是否有text
, 如果有並且和oldVnode
的text
不同直接更新文本內容(patchVnode)
-
如果新的 VNode 有 children, 判斷子節點是否有變化
(updateChildren,最麻煩,最難實現)
源碼:
補充 1: sameVnode 函數
patchVnode
-
第一階段觸發
prepatch
函數以及update
函數 (都會觸發 prepatch 函數, 兩者不完全相同纔會觸發 update 函數) -
第二階段, 真正對比新舊
vnode
差異的地方 -
第三階段, 觸發
postpatch
函數更新節點
源碼:
看得可能有點矇蔽, 下面再上一副思維導圖:
題外話: diff 算法簡介
傳統 diff 算法
-
虛擬 DOM 中的 Diff 算法
-
傳統算法
查找兩顆樹每一個節點的差異 -
會運行 n1(dom1 的節點數)*n2(dom2 的節點數) 次方去對比, 找到差異的部分再去更新
snabbdom 的 diff 算法優化
-
Snbbdom 根據 DOM 的特點對傳統的 diff 算法做了
優化
-
DOM 操作時候很少會跨級別操作節點
-
只比較
同級別
的節點
下面我們就會介紹updateChildren
函數怎麼去對比子節點的異同
, 也是Diff算法
裏面的一個核心以及難點;
updateChildren(核中核: 判斷子節點的差異)
- 這個函數我分爲三個部分,
部分1:聲明變量
,部分2:同級別節點比較
,部分3:循環結束的收尾工作
(見下圖);
同級別節點比較
的五種
情況:
-
oldStartVnode/newStartVnode
(舊開始節點 / 新開始節點) 相同 -
oldEndVnode/newEndVnode
(舊結束節點 / 新結束節點) 相同 -
oldStartVnode/newEndVnode
(舊開始節點 / 新結束節點) 相同 -
oldEndVnode/newStartVnode
(舊結束節點 / 新開始節點) 相同 -
特殊情況當1,2,3,4的情況都不符合
的時候就會執行, 在oldVnodes
裏面尋找跟newStartVnode
一樣的節點然後位移到oldStartVnode
, 若沒有找到在就oldStartVnode
創建一個
-
執行過程是一個循環, 在每次循環裏, 只要執行了上述的情況的五種之一就會結束一次循環
-
循環結束的收尾工作
: 直到 oldStartIdx>oldEndIdx || newStartIdx>newEndIdx(代表舊節點或者新節點已經遍歷完)
爲了更加直觀的瞭解, 我們再來看看同級別節點比較
的五種
情況的實現細節:
新開始節點和舊開始節點 (情況 1)
-
若
情況1符合:(從新舊節點的開始節點開始對比
,oldCh[oldStartIdx]和newCh[newStartIdx]
進行sameVnode(key和sel相同)
判斷是否相同節點) -
則執行
patchVnode
找出兩者之間的差異, 更新圖; 如沒有差異則什麼都不操作, 結束一次循環 -
oldStartIdx++/newStartIdx++
新結束節點和舊結束節點 (情況 2)
-
若
情況1不符合
就判斷情況2
, 若符合:(從新舊節點的結束節點開始對比,oldCh[oldEndIdx]和newCh[newEndIdx]
對比, 執行sameVnode(key和sel相同)
判斷是否相同節點) -
執行
patchVnode
找出兩者之間的差異, 更新視圖,; 如沒有差異則什麼都不操作, 結束一次循環 -
oldEndIdx--/newEndIdx--
舊開始節點 / 新結束節點 (情況 3)
-
若
情況1,2
都不符合, 就會嘗試情況 3:(舊節點的開始節點與新節點的結束節點開始對比,oldCh[oldStartIdx]和newCh[newEndIdx]
對比, 執行sameVnode(key和sel相同)
判斷是否相同節點) -
執行
patchVnode
找出兩者之間的差異, 更新視圖, 如沒有差異則什麼都不操作, 結束一次循環 -
oldCh[oldStartIdx]對應的真實dom
位移到oldCh[oldEndIdx]對應的真實dom
後 -
oldStartIdx++/newEndIdx--
;
舊結束節點 / 新開始節點 (情況 4)
-
若
情況1,2,3
都不符合, 就會嘗試情況 4:(舊節點的結束節點與新節點的開始節點開始對比,oldCh[oldEndIdx]和newCh[newStartIdx]
對比, 執行sameVnode(key和sel相同)
判斷是否相同節點) -
執行
patchVnode
找出兩者之間的差異, 更新視圖, 如沒有差異則什麼都不操作, 結束一次循環 -
oldCh[oldEndIdx]對應的真實dom
位移到oldCh[oldStartIdx]對應的真實dom
前 -
oldEndIdx--/newStartIdx++
;
新開始節點 / 舊節點數組中尋找節點 (情況 5)
-
從舊節點裏面尋找, 若尋找到與
newCh[newStartIdx]
相同的節點 (且叫對應節點[1]
), 執行patchVnode
找出兩者之間的差異, 更新視圖, 如沒有差異則什麼都不操作, 結束一次循環 -
對應節點[1]對應的真實dom
位移到oldCh[oldStartIdx]對應的真實dom
前
-
若沒有尋找到相同的節點
, 則創建一個與newCh[newStartIdx]
節點對應的真實dom
插入到oldCh[oldStartIdx]對應的真實dom
前 -
newStartIdx++
下面我們再介紹一下結束循環
的收尾工作(oldStartIdx>oldEndIdx || newStartIdx>newEndIdx)
:
-
新節點的所有子節點
先遍歷完 (newStartIdx>newEndIdx
), 循環結束 -
新節點的所有子節點
遍歷結束就是把沒有對應相同節點的子節點
刪除
-
舊節點的所有子節點
先遍歷完 (oldStartIdx>oldEndIdx
), 循環結束 -
舊節點的所有子節點
遍歷結束就是在多出來的子節點
插入到舊節點結束節點
前;(源碼:newCh[newEndIdx + 1].elm)
, 就是對應的舊結束節點的真實dom
,newEndIdx+1 是因爲在匹配到相同的節點需要 - 1, 所以需要加回來就是結束節點
最後附上源碼:
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) { let oldStartIdx = 0; // 舊節點開始節點索引
let newStartIdx = 0; // 新節點開始節點索引
let oldEndIdx = oldCh.length - 1; // 舊節點結束節點索引
let oldStartVnode = oldCh[0]; // 舊節點開始節點
let oldEndVnode = oldCh[oldEndIdx]; // 舊節點結束節點
let newEndIdx = newCh.length - 1; // 新節點結束節點索引
let newStartVnode = newCh[0]; // 新節點開始節點
let newEndVnode = newCh[newEndIdx]; // 新節點結束節點
let oldKeyToIdx; // 節點移動相關
let idxInOld; // 節點移動相關
let elmToMove; // 節點移動相關
let before;
// 同級別節點比較
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVnode == null) {
oldStartVnode = oldCh[++oldStartIdx];
// Vnode might have been moved left
}
else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx];
}
else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx];
}
else if (newEndVnode == null) {
newEndVnode = newCh[--newEndIdx];
}
else if (sameVnode(oldStartVnode, newStartVnode))
{ // 判斷情況1
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
}
else if (sameVnode(oldEndVnode, newEndVnode))
{ // 情況2
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
}
else if (sameVnode(oldStartVnode, newEndVnode))
{ // Vnode moved right情況3
patchVnode(oldStartVnode, newEndVnode,
insertedVnodeQueue);
api.insertBefore(parentElm, oldStartVnode.elm, api.
nextSibling(oldEndVnode.elm));
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
}
else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left情況4
patchVnode(oldEndVnode, newStartVnode,
insertedVnodeQueue);
api.insertBefore(parentElm, oldEndVnode.elm,
oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
}
else { // 情況5
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx,
oldEndIdx);
}
idxInOld = oldKeyToIdx[newStartVnode.key];
if (isUndef(idxInOld))
{ // New element // 創建新的節點在舊節點的新節點前
api.insertBefore(parentElm, createElm
(newStartVnode,
insertedVnodeQueue), oldStartVnode.elm);
}
else {
elmToMove = oldCh[idxInOld];
if (elmToMove.sel !== newStartVnode.sel)
{ // 創建新的節點在舊節點的新節點前
api.insertBefore(parentElm, createElm
(newStartVnode, insertedVnodeQueue),
oldStartVnode.elm);
}
else
{// 在舊節點數組中找到相同的節點就對比差異更新視圖,然後移動位置
patchVnode(elmToMove, newStartVnode,
insertedVnodeQueue);
oldCh[idxInOld] = undefined;
api.insertBefore(parentElm, elmToMove.elm,
oldStartVnode.elm);
}
}
newStartVnode = newCh[++newStartIdx];
}
}
// 循環結束的收尾工作
if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
if (oldStartIdx > oldEndIdx) {
// newCh[newEndIdx + 1].elm就是舊節點數組中的結束節點對應的dom元素
// newEndIdx+1是因爲在之前成功匹配了newEndIdx需要-1
// newCh[newEndIdx + 1].elm,因爲已經匹配過有相同的節點了,
它就是等於舊節點數組中的結束節點對應的dom元素(oldCh[oldEndIdx + 1]
.elm)
before = newCh[newEndIdx + 1] == null ?
null : newCh[newEndIdx + 1].
elm;
// 把新節點數組中多出來的節點插入到before前
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx,
insertedVnodeQueue);
}
else {
// 這裏就是把沒有匹配到相同節點的節點刪除掉
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
}
key 的作用
-
Diff 操作可以
更加快速
; -
Diff 操作可以更加準確;
(避免渲染錯誤)
-
不推薦使用索引
作爲 key
以下我們看看這些作用的實例:
Diff 操作可以更加準確;****(避免渲染錯誤)
:
實例: a,b,c 三個 dom 元素中的 b,c 間插入一個 z 元素
沒有設置 key
Diff 操作可以更加準確;(避免渲染錯誤)
實例: a,b,c 三個 dom 元素, 修改了 a 元素的某個屬性再去在 a 元素前新增一個 z 元素
沒有設置 key:
因爲沒有設置 key, 默認都是 undefined, 所以節點都是相同的, 更新了 text 的內容但還是沿用了之前的 dom, 所以實際上a->z(a原本打勾的狀態保留了,只改變了text),b->a,c->b,d->c
, 遍歷完畢發現還要增加一個 dom, 在最後新增一個 text 爲 d 的 dom 元素
設置了 key:
當設置了 key,a,b,c,d 都有對應的 key,a->a,b->b,c->c,d->d
, 內容相同無需更新, 遍歷結束, 新增一個 text 爲 z 的 dom 元素
不推薦使用索引
作爲 key:
設置索引爲 key:
這明顯效率不高, 我們只希望找出不同的節點更新, 而使用索引作爲 key 會增加運算時間, 我們可以把 key 設置爲與節點 text 爲一致就可以解決這個問題:
來源:
https://juejin.cn/post/7000266544181674014
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/hh6VCDWiqt3BaJuD92Xl6Q