深入理解 React diff 算法

傳統 diff 算法

傳統 diff 算法通過循環遞歸對所有節點兩兩對比,時間複雜度是 O(n^2),再對樹的編輯(插入,替換,刪除)進行一次遍歷,因此時間複雜度是 O(n^3),其中 n 是節點總數,假設我們要展示 1000 個節點,那麼我們就要依次執行上十億次的比較,效率十分低效。在前端渲染場景來說成本過高

React diff 算法

在 React 中通過三個策略,將 O(n^3)複雜度的問題轉換成 O(n)複雜度的問題

  • 策略一:WebUI 中 DOM 節點跨層級的移動特別少,可以忽略不急
  • 策略二:擁有相同類的兩個組件將會生成相似的樹形結構,擁有不同類的兩個組件將會生成不同的樹形結構
  • 策略三:對於同一層級的一組子節點,它們可以通過唯一 id 進行區分。

基於以上策略,React 分別對 tree diff,component diff 以及 element diff 進行算法優化。

tree diff

React 通過 updateDepth 對 Virtual dom 樹進行層級控制,只會對相同層級的 DOM 節點進行比較,即同一個父節點下的所有子節點。當發現節點已經不存在時,則該節點及其子節點會被完全刪除掉,不會用於進一步的比較。這樣只需要對樹進行一次遍歷,便能完成整個 DOM 樹的比較。

深入理解 React diff 算法

<code>updateChildren: function(nextNestedChildrenElements, transaction, context) {
updateDepth++;
var errorThrown = true;
try {
this._updateChildren(nextNestedChildrenElements, transaction, context);
errorThrown = false;
} finally {
updateDepth--;
if (!updateDepth) {
if (errorThrown) {
clearQueue();
} else {
processQueue();
}
}
}
}/<code>

出現了 DOM 跨層級的移動操作,如下圖。A 節點整個被移動到了 D 節點下,React 只會考慮同層級節點的位置變換,而對於不同層級的節點,只有創建和刪除操作。當根節點發現子節中 A 消失了,就會直接銷燬 A;當 D 發現多了一個子節點 A,則會創建新的 A(包括子節點)作為子節點。此時,diff 的執行情況:

delete A -> create A -> create B -> create C

深入理解 React diff 算法

component diff

  • 如果是同一個類型的組件,則按照原策略進行 Virtual DOM 比較。
  • 如果不是同一類型的組件,則將其判斷為 dirty component,從而替換整個組價下的所有子節點。
  • 如果是同一個類型的組件,有可能經過一輪 Virtual DOM 比較下來,並沒有發生變化。如果我們能夠提前確切知道這一點,那麼就可以省下大量的 diff 運算時間。因此,React 允許用戶通過 shouldComponentUpdate()來判斷該組件是否需要進行 diff 算法分析。

如下圖所示,當組件 D 變為組件 G 時,即使這兩個組件結構相似,一旦 React 判斷 D 和 G 是不用類型的組件,就不會比較兩者的結構,而是直接刪除組件 D,重新創建組件 G 及其子節點。雖然當兩個組件是不同類型但結構相似時,進行 diff 算法分析會影響性能,但是畢竟不同類型的組件存在相似 DOM 樹的情況在實際開發過程中很少出現,因此這種極端因素很難在實際開發過程中造成重大影響。

深入理解 React diff 算法

element diff

當節點屬於同一層級時,diff 提供了 3 種節點操作,分別為 INSERT_MARKUP(插入),MOVE_EXISTING(移動),REMOVE_NODE(刪除)。

  • INSERT_MARKUP:新的組件類型不在舊集合中,即全新的節點,需要對新節點進行插入操作。
  • MOVE_EXISTING:舊集合中有新組件類型,且 element 是可更新的類型,這時候就需要做移動操作,可以複用以前的 DOM 節點。
  • REMOVE_NODE:舊組件類型,在新集合裡也有,但對應的 element 不同則不能直接複用和更新,需要執行刪除操作,或者舊組件不在新集合裡的,也需要執行刪除操作。
<code>// 新節點插入操作
function makeInsertMarkup(markup, afterNode, toIndex) {
return {
type: ReactMultichildUpdateTypes.INSERT_MARKUP,
content: markup,
fromIndex: null,
fromNode: nuLL,
toIndex: toIndex, // 插入位置
afterNode: afterNode // 記錄下一個節點
};
}

function makeMove(child, afterNode, toIndex) {
return {
type: ReactMultichildUpdateTypes.MOVE_EXISTING,
content: null,
fromIndex: child._mountIndex, // 移動起始位置

fromNode: ReactReconciler.getNativeNode(child), // 記錄移動的節點
toIndex: toIndex, // 移動結束位置
afterNode: afterNode // 記錄下一個節點
};
}

function makeRemove(child, node) {
return {
type: ReactMultichildUpdateTypes.REMOVE_NODE,
content: null,
fromIndex: child._mountIndex,
fromNode: node, // 記錄移動的節點
toIndex: null,
afterNode: null
};
}/<code>

舊集合中包含節點 A,B,C 和 D,更新後的新集合中包含節點 B,A,D 和 C,此時新舊集合進行 diff 差異化對比,發現 B!=A,則創建並插入 B 至新集合,刪除舊集合 A;以此類推,創建並插入 A,D 和 C,刪除 B,C 和 D。

深入理解 React diff 算法

React 發現這類操作煩瑣冗餘,因為這些都是相同的節點,但由於位置發生變化,導致需要進行繁雜低效的刪除,創建操作,其實只要對這些節點進行位置移動即可。React 提出了優化策略:允許開發者對同一層級的同組子節點,添加唯一 key 進行區分

現在 diff 的運作方式:

首先,對新集合中的節點進行循環遍歷 for( name in nextchildren),通過唯一的 key 判斷,新舊集合中是否存在相同的節點 if( prevChild === nextChild),如果存在相同節點,則進行移動操作,但在移動前需要將當前節點在舊集合中的位置與 lastIndex 進行比較 if( prevChild._mountIndex < lastIndex),否則不執行該操作。這是一種順序優化手段, lastIndex 一直在更新,表示訪問過的節點在舊集合中最右的位置(即最大的位置)如果新集合中當前訪問的節點比 lastIndex 大,說明當前訪問節點在舊集合中就比上一個節點位置靠後,則該節點不會影響其他節點的位置,因此不用添加到差異隊列中,即不執行移動操作。只有當訪問的節點比 lastIndex 小時,才需要進行移動操作。

如下圖:

深入理解 React diff 算法

  1. 從新集合中取得 B,因為舊集合中 B._mountIndex = 1 < lastIndex = 0,不滿足 prevChild._mountIndex < lastIndex,所以不對 B 進行操作,更新 lastInde x= prevChild._mountIndex,並且將 B 的位置更新為新集合中的位置,prevChild._mountIndex = nextIndex,nextIndex++,進入下一個節點判斷。
  2. 從新集合中取得 A,因為舊集合中 A._mountIndex = 0,滿足 prevChild._mountIndex lastIndex,所以對 A 進行移動操作 enqueueMove(this,child._mountIndex,toIndex),其中 toIndex 就是 nextIndex,表示 A 需要移動到的位置。並且將A的位置更新為新集合的中的位置 prevChild._mountIndex = nextIndex,nextIndex++,進入下一節點判斷。C,D用同樣的方式進行 diff


分享到:


相關文章: