前文
什么是Diff春畔？
日常編程中有時候會遇到對比字符串脱货，對比數(shù)組的情況，找出前后新舊數(shù)據(jù)的不同拐迁，可以稱之為Diff蹭劈。
什么是LCS？
Longest Common Subsequence的簡稱线召，最長公共子序列铺韧。
LCS有哪些應(yīng)用？
1.Git等版本控制缓淹，常用的git diff命令
2.一些對比軟件哈打，如Kaleidoscope塔逃，能進行圖片、文件料仗、文本的對比
3.Facebook iOS Snapshot Test框架湾盗，通過snapshot的方式，進行頁面UI測試
4.IGListKit一個基于UICollectionView的框架立轧，通過LCS衍生優(yōu)化算法格粪，進行UICollectionView的刷新
關(guān)于本文...
前幾部分都是LCS算法的一些簡單介紹，感興趣的可以看看氛改，也可直接看靠后的LCS算法在UICollectionView中的應(yīng)用帐萎。
傳統(tǒng)的LCS算法
以最常見的字符串對比為例，我們要從ADFGT變化到AFOXT找出LCS胜卤。從后向前進行對比疆导，T相同表明T是LCS的一部分，所以能進一步簡化為：
繼續(xù)向前對比ADFG和AFOX葛躏，發(fā)現(xiàn)G和X不同澈段，這意味著G只可能是字符串ADFG和AFO的LCS，也意味著X只可能是字符串ADF和AFOX的LCS舰攒，那么問題簡化為：
很容易能計算出败富，這種算法時間復雜度為O( 2^n )，當字符串或者數(shù)組很長時摩窃，會非常慢...
結(jié)合動態(tài)規(guī)劃的改進LCS算法
動態(tài)規(guī)劃常常能用來解決一些遞歸問題囤耳，LCS問題也是，使用一個二維數(shù)組就可以避開遞歸偶芍。
仍舊以ADFGT和AFOXT為例充择，舉例如下 A = "ADFGT" B = "AFOXT" m = A.length n = B.length
1.首先建立一個二維數(shù)組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段化，最后填完所有空結(jié)果如下：
此時嘁捷，時間復雜度已經(jīng)是O( n^2 )，但是我們已經(jīng)算出兩個字符串LCS的長度是3了显熏，接下來需要利用table將LCS找出來雄嚣。
仍然選擇從table右下角向坐上角遍歷，中間會遇到三種情況：
1.當i=m+1，j=n+1時缓升，發(fā)現(xiàn)此時的A[i]=B[i]鼓鲁，那么這個元素肯定是LCS的一部分，向左上角走港谊，直接將i-1,j-1
2.此時i=m骇吭，j=n時，發(fā)現(xiàn)A[i]!=B[i]歧寺，那么比較table[i][j]和table[i-1][j]燥狰，當兩者相同時向上走i-1，否則向左走j-1
3.按照前兩種策略一直向左上方走斜筐，知道遇到i=0碾局，j=0，結(jié)束搜索過程奴艾，下圖表明了整個線路，可以看到紅圈內(nèi)的就是LCS
得到正確的LCS為AFT内斯。
上面過程時間復雜度是O(n)蕴潦，結(jié)合構(gòu)造table的過程，整個過程時間復雜度是O( n^2 )俘闯，遠小于第一種遞歸算法潭苞。
4 LCS能做什么？
上面兩部分介紹了LCS問題的兩種算法真朗，為什么要算出LCS此疹？！ 繼續(xù)看在上面ADFGT和AFOXT對比算出的table二維數(shù)組遮婶，會發(fā)現(xiàn)幾個有趣的地方：
向左上走的單元蝗碎，都是兩個字符串重復的部分，即Reload/Move
向上走的單元旗扑，都是舊數(shù)據(jù)中需要刪除的部分蹦骑，即Delete
向左走的單元，都是新數(shù)據(jù)中需要插入的部分臀防，即Insert
這么以來眠菇，就很好理解table的作用了，我們也就可以在遍歷table中找到據(jù)的所有更新操作如下：
Reload：[0]A袱衷、[4]T
Insert：[2]O捎废、[3]X
Delete：[1]D、[3]G
Move：[3]F > [2]F
5 結(jié)合iOS UIColletionView
首先看一下當有數(shù)據(jù)源后致燥，有哪幾種方法刷新列表登疗？
1. reloadData，最直接最簡單的方式嫌蚤，當數(shù)據(jù)源很小谜叹，Cell樣式簡單時沒有問題匾寝，但是：
有非常復雜非常多Cell，Cell Subviews非常復雜的情況下荷腊，列如嵌套UIStackView艳悔、UICollectionView...直接調(diào)用ReloadData，意味著列表會重新計算Cell Size等各種layout attributes女仰，并渲染到屏幕上猜年，這肯定會消耗一部分CPU資源。
某些情況下疾忍，加載新數(shù)據(jù)插入列表最后乔外，調(diào)用ReloadData會重走一遍Cell周期，意味著cellWillDisplay一罩，cellDidEndDisplay回調(diào)杨幼，如果在會回調(diào)方法內(nèi)有很多邏輯處理的話，要格外小心聂渊。
2. performBatchUpdates或beginUpdates/endUpdates差购，可以計算Cell前后變化，調(diào)用insert/delete/reload/move等操作汉嗽。
這么做可以少計算一些Cell欲逃，同時也可以添加一些動畫效果。
但當數(shù)據(jù)源非常復雜時如何計算前后變化饼暑，如何判斷計算后的結(jié)果是不是最優(yōu)方案呢稳析，如果計算中稍有錯誤就會產(chǎn)生Cell和數(shù)據(jù)源不匹配的Crash。
因此弓叛，才希望能通過LCS計算出正確的insert/delete/reload/Move數(shù)組彰居，能在提高刷新效率的同時，保證計算的正確性撰筷。
6 此時存在的問題
現(xiàn)在有兩個問題擺在面前：
第一個問題是上文通過一個二維數(shù)組將LCS算法時間復雜度降低到O( n^2 )裕菠，但是會發(fā)現(xiàn)，當n很大的時候闭专，比如幾百幾千奴潘，這個復雜度也非常高。
其次是Move操作影钉，我們會遇到一些問題画髓，把后一個字符串中的F和T調(diào)換一下字母順序，然后對比ADFGT和ATOXF平委，作出table圖如下:
會發(fā)現(xiàn)奈虾，按照前面介紹的遍歷table邏輯會有下面的刷新操作：
Reload：[0]A
Insert：[1]T、[2]O、[3]X
Delete：[1]D肉微、[3]G匾鸥、[4]T
Move：[2]F > [4]F
發(fā)現(xiàn)其中的T既有Delete也有Insert，但是卻沒有進行Move操作...稍微思考下發(fā)現(xiàn)：
當前后數(shù)據(jù)存在多個LCS結(jié)果時碉纳，只會取其中一組勿负，其余的只能進行Insert/Delete操作
這是第二個問題。
7 進一步優(yōu)化方案 -- IGListKit Diff方案
那么有沒有既能降低時間復雜度劳曹，又能對Move操作進行一些優(yōu)化奴愉，而不是簡單調(diào)用Insert/Delete的方法呢？
有的铁孵。Instagram團隊的IGListKit框架锭硼，結(jié)合了Paul Heckel’s Diff(1978年)的一篇論文，進一步優(yōu)化蜕劝，使用額外一些內(nèi)存空間檀头，降低時間復雜度到O(n)，并且能準確獲取所有Insert/Delete/Move操作岖沛。
簡化問題暑始，仍以ADFGT和ATOXF為例子，首先考慮的是降維處理烫止，避免使用二維數(shù)組，結(jié)合上面兩張路線路戳稽，不難發(fā)現(xiàn)馆蠕，最重要的是沿線路的幾個位置，其余位置并沒有走過惊奇。準確來說互躬，需要走一遍的距離是：
m + n - LCS.length
因此可以確定的說，一定會走過所有去重后的元素颂郎，仔細思考下吼渡，對于每個元素，我們需要的到底是什么乓序？
元素在新舊數(shù)據(jù)中的位置
我們需要一個數(shù)據(jù)結(jié)構(gòu)能夠快速映射出每個元素到它在新舊數(shù)據(jù)中的位置寺酪，這里IGListKit選擇使用一個無序去重unordered_map，以每一個元素作為key替劈，以entry為value寄雀，entry定義如下：
1. 正序遍歷新數(shù)據(jù)，對應(yīng)的每個entry陨献，newCounter++盒犹，oldIndexes壓入NSNotFound
2. 因為棧后進先出，倒序遍歷舊數(shù)據(jù)，對應(yīng)的每個entry急膀，oldCounter++沮协，oldIndexed壓入元素在舊數(shù)據(jù)中的位置
3. 由于map的查找速度是O(1)，因此遍歷時間為O(m+n)
以ADFGT和ATOXF為例卓嫂，經(jīng)過兩次遍歷慷暂，就能獲得下面的map數(shù)據(jù)，oldIndexes左側(cè)表示棧底：
觀察上面的表格命黔，不難發(fā)現(xiàn)：
oldIndexes棧中只有NSNotFound的表明是新元素呜呐，需要Insert
oldIndexes棧中只有數(shù)字的表明是要刪除的舊元素，需要Delete
oldIndexes棧中既有NSNotFound也有數(shù)字的元素悍募，需要Move蘑辑，可能需要Insert/Delete
那么接下來就是從map數(shù)據(jù)中得到最終結(jié)果，這里重新定義一個結(jié)構(gòu)體record如下坠宴，每一個新舊數(shù)據(jù)的index都對應(yīng)一個record洋魂，其中entry可以讓我們快速訪問到數(shù)據(jù)對應(yīng)的entry，index則用于記錄一個新數(shù)據(jù)在舊數(shù)據(jù)中的位置（如果存在的情況下）或一個舊數(shù)據(jù)在新數(shù)據(jù)中的位置（如果存在的情況下）喜鼓。
1.遍歷新數(shù)據(jù)副砍，對每一個元素對應(yīng)的entry的棧進行pop，記錄出棧的的數(shù)字庄岖。如果是NSNotFound表示該元素在舊數(shù)據(jù)中沒有出現(xiàn)豁翎，加入Insert數(shù)組。如果是數(shù)字則表示舊數(shù)據(jù)相同元素的位置隅忿，那么將新舊相同數(shù)據(jù)的record中的index互相設(shè)置心剥。
2.遍歷舊數(shù)據(jù)，對每一個元素對應(yīng)的entry的棧進行pop背桐，記錄出棧的的數(shù)字优烧。如果不是NSNotFound，那么加入Delete數(shù)組链峭。
3.再次遍歷新數(shù)據(jù)畦娄，獲取每一個元素的record，如果index是數(shù)字且和新數(shù)據(jù)位置不同時弊仪，表示進行Move操作熙卡，如果和新數(shù)據(jù)位置相同，則表示進行了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結(jié)果，在O(n)復雜度下完成且能避免多個LCS結(jié)果會產(chǎn)生的Move問題灾杰。最后只需要進一步封裝蚊丐，將結(jié)果包在UITableView的beginUpdates/endUpdates或UICollectionView的performBatchUpdates中即可。
在每次實際loadMore或者refresh時艳吠，調(diào)用封裝的performUpdate方法麦备，其中會首先計算前后數(shù)據(jù)源的diff，得到insert/delete/move操作的indexPath后昭娩，再使用系統(tǒng)的performUpdates方法凛篙。
IGListKit通過一個unorderedmap解決了所有問題，但使用這種方法有一些小小的弊端栏渺。unorderedmap是O(1)的查找速度呛梆，內(nèi)部使用哈希表實現(xiàn)，相比map會使用更多的內(nèi)存空間磕诊。因此在內(nèi)存比較拘束下填物，可能會產(chǎn)生問題。
這部分的具體實現(xiàn)代碼參見：IGListDiff.mm
8 IGList數(shù)據(jù)流簡介
在這一步霎终，IGList有自己獨特的處理方式滞磺，簡單介紹下IGListKit對UICollectionView封裝，整體架構(gòu)組成如下圖：
中心調(diào)度器是Adapter莱褒，adapter作為UICollectionView的datasource击困，每次都會從sectionController中獲取cell，同時作為UICollectionView和UIScrollView的delegate广凸，負責向sectionController回調(diào)阅茶。
IGList的adapter對外提供datasource回調(diào)，外界需要提供data數(shù)組炮障、sectionController的對象實例目派、以及empty view坤候，官方demo如下圖代碼所示：
其中PostSectionController作為具體section實現(xiàn)胁赢，繼承自IGListSectionController，想要添加cell到section中白筹，必須實現(xiàn)其中幾個方法智末。
在其中發(fā)現(xiàn)有幾點需要注意：
1.回調(diào)給adapter的data數(shù)據(jù)必須實現(xiàn)IGListDiffable協(xié)議，diff算法需要用到協(xié)議中的兩個方法徒河。
2. PostSectionController中collectionContext實際就是就是adapter系馆，也就是說實際上兩者是相互引用的關(guān)系。
3.每次系統(tǒng)的UICollectionView需要數(shù)據(jù)時顽照，作為dataSource的adapter都會問每一個sectionController由蘑，sectionController實際上又向adapter詢問闽寡，獲取某個index的cell...
其實IGListSectionController提供了很多property和method，比如inset尼酿、space的設(shè)置爷狈、selected、highlight方法裳擎、以及supplementaryViewSource涎永、displayDelegate、workingRangeDelegate鹿响、scrollDelegate這幾種很好用的delegate羡微。
其中最有意思的IGListWorkingRangeDelegate協(xié)議，設(shè)置working range范圍惶我，就可以控制sectionController提前回調(diào)下面的方法妈倔，IGListKit官方表示可以在這個時候做一些圖片下載，文字計算等工作指孤。具體實現(xiàn)文件可見IGListWorkingRangeHandler.mm启涯，其中使用了unordered_set實現(xiàn)。
9 總結(jié)
最初只是好奇而研究了IGListKit框架恃轩，卻發(fā)現(xiàn)針對某些問題解決的非常好结洼。通常在進行列表加載新數(shù)據(jù)選擇直接reloadData的操作，其中的一些問題和坑都遇到過叉跛，iOS的UITableView和UICollectionView會對所有cell重新計算布局再渲染松忍，使用基于LCS的Diff算法計算出其中差異cell，使用performUpdates進行小范圍的insert/delete/move操作不失為一種新的嘗試筷厘。
1.我們常常在UITableView或UICollectionView的delegate方法cellWillDisplay和cellDidEndDisplay中處理一些Cell的埋點鸣峭。比如展現(xiàn)和消失，但是在loadMore的reloadData后酥艳，會回調(diào)已經(jīng)在屏幕中Cell的代理方法摊溶，可能會導致埋點多發(fā)。
2.實現(xiàn)本地數(shù)據(jù)過濾充石，我們常常會遇到本地數(shù)據(jù)源很多格式的情況莫换，簡單的例子就是文本、圖片骤铃、視頻拉岁、問答等各種樣式。如果有某種篩選功能惰爬。簡單的reloadData能夠?qū)崿F(xiàn)喊暖，但使用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
- IGListKit Github
6.IGListKit Docs
7. 大規(guī)模重構(gòu)——重寫 Instagram Feed 的經(jīng)驗之談
