建站
咨詢
售后
建站咨詢
新聞中心
云計算 虛擬化 Vue的diff算法與動態(tài)規(guī)劃算法中的經(jīng)典案例“計算a到b的最小編輯距離”看上去有些相似，實際完全不同，Vue的diff相對來說輕量很多，感興趣的朋友可以查閱相關(guān)資料進行了解。
一、前言
Vue的核心是雙向綁定和虛擬DOM(下文我們簡稱為vdom)，關(guān)于雙向綁定可以參閱木琴的文章《剖析Vue原理&實現(xiàn)雙向綁定MVVM》，vdom是樹狀結(jié)構(gòu)，其節(jié)點為vnode，vnode和瀏覽器DOM中的Node一一對應，通過vnode的elm屬性可以訪問到對應的Node。
vdom因為是純粹的JS對象，所以操作它會很高效，但是vdom的變更最終會轉(zhuǎn)換成DOM操作，為了實現(xiàn)高效的DOM操作，一套高效的虛擬DOM diff算法顯得很有必要。
Vue的diff算法是基于snabbdom改造過來的，感興趣的朋友可以選擇查閱。
這是一張很經(jīng)典的圖，出自《React’s diff algorithm》，Vue的diff算法也同樣，即僅在同級的vnode間做diff，遞歸地進行同級vnode的diff，最終實現(xiàn)整個DOM樹的更新。那同級vnode diff的細節(jié)又是怎樣的呢?正是本文所要講的。
二、例子
我們在下文中將使用這個簡化的例子來講述diff的過程
如上圖的例子，更新前是1到10排列的Node列表，更新后是亂序排列的Node列表。羅列一下圖中有以下幾種類型的節(jié)點變化情況：
(1)、頭部相同、尾部相同的節(jié)點：如1、10
(2)、頭尾相同的節(jié)點：如2、9(處理完頭部相同、尾部相同節(jié)點之后)
(3)、新增的節(jié)點：11
(4)、刪除的節(jié)點：8
(5)、其他節(jié)點：3、4、5、6、7
三、簡單的diff
簡單的diff算法可以這樣設(shè)計：
逐個遍歷newVdom的節(jié)點，找到它在oldVdom中的位置，如果找到了就移動對應的DOM元素，如果沒找到說明是新增節(jié)點，則新建一個節(jié)點插入。遍歷完成之后如果oldVdom中還有沒處理過的節(jié)點，則說明這些節(jié)點在newVdom中被刪除了，刪除它們即可。
仔細思考一下，幾乎每一步都要做移動DOM的操作，這在DOM整體結(jié)構(gòu)變化不大時的開銷是很大的，實際上DOM變化不大的情況現(xiàn)實中經(jīng)常發(fā)生，很多時候我們只需要變更某個節(jié)點的文本而已。
接下來我們看一下Vue的diff實現(xiàn)
四、Vue的diff實現(xiàn)
上圖例子中我畫上了oldStart+oldEnd，newStart+newEnd這樣2對指針，分別對應oldVdom和newVdom的起點和終點。起止點之前的節(jié)點是待處理的節(jié)點，Vue不斷對vnode進行處理同時移動指針直到其中任意一對起點和終點相遇。處理過的節(jié)點Vue會在oldVdom和newVdom中同時將它標記為已處理(標記方法后文中有介紹)。Vue通過以下措施來提升diff的性能。
(一)、優(yōu)先處理特殊場景
(1)、頭部的同類型節(jié)點、尾部的同類型節(jié)點
這類節(jié)點更新前后位置沒有發(fā)生變化，所以不用移動它們對應的DOM
(2)、頭尾/尾頭的同類型節(jié)點
這類節(jié)點位置很明確，不需要再花心思查找，直接移動DOM就好
處理了這些場景之后，一方面一些不需要做移動的DOM得到快速處理，另一方面待處理節(jié)點變少，縮小了后續(xù)操作的處理范圍，性能也得到提升。
(二)、“原地復用”
“原地復用”是指Vue會盡可能復用DOM，盡可能不發(fā)生DOM的移動。Vue在判斷更新前后指針是否指向同一個節(jié)點，其實不要求它們真實引用同一個DOM節(jié)點，實際上它僅判斷指向的是否是同類節(jié)點(比如2個不同的div，在DOM上它們是不一樣的，但是它們屬于同類節(jié)點)，如果是同類節(jié)點，那么Vue會直接復用DOM，這樣的好處是不需要移動DOM。再看上面的實例，假如10個節(jié)點都是div，那么整個diff過程中就沒有移動DOM的操作了。
“原地復用”在Vue的官方文檔中有提到，雖然帶來了好處，但是也會產(chǎn)生一些問題，朋友們可以復習一下
https://cn.vuejs.org/v2/guide/list.html#key
https://cn.vuejs.org/v2/guide/conditional.html#用-key-管理可復用的元素
五、按步解剖實例
(一)、整體視圖
先看一張整體視圖，整個diff分兩部分：
(1)、***部分是一個循環(huán)，循環(huán)內(nèi)部是一個分支邏輯，每次循環(huán)只會進入其中的一個分支，每次循環(huán)會處理一個節(jié)點，處理之后將節(jié)點標記為已處理(oldVdom和newVdom都要進行標記，如果節(jié)點只出現(xiàn)在其中某一個vdom中，則另一個vdom中不需要進行標記)，標記的方法有2種，當節(jié)點正好在vdom的指針處，移動指針將它排除到未處理列表之外即可，否則就要采用其他方法，Vue的做法是將節(jié)點設(shè)置為undefined。
(2)、循環(huán)結(jié)束之后，可能newVdom或者oldVdom中還有未處理的節(jié)點，如果是newVdom中有未處理節(jié)點，則這些節(jié)點是新增節(jié)點，做新增處理。如果是oldVdom中有這類節(jié)點，則這些是需要刪除的節(jié)點，相應在DOM樹中刪除之
整個過程是逐步找到更新前后vdom的差異，然后將差異反應到DOM樹上(也就是patch)，特別要提一下Vue的patch是即時的，并不是打包所有修改***一起操作DOM(React則是將更新放入隊列后集中處理)，朋友們會問這樣做性能很差吧?實際上現(xiàn)代瀏覽器對這樣的DOM操作做了優(yōu)化，并無差別。
(二)、逐步解析
(1)、處理頭部的同類型節(jié)點，即oldStart和newStart指向同類節(jié)點的情況，如下圖中的節(jié)點1
這種情況下，將節(jié)點1的變更更新到DOM，然后對其進行標記，標記方法是oldStart和newStart后移1位即可，過程中不需要移動DOM(更新DOM或許是要的，比如屬性變更了，文本內(nèi)容變更了等等)
(2)、處理尾部的同類型節(jié)點，即oldEnd和newEnd指向同類節(jié)點的情況，如下圖中的節(jié)點10
與情況(1)類似，這種情況下，將節(jié)點10的變更更新到DOM，然后oldEnd和newEnd前移1位進行標記，同樣也不需要移動DOM
(3)、處理頭尾/尾頭的同類型節(jié)點，即oldStart和newEnd，以及oldEnd和newStart指向同類節(jié)點的情況，如下圖中的節(jié)點2和節(jié)點9
先看節(jié)點2，其實是往后移了，移到哪里?移到oldEnd指向的節(jié)點(即節(jié)點9)后面，移動之后標記該節(jié)點，將oldStart后移1位，newEnd前移一位
操作結(jié)束之后情況如下圖
同樣地，節(jié)點9也是類似的處理，處理完之后成了下面這樣
(4)、處理新增的節(jié)點
newStart來到了節(jié)點11的位置，在oldVdom中找不到節(jié)點11，說明它是新增的
那么就創(chuàng)建一個新的節(jié)點，插入DOM樹，插到什么位置?插到oldStart指向的節(jié)點(即節(jié)點3)前面，然后將newStart后移1位標記為已處理(注意oldVdom中沒有節(jié)點11，所以標記過程中它的指針不需要移動)，處理之后如下圖
(5)、處理更新的節(jié)點
經(jīng)過第(4)步之后，newStart來到了節(jié)點7的位置，在oldVdom中能找到它而且不在指針位置(查找oldVdom中oldStart到oldEnd區(qū)間內(nèi)的節(jié)點)，說明它的位置移動了
那么需要在DOM樹中移動它，移到哪里?移到oldStart指向的節(jié)點(即節(jié)點3)前面，與此同時將節(jié)點標記為已處理，跟前面幾種情況有點不同，newVdom中該節(jié)點在指針下，可以移動newStart進行標記，而在oldVdom中該節(jié)點不在指針處，所以采用設(shè)置為undefined的方式來標記(一定要標記嗎?后面會提到)
處理之后就成了下面這樣
(6)、處理3、4、5、6節(jié)點
經(jīng)過第(5)步處理之后，我們看到了令人欣慰的一幕，newStart和oldStart又指向了同一個節(jié)點(即都指向節(jié)點3)，很簡單，按照(1)中的做法只需移動指針即可，非常高效，3、4、5、6都如此處理，處理完之后如下圖
(7)、處理需刪除的節(jié)點
經(jīng)過前6步處理之后(實際上前6步是循環(huán)進行的)，朋友們看newStart跨過了newEnd，它們相遇啦!而這個時候，oldStart和oldEnd還沒有相遇，說明這2個指針之間的節(jié)點(包括它們指向的節(jié)點，即上圖中的節(jié)點7、節(jié)點8)是此次更新中被刪掉的節(jié)點。
OK，那我們在DOM樹中將它們刪除，再回到前面我們對節(jié)點7做了標記，為什么標記是必需的?標記的目的是告訴Vue它已經(jīng)處理過了，是需要出現(xiàn)在新DOM中的節(jié)點，不要刪除它，所以在這里只需刪除節(jié)點8。
在應用中也可能會遇到oldVdom的起止點相遇了，但是newVdom的起止點沒有相遇的情況，這個時候需要對newVdom中的未處理節(jié)點進行處理，這類節(jié)點屬于更新中被加入的節(jié)點，需要將他們插入到DOM樹中。
至此，整個diff過程結(jié)束了
Vue的diff算法與動態(tài)規(guī)劃算法中的經(jīng)典案例“計算a到b的最小編輯距離”看上去有些相似，實際完全不同，Vue的diff相對來說輕量很多，感興趣的朋友可以查閱相關(guān)資料進行了解。
原文鏈接：https://www.qcloud.com/community/article/648055
作者：汪玉林
【本文是51CTO專欄作者“騰訊云技術(shù)社區(qū)”的原創(chuàng)稿件，轉(zhuǎn)載請通過51CTO聯(lián)系原作者獲取授權(quán)】
名稱欄目：深入Vue2.x的虛擬DOMdiff原理
分享路徑：http://www.5511xx.com/article/cocijse.html
