Vue3 diff

最長遞增子序列+雙端diff

理念

1. 相同的前置和后置元素的預處理，考慮邊界情況，減少移動；
2. 最長遞增子序列（動態規劃、二分法），判斷是否需要移動

操作

1. 前置與后置預處理
2. 判斷是否需要移動
   遞增法：根據新列表剩余的節點數，創建一個source數組，填入-1，存儲新節點在舊節點的位置，再算出source中最長遞增子序列，用于移動DOM，如舊節點在新列表中沒有，則直接刪除
3. 移動DOM：根據source對新列表進行重新編號，找到source的最長遞增子序列在原本數組中的索引，創建一個數組保存每個值的最長子序列在數組中的index，然后從后向前遍歷source
   • 當前index=-1，則創建DOM節點插入隊尾
   • 當前index為最長遞增子序列中的值，則不需要移動，判斷是否有全新的節點添加
   • 當前index不在最長遞增子序列中，則移動，將DOM節點插入隊尾

細節

1. 同層級比較
2. 節點類型判斷：不同類型直接替換
3. key值比較：相同key可復用
4. 屬性比較：只更新變化的屬性

Vue2 diff

雙端比較
缺乏事件切片能力，除了高幀率動畫，其他場景都可以使用防抖和節流提高響應性能

理念

新列表和舊列表兩個列表的頭和尾互相對比，在對比的過程中指針會逐漸向內靠攏，直到某一個列表的節點全部遍歷過，對比停止

過程

1. vue的diff算法是平級比較，不考慮跨級比較的情況，即只有在新舊children都為多個子節點時才需要使用diff算法進行同層級比較
2. 內部采用深度遞歸的方式+雙指針的方式進行比較
   • 舊children和新children各有兩個頭尾的變量startIdx和EndIdx，頭頭、尾尾、頭尾、尾頭進行對比，一共四種比較方式
     • 使用舊列表的頭一個節點與新列表的頭一個節點對比
     • 使用舊列表的最后一個節點與新列表的最后一個節點對比
     • 使用舊列表的頭一個節點與新列表的最后一個節點對比
     • 使用舊列表的最后一個節點與新列表的頭一個節點對比去
       尋找key相同的可復用的節點，如果找到則停止后面的尋找；
   • 四種方式都沒匹配，如果設置了key，就用key進行比較，拿新列表中第一個節點去舊列表中找與其key相同的節點
     • 在舊列表中找到了：移動找到的節點，舊列表中的節點改為undefined，移動過的節點不需要再進行節點對比；
     • 在舊列表中沒找到：創建新節點放到最前面在比較中，變量會往中間靠，如果startIdx>EndIdx，表明舊children和新children至少有一個已經遍歷完成，結束比較
3. vue的diff算法稱為patching算法，diff執行時刻是組件內響應式數據變更觸發實例執行其更新函數，再次執行render函數得到最新的虛擬DOM，然后執行patch函數，并傳入新舊兩次的虛擬DOM，對比找到變化，將其轉化為對應的DOM操作
4. patch過程是遞歸過程，遵循深度優先，同層比較的策略

Vue3 diff和Vue2 diff比較

1. 最長遞增子序列算法
   減少不必要的DOM操作，提升性能
2. 靜態標記
   更新時跳過靜態節點
3. 緩存數組
   將新舊VNode數組緩存，只對數組中不同的VNode對比，減少比對次數，提升性能
4. 動態刪除數組
   異步隊列方式，將多個刪除操作合并