標籤：

Diff應用：從LCS到UICollectionView

05-25
Diff應用：從LCS到UICollectionView

1前文

什麼是Diff？

日常編程中有時候會遇到對比字元串，對比數組的情況，找出前後新舊數據的不同，可以稱之為Diff。

什麼是LCS？

Longest Common Subsequence的簡稱，最長公共子序列。

LCS有哪些應用？

1.Git等版本控制，常用的git diff命令

2.一些對比軟體，如Kaleidoscope，能進行圖片、文件、文本的對比

3.Facebook iOS Snapshot Test框架，通過snapshot的方式，進行頁面UI測試

4.IGListKit一個基於UICollectionView的框架，通過LCS衍生優化演算法，進行UICollectionView的刷新

關於本文...

前幾部分都是LCS演算法的一些簡單介紹，感興趣的可以看看，也可直接看靠後的LCS演算法在UICollectionView中的應用。

2傳統的LCS演算法

以最常見的字元串對比為例，我們要從ADFGT變化到AFOXT找出LCS。從後向前進行對比，T相同表明T是LCS的一部分，所以能進一步簡化為：

繼續向前對比ADFG和AFOX，發現G和X不同，這意味著G只可能是字元串ADFG和AFO的LCS，也意味著X只可能是字元串ADF和AFOX的LCS，那麼問題簡化為：

很容易能計算出，這種演算法時間複雜度為O( 2^n )，當字元串或者數組很長時，會非常慢...

3結合動態規劃的改進LCS演算法

動態規劃常常能用來解決一些遞歸問題，LCS問題也是，使用一個二維數組就可以避開遞歸。

仍舊以ADFGT和AFOXT為例，舉例如下 A = "ADFGT" B = "AFOXT" m = A.length n = B.length

1.首先建立一個二維數組table[m+1][n+1]，默認在i=0行和j=0列填充0，如下圖：

2.在其他位置，任一[i][j]，先計算max(table[i-1][j], table[i][j-1])，然後判斷A[i-1]和B[j-1]，相同的話此處填max+1，否則填max，最後填完所有空結果如下：

此時，時間複雜度已經是O( n^2 )，但是我們已經算出兩個字元串LCS的長度是3了，接下來需要利用table將LCS找出來。

仍然選擇從table右下角向坐上角遍歷，中間會遇到三種情況：

1.當i=m+1，j=n+1時，發現此時的A[i]=B[i]，那麼這個元素肯定是LCS的一部分，向左上角走，直接將i-1,j-1

2.此時i=m，j=n時，發現A[i]!=B[i]，那麼比較table[i][j]和table[i-1][j]，當兩者相同時向上走i-1，否則向左走j-1

3.按照前兩種策略一直向左上方走，知道遇到i=0，j=0，結束搜索過程，下圖表明了整個線路，可以看到紅圈內的就是LCS

得到正確的LCS為AFT。

上面過程時間複雜度是O(n)，結合構造table的過程，整個過程時間複雜度是O( n^2 )，遠小於第一種遞歸演算法。

4LCS能做什麼？

上面兩部分介紹了LCS問題的兩種演算法，為什麼要算出LCS？！ 繼續看在上面ADFGT和AFOXT對比算出的table二維數組，會發現幾個有趣的地方：

  • 向左上走的單元，都是兩個字元串重複的部分，即Reload/Move
  • 向上走的單元，都是舊數據中需要刪除的部分，即Delete
  • 向左走的單元，都是新數據中需要插入的部分，即Insert

這麼以來，就很好理解table的作用了，我們也就可以在遍歷table中找到據的所有更新操作如下：

  • Reload：[0]A、[4]T
  • Insert：[2]O、[3]X
  • Delete：[1]D、[3]G
  • Move：[3]F > [2]F

5結合iOS UIColletionView

OK，首先看一下當有數據源後，有哪幾種方法刷新列表？

1. reloadData，最直接最簡單的方式，當數據源很小，Cell樣式簡單時沒有問題，但是：

有非常複雜非常多Cell，Cell Subviews非常複雜的情況下，列如嵌套UIStackView、UICollectionView...直接調用ReloadData，意味著列表會重新計算Cell Size等各種layout attributes，並渲染到屏幕上，這肯定會消耗一部分CPU資源。

