本文首發於我的 Blog
當你看到這個標題的時候，一定很好奇，React 不是很快麼？為啥會變慢呢？在寫這篇文章之前，我也是這麼認為的，但是當我去看了一下 React 有關 Array 的 Diff 之後，我才認識到其實 React 如果你用的不正確，那麼是會變慢的。
React Diff 算法
React Diff 算法相信大家不是很陌生吧，這裡就不具體展開講了。不過有一點要補充下，Diff 算法針對的是整個 React 組件樹，而不僅僅是 DOM 樹，雖然這樣性能會比較低一些，但是實現起來卻很方便。
而在 Diff 算法中，針對數組的 diff 其實是比較有意思的一個地方。在開始講解方面，我希望你能對 React 有一定的瞭解和使用。
試一試有什麼區別？
首先我們創建 3 個組件，分別渲染 10000 個 DOM 元素，從 [1...10000] ，渲染成如下。
const e10000 = new Array(10000).fill(0).map((_, i) => i + 1)
element10000.map(i => <div key={`${i}`}>{i}</div>)
每個組件有兩個狀態，會切換數據的順序
- 組件 A 在
[1...10000]和[2,1,3...10000]之間切換。 - 組件 B 在
[1...10000]和[10000,1...9999]之間切換 - 組件 C 在
[1...10000]和[10000...1]之間切換，也就是正序和倒序之間切換。
我們簡單命名下，默認的初始狀態為 S1 而切換之後的狀態為 S2 。大家可以思考一下，同一個組件狀態切換的時候，所耗費的時間是不是都是一樣的？可以直接使用這個 DEMO。
可以直接點擊上方的 toggle 來切換兩者之間的狀態，並在控制檯中查看渲染的時間。因為每次時間都不是絕對準確的，所以取了多次平均值，直接揭曉答案：
| 組件 | S2 => S1 | S1 => S2 |
|---|---|---|
| A | 102ms | 103ms |
| B | 129ms | 546ms |
| C | 556ms | 585ms |
有麼有覺得很奇怪，為什麼同樣是 S1 ⇒ S2 ，同樣是只改變了一個元素的位置，為什麼 A 和 B 的時間差距有這麼多的差距。這個具體原理就要從 Diff 算法開始講起了。
Array Diff 的原理
在講 React 的實現之前，我們先來拋開 React 的實現獨立思考一下。但是如果直接從 React 的組件角度下手會比較麻煩，首先簡化一下問題。
存在兩個數組 A 和 B，數組中每一個值必須要保證在對應數組內是唯一的，類型可以是字符串或者數字。那麼這個問題就轉變成了如何從數組 A 通過最少的變換步驟到數組 B。
其實每個元素的值對應的就是 React 當中的 key。如果一個元素沒有 key 的話，index 就是那個元素默認的 key。為什麼要強調最少？因為我們希望的是能夠用最少的步數完成，但是實際上這會造成計算量的加大，而 React 的實現並沒有計算出最優解，而是一個較快解。
順便定義一下操作的類型有：刪除元素，插入元素，移動元素。
這裡又要引申一個特殊點，React 充分利用了 DOM 的特性，在 DOM 操作中，你是可以不使用 index 來索引數據的。簡單來講，如果用數組表示，刪除需要指定刪除元素的索引，插入需要指定插入的位置，而移動元素需要指定從哪個索引移動到另一個索引。而利用 DOM，我們就可以簡化這些操作，可以直接刪除某個元素的實例，在某個元素前插入或者移動到這裡（利用 insertBefore API，如果是要在添加或者移動到最後，可以利用 append ）。這樣最大的好處是我們不需要記錄下移動到的位置，只需要記錄下那些元素移動了即可，而且這部分操作正好可以由 Fiber 來承擔。
舉個例子說，從 A=[1,2,3] 變化到 B=[2,3,4,1]，那麼只需要記錄如下操作即可：
有人好奇，不需要記錄移動插入到那個元素前面麼？其實不需要的，這是因為你有了操作列表和 B 數組之後，就可以知道目標元素在哪裡了。而且採用這種方式就根本不需要關心每次操作之後索引的變化。
回到上面的簡化後的問題，首先通過對比 A、B 數組，可以得到哪些元素是刪除的，哪些元素是添加的，而不管採用什麼樣子的策略，添加刪除元素的操作次數是無法減少的。因為你不能憑空產生或者消失一個元素。那麼我們問題就可以再簡化一下，把所有的添加刪除的元素剔除後分別得到數組 A’ 和 B’，也就是 A’ 中不包含被刪除的元素，B’ 中不包含被添加的元素，此時 A’ 和 B’ 的長度一定是一樣長的。也就是求解出最少移動次數使得數組 A’ 能夠轉化成數組 B’。
如果只是簡單的求解一下最少移動步數的話，答案很簡單，就是最長上升子序列（LIS，Longest Increasing Subsequence）。關於如何證明為什麼是最長不下降子序列這個算法，可以通過簡單的反證法得到。關於這個算法的內容我就不具體講解了，有興趣的可以自行 Google。在這裡我們只需要知道這個算法的時間複雜度是 O(n^2) 。
但是現在我們還無法直接應用這個算法，因為每個元素的類型可能是字符串或者數字，無法比較大小。定義數組 T 為 B’ 內元素在 A’ 的位置。舉個例子，如果 A' = ['a', 'b', 'c'] B' = ['b', 'c', 'a']，那麼 T = [2, 3, 1]。本文約定位置是從 1 開始，索引從 0 開始。
此時便可以對 T 求解 LIS，可以得到 [2, 3]，我們將剩下不在 LIS 中的元素標記為移動元素，在這裡就是 1，最後補上被剔除的刪除和插入的元素的操作動作。這樣 Diff 算法就可以結束了。
上面講解的是一個個人認為完整的 Array Diff 算法，但是還是可以在保證正確性上繼續優化。但是不管優化，這個複雜度對於 React 來講還是偏高的，而如何平衡效率和最優解成為了最頭疼的問題，好在 React 採用了一個混合算法，在犧牲掉一定正確性的前提下，將複雜度降低為 O(n)。下面我們來講解下。
React 簡化之後的 Array Diff
大家有過 React 開發經驗的人很清楚，大部分情況下，我們通常是這樣使用的：
情形1：一個標籤的的直接子子標籤數量類型順序不變，通常用於靜態內容或者對子組件的更新
// 比如每次渲染都是這樣的，裡面的直接子元素的類型和數量是不變的，在這種情況下，其實是可以省略 key <div> <div key="header">header</div> <div key="content">content</div> <div key="footer">footer</div> <SubCmp time={Date.now()}/> </div>情形2：一個標籤有多個子標籤，但是一般只改變其中的少數幾個子標籤。最常見的場景就是規則編輯器，每次只在最後添加新規則，或者刪除其中某個規則。當然了，滾動加載也算是這種。
情形3：交換某幾個子標籤之間的順序
情形4：翻頁操作，幾乎重置了整個子元素
上面只是簡單舉了幾個常見的例子，大家可以發現，大部分情況下子標籤變動的其實並不多，React 利用了這個，所以將 LIS 簡化成以第一個元素開始，找到最近上升子序列。簡單來來講就是從頭開始遍歷，只要這個元素不小於前的元素，那麼就加入隊列。
Q = [4, 1, 5, 2, 3]
// 標準算法
LIS = [1, 2, 3]
// 簡化後的算法，從第一個開始，找到最近的不下降子序列即可。
LIS_React = [4, 5]
我們乍一看，這個算法不對呀，隨便就能舉出一個例子讓這個算法錯成狗，但是我們要結合實際情況來看。如果我們套回前面說的幾種情況，可以看到對於情況 1,2,3 來講，幾乎和簡化前效果是一樣。而這樣做之後，時間複雜度降低為 O(n) ，空間複雜度降低為 O(1)。我們給簡化後的算法叫做 LIS' 方便後面區分。
我們將 LIS 算法簡化後，配合上之前一樣的流程就可以得出 React 的 Array Diff 算法的核心流程了。（為什麼叫核心流程，因為還有很多優化的地方沒有講）
變慢的原因？
當我們在瞭解了 React 的實現之後，我們再回過來頭來看看前面給出的三個例子為啥會有這麼大的時間差距？
- 組件 A 從
[1...10000]變化到[2,1,3...10000]。此時我們先求解一下LIS'可以得到[2,3,4...10000]，那麼我們只需要移動1這個元素就可以了，將移動到元素3前面。同理反過來也是如此，也就是說 S1 ⇒ S2 和 S2 ⇒ S1 的所需要移動的次數是一致的，理論上時間上也就是相同的。 - 組件 B 從
[1...10000]變化到[10000,1,2...9999]。同理，先計算LIS'可以得到[10000]，沒錯，你沒看錯，就是隻有一次元素，那麼我需要將剩下的所有元素全都移動到10000的後面去，換句話要進行 9999 次移動。這也就是為啥S1 => S2的時間會這麼慢。但是反過來卻不需要這個樣子，將狀態反過來，並重新計算索引，那麼也就是從[1...10000]到[2,3....10000,1]，在計算一次LIS'得到[2,3...10000]，此時只需要移動一次即可，S2 ⇒ S1的時間也就自然恢復的和組件 A 一致。 - 組件 C 是完全倒序操作，所以只分析其中一個過程即可。首先計算
LIS'可以得到，[10000]，也就是說要移動 9999 次，反過來也是要 9999 次，所以時間狀態是一致的。
經過這樣的分析大家是不是就明白為啥會變慢了吧？
優化細節
降低 Map 的生成操作次數
上面有一點沒有講到，不知道大家有沒有思考到，我怎麼知道某個元素是該添加函數刪除呢？大家第一反應就是構建一個 Set，將數組元素全放進去，然後進行判斷就可以了。但是在 React 中，其實用的是 Map，因為要存儲對應的 Fiber，具體細節大家可以不用關注，只需要知道這裡用 Map 實現了這個功能。
不管怎麼樣，根據算法，一開始肯定要構建一遍 Map，但是我們來看下上面的 情形1。發現內容是根本不會發生變化的，而且對於 情形2 來講，有很大的概率前面的大部分是相同的。
於是 React 一開始不構建 Map，而是假設前面的內容都是一致的，對這些元素直接執行普通的更新 Fiber 操作，直到碰到第一個 key 不相同的元素才開始構建 Map 走正常的 Diff 流程。按照這個方式，情形1根本不會創建 Map，而且對於情形2、3來講也會減少很多 Map 元素的操作（set、get、has）。
降低循環次數
按照上面的算法，我們需要至少 3 遍循環：第一遍構建 Map，第二遍剔除添加刪除的元素生成 A’ 和 B’，第三遍計算 LIS 並得到哪些元素需要移動或者刪除。而我們發現第二遍和第三遍是可以合併在一起的。也即是說我們在有了 Map 的情況下，不需要剔除元素，當遍歷發現這個元素是新增的時候，直接記錄下來。
總結
關於 Diff 算法其實還有很多的細節，我這邊沒有過多講解，因為比較簡單，比較符合直覺。大家有興趣的可以自己去看下。另外有人應該會注意到，上面的例子中，為什麼切換同樣的次數，有的時間長，有的時間短了。日後有時間再分析下補充了。