由淺入深讀透vue原始碼:diff演算法
導語 | 開發者工作中,研究程式碼邏輯常需要思考這個問題:陣列變更後,具體變更了哪一些元素?變更的位置如何?本文作者陳碧鬆解析並覆寫了針對陣列變化的diff演算法邏輯。希望本文對你有幫助。
diff方法的執行規則和前提方法
為了瞭解diff方法的執行規則和前提方法,首先我們通過幾個圖快速區別虛擬node進行深度優先和同級對比。
深度優先:
同級對比:
如上面圖所示,每次vnode都是執行同級對比。(對應dom同一個父元素)
程式碼邏輯如下圖:
第二,簡單判斷:sameVnode
函式用來進行判斷是否是同一個vnode元素。原始碼如下:
如圖所示:
這裡有兩個重要元素:key
: 開發者定義的“:key”;sel
: 元素tagName+元素id+元素class。
sel的定義原始碼如下:
vNode構建函式:
第三是構建索引。
邏輯如圖:
如何處理元素
儘量不新增/刪除dom。如圖下所示:
如果是相同vnode,原始碼如下:
開始比較
首先會進行時間複雜度O(n)的while迴圈,迴圈條件為“遍歷舊節點陣列&&遍歷新節點陣列,誰先遍歷完迴圈就結束”。原始碼如下圖:
在每次的迴圈過程中,會有兩大類判斷方法:
1)首尾比較&首尾序號
邏輯:如圖上所示。首先在迴圈遍歷前標記好新,舊節點陣列的開始位置和結束位置的序號:oldStartIdx、oldEndIdx、newStartIdx、newEndIdx;其次在迴圈遍歷的過程中採用“首首比較,尾尾比較,首尾比較"。
原始碼如下:
如果資料為圖上所示,那麼根據首尾比較方法會有如下圖所示結果,最終全部執行了更新操作:
2)索引比較
最壞情況,這裡的時間複雜度也是O(n),即整個演算法複雜度O(n)+O(n)。每次遍歷的過程中可能存在"新陣列節點新增/舊陣列節點刪除",那麼前後對比就滿足不了條件。這裡邏輯會進入索引比較:比如這種情況:
那麼迴圈中會執行一遍,建立舊陣列的索引物件。從建立到比較的整個邏輯圖如下:
這裡的原始碼如下:
-
當舊節點不存在新增的節點時,進行當前oldStartIdx位置的新增
原始碼如下:
-
當舊陣列存在節點,那麼進行位置移動
原始碼:
3)當節點遍歷完之後
會存在兩種情況:新陣列已經遍歷完,但舊陣列沒有遍歷完成;舊陣列遍歷完成,但新陣列沒有遍歷完成。故原始碼的判斷如下:
- 舊陣列沒有迴圈完成
舊陣列沒有迴圈完成的效果如下圖所示:
這裡注意一個點,我們每次的節點更新會移動序號,即使被刪除的節點不在一塊最終也會被首尾比較演算法“摞在一塊”(oldStartIdx~oldEndIdx)。上圖所示更加明顯。原始碼在這裡就進行批量刪除:
- 新陣列沒有迴圈完成
效果如下圖所示:
整體來說,有幾個關鍵點:簡單對比;建立舊陣列的索引表;首位對比&首尾索引&vnode位置移動;索引新增/位移;剩餘部分批量處理新增/刪除。
經過前後對比&索引的過濾後,只會存在新.末尾節點!==舊節點及之前的連續的新節點(!==舊節點),所以這裡也被“摞在一塊”,即 (newStartIdx~newEndIdx)。原始碼如下。這樣,整個diff的對比演算法就已經走完了。核心就是:前後對比+索引。
vue3.0對於diff比較前的優化
vue3.0針對“無腦”patchVnode進行了過濾--靜態型別Vnode老版的原始碼:
這裡,我們再重複下vue2.x系列的對比更新邏輯:
新版的vue3.0增加了靜態型別Vnode。如果是靜態型別的vnode,直接跳過更新,修改新節點引用即可。
comment型別目前翻到它的原始碼也只是更改引用,原始碼作者加上了一行註釋。
補充一下,flagment碎片型別為新增的vnode型別,即:
vue3.0的過濾判斷原始碼如下:
陣列比較的應用
由於我們想監聽陣列的變化,參考了diff演算法覆寫類似的邏輯,用來在update,add,dels時,程式碼層面獲取操作的具體節點明細(新舊節點的位置,內容)。希望本文對你有幫助。
你可能感興趣的騰訊工程師作品
- 由淺入深讀透vue原始碼:diff演算法
- 打造更安全的視訊加密,雲點播版權保護實踐
- 《鋒巢直播平臺——基於騰訊雲音視訊小程式雲直播互動平臺》視訊課程上線“騰訊雲開發者社群”
- 從伺服器到雲託管,到底經歷了什麼?
- 解鎖tRPC高效能密碼:網路方案簡介!
- Web函式請求多併發上線,Web服務部署更快更省!
- 大勢所趨!生於雲,長於雲,開發者如何更好地吃透雲原生?
- 實現全鏈路重塑!從思維走向實踐,數字化轉型 IT 經營的成功路徑
- 深耕行業數十年,多元視角解讀!從思維轉變看數字化轉型 IT 經營
- 擁抱"後疫情時代",遠端辦公如何建設和管理團隊,邁向成功?
- 爭鋒相對,技術大咖辯論大PK!數字化轉型迎巨浪,技術管理者見真章
- 詳細解讀!推薦演算法架構——召回
- 搖滾開源人CC:熱愛足球音樂,亦是工業網際網路生態構建者!
- 七年激盪!Serverless 的下一站將去往何方?
- Go modules基礎精進,六大核心概念全解析
- 鏈路追蹤(Tracing)的前世今生(上)
- ClubHouse 上線支援Replay功能;WebOBS直播推流工具要流行起來了 |WebRTC風向標
- 日均請求量1.6萬億次背後,DNSPod的祕密-國密DoH篇
- 千萬併發連線下,如何保障網路效能
- 解放人與裝置距離,5G時代的遠端操控該如何完成