某些情況下，載入新數據插入列表最後，調用ReloadData會重走一遍Cell周期，意味著cellWillDisplay，cellDidEndDisplay回調，如果在會回調方法內有很多邏輯處理的話，要格外小心。

2. performBatchUpdates或beginUpdates/endUpdates，可以計算Cell前後變化，調用insert/delete/reload/move等操作。

  • 這麼做可以少計算一些Cell，同時也可以添加一些動畫效果。
  • 但當數據源非常複雜時如何計算前後變化，如何判斷計算後的結果是不是最優方案呢，如果計算中稍有錯誤就會產生Cell和數據源不匹配的Crash。

因此，才希望能通過LCS計算出正確的insert/delete/reload/Move數組，能在提高刷新效率的同時，保證計算的正確性。

6此時存在的問題

現在有兩個問題擺在面前：

  • 第一個問題是上文通過一個二維數組將LCS演算法時間複雜度降低到O( n^2 )，但是會發現，當n很大的時候，比如幾百幾千，這個複雜度也非常高。
  • 其次是Move操作，我們會遇到一些問題，把後一個字元串中的F和T調換一下字母順序，然後對比ADFGT和ATOXF，作出table圖如下:

會發現，按照前面介紹的遍歷table邏輯會有下面的刷新操作：

  • Reload：[0]A
  • Insert：[1]T、[2]O、[3]X
  • Delete：[1]D、[3]G、[4]T
  • Move：[2]F > [4]F

發現其中的T既有Delete也有Insert，但是卻沒有進行Move操作...稍微思考下發現：

當前後數據存在多個LCS結果時，只會取其中一組，其餘的只能進行Insert/Delete操作

這是第二個問題。

7進一步優化方案 -- IGListKit Diff方案

那麼有沒有既能降低時間複雜度，又能對Move操作進行一些優化，而不是簡單調用Insert/Delete的方法呢？

有的。Instagram團隊的IGListKit框架，結合了Paul Heckel』s Diff(1978年)的一篇論文，進一步優化，使用額外一些內存空間，降低時間複雜度到O(n)，並且能準確獲取所有Insert/Delete/Move操作。

簡化問題，仍以ADFGT和ATOXF為例子，首先考慮的是降維處理，避免使用二維數組，結合上面兩張路線路，不難發現，最重要的是沿線路的幾個位置，其餘位置並沒有走過。準確來說，需要走一遍的距離是：

m + n - LCS.length

因此可以確定的說，一定會走過所有去重後的元素，仔細思考下，對於每個元素，我們需要的到底是什麼？

元素在新舊數據中的位置

我們需要一個數據結構能夠快速映射出每個元素到它在新舊數據中的位置，這裡IGListKit選擇使用一個無序去重unordered_map，以每一個元素作為key，以entry為value，entry定義如下：

1. 正序遍歷新數據，對應的每個entry，newCounter++，oldIndexes壓入NSNotFound

2. 因為棧後進先出，倒序遍歷舊數據，對應的每個entry，oldCounter++，oldIndexed壓入元素在舊數據中的位置

3. 由於map的查找速度是O(1)，因此遍歷時間為O(m+n)

以ADFGT和ATOXF為例，經過兩次遍歷，就能獲得下面的map數據，oldIndexes左側表示棧底：

觀察上面的表格，不難發現：

  • oldIndexes棧中只有NSNotFound的表明是新元素，需要Insert
  • oldIndexes棧中只有數字的表明是要刪除的舊元素，需要Delete
  • oldIndexes棧中既有NSNotFound也有數字的元素，需要Move，可能需要Insert/Delete

那麼接下來就是從map數據中得到最終結果，這裡重新定義一個結構體record如下，每一個新舊數據的index都對應一個record，其中entry可以讓我們快速訪問到數據對應的entry，index則用於記錄一個新數據在舊數據中的位置（如果存在的情況下）或一個舊數據在新數據中的位置（如果存在的情況下）。

1.遍歷新數據，對每一個元素對應的entry的棧進行pop，記錄出棧的的數字。如果是NSNotFound表示該元素在舊數據中沒有出現，加入Insert數組。如果是數字則表示舊數據相同元素的位置，那麼將新舊相同數據的record中的index互相設置。

2.遍歷舊數據，對每一個元素對應的entry的棧進行pop，記錄出棧的的數字。如果不是NSNotFound，那麼加入Delete數組。

3.再次遍歷新數據，獲取每一個元素的record，如果index是數字且和新數據位置不同時，表示進行Move操作，如果和新數據位置相同，則表示進行了Reload操作。

能得到最終Record如下，從中不難得到我們需要的各種操作了。

  • Reload：[0]A
  • Insert：[2]O、[3]X
  • Delete：[1]D、[3]G
  • Move：[2]F > [4]F、[4]T > [1]T

只通過五次遍歷就可以得到準確的Diff結果，在O(n)複雜度下完成且能避免多個LCS結果會產生的Move問題。最後只需要進一步封裝，將結果包在UITableView的beginUpdates/endUpdates或UICollectionView的performBatchUpdates中即可。

在每次實際loadMore或者refresh時，調用封裝的performUpdate方法，其中會首先計算前後數據源的diff，得到insert/delete/move操作的indexPath後，再使用系統的performUpdates方法。

IGListKit通過一個unorderedmap解決了所有問題，但使用這種方法有一些小小的弊端。unorderedmap是O(1)的查找速度，內部使用哈希表實現，相比map會使用更多的內存空間。因此在內存比較拘束下，可能會產生問題。

這部分的具體實現代碼參見：IGListDiff.mm

8IGList數據流簡介

在這一步，IGList有自己獨特的處理方式，簡單介紹下IGListKit對UICollectionView封裝，整體架構組成如下圖：

中心調度器是Adapter，adapter作為UICollectionView的datasource，每次都會從sectionController中獲取cell，同時作為UICollectionView和UIScrollView的delegate，負責向sectionController回調。

IGList的adapter對外提供datasource回調，外界需要提供data數組、sectionController的對象實例、以及empty view，官方demo如下圖代碼所示：

其中PostSectionController作為具體section實現，繼承自IGListSectionController，想要添加cell到section中，必須實現其中幾個方法。

在其中發現有幾點需要注意：

1.回調給adapter的data數據必須實現IGListDiffable協議，diff演算法需要用到協議中的兩個方法。

2. PostSectionController中collectionContext實際就是就是adapter，也就是說實際上兩者是相互引用的關係。

3.每次系統的UICollectionView需要數據時，作為dataSource的adapter都會問每一個sectionController，sectionController實際上又向adapter詢問，獲取某個index的cell...

其實IGListSectionController提供了很多property和method，比如inset、space的設置、selected、highlight方法、以及supplementaryViewSource、displayDelegate、workingRangeDelegate、scrollDelegate這幾種很好用的delegate。

其中最有意思的IGListWorkingRangeDelegate協議，設置working range範圍，就可以控制sectionController提前回調下面的方法，IGListKit官方表示可以在這個時候做一些圖片下載，文字計算等工作。具體實現文件可見IGListWorkingRangeHandler.mm，其中使用了unordered_set實現。

9總結

最初只是好奇而研究了IGListKit框架，卻發現針對某些問題解決的非常好。通常在進行列表載入新數據選擇直接reloadData的操作，其中的一些問題和坑都遇到過，iOS的UITableView和UICollectionView會對所有cell重新計算布局再渲染，使用基於LCS的Diff演算法計算出其中差異cell，使用performUpdates進行小範圍的insert/delete/move操作不失為一種新的嘗試。

1.我們常常在UITableView或UICollectionView的delegate方法cellWillDisplay和cellDidEndDisplay中處理一些Cell的埋點。比如展現和消失，但是在loadMore的reloadData後，會回調已經在屏幕中Cell的代理方法，可能會導致埋點多發。

2.實現本地數據過濾，我們常常會遇到本地數據源很多格式的情況，簡單的例子就是文本、圖片、視頻、問答等各種樣式。如果有某種篩選功能。簡單的reloadData能夠實現，但使用insert/delete/move操作可以達到更好的動畫效果。

參考資料：

1. Longest Common Subsequence Diff Part 1

2. Diff in iOS Part 2

3. Open Sourcing IGListKit

4. Isolating Differences Between Files

5. IGListKit Github

6. IGListKit Docs

7. 大規模重構——重寫 Instagram Feed 的經驗之談


推薦閱讀：

※Python小白的日常練習之Codewars
※從字元串中提取頭銜

TAG:字元串 |