Diff应用：从LCS到UICollectionView

前文

什么是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中的应用。

传统的LCS算法

以最常见的字符串对比为例，我们要从ADFGT变化到AFOXT找出LCS。从后向前进行对比，T相同表明T是LCS的一部分，所以能进一步简化为：

image

继续向前对比ADFG和AFOX，发现G和X不同，这意味着G只可能是字符串ADFG和AFO的LCS，也意味着X只可能是字符串ADF和AFOX的LCS，那么问题简化为：

image

很容易能计算出，这种算法时间复杂度为O( 2^n )，当字符串或者数组很长时，会非常慢...

结合动态规划的改进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，如下图：

image

2.在其他位置，任一[i][j]，先计算max(table[i-1][j], table[i][j-1])，然后判断A[i-1]和B[j-1]，相同的话此处填max+1，否则填max，最后填完所有空结果如下：

image

此时，时间复杂度已经是O( n^2 )，但是我们已经算出两个字符串LCS的长度是3了，接下来需要利用table将LCS找出来。

仍然选择从table右下角向坐上角遍历，中间会遇到三种情况：

1.当i=m+1，j=n+1时，发现此时的A[i]=B[i]，那么这个元素肯定是LCS的一部分，向左上角走，直接将i-1,j-1

image

2.此时i=m，j=n时，发现A[i]!=B[i]，那么比较table[i][j]和table[i-1][j]，当两者相同时向上走i-1，否则向左走j-1

image image

3.按照前两种策略一直向左上方走，知道遇到i=0，j=0，结束搜索过程，下图表明了整个线路，可以看到红圈内的就是LCS

image

得到正确的LCS为AFT。

上面过程时间复杂度是O(n)，结合构造table的过程，整个过程时间复杂度是O( n^2 )，远小于第一种递归算法。

4 LCS能做什么？

上面两部分介绍了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

首先看一下当有数据源后，有哪几种方法刷新列表？

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图如下:

image

会发现，按照前面介绍的遍历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定义如下：

image

1. 正序遍历新数据，对应的每个entry，newCounter++，oldIndexes压入NSNotFound

2. 因为栈后进先出，倒序遍历旧数据，对应的每个entry，oldCounter++，oldIndexed压入元素在旧数据中的位置

3. 由于map的查找速度是O(1)，因此遍历时间为O(m+n)

以ADFGT和ATOXF为例，经过两次遍历，就能获得下面的map数据，oldIndexes左侧表示栈底：

image

观察上面的表格，不难发现：

• oldIndexes栈中只有NSNotFound的表明是新元素，需要Insert

• oldIndexes栈中只有数字的表明是要删除的旧元素，需要Delete

• oldIndexes栈中既有NSNotFound也有数字的元素，需要Move，可能需要Insert/Delete

那么接下来就是从map数据中得到最终结果，这里重新定义一个结构体record如下，每一个新旧数据的index都对应一个record，其中entry可以让我们快速访问到数据对应的entry，index则用于记录一个新数据在旧数据中的位置（如果存在的情况下）或一个旧数据在新数据中的位置（如果存在的情况下）。

image

1.遍历新数据，对每一个元素对应的entry的栈进行pop，记录出栈的的数字。如果是NSNotFound表示该元素在旧数据中没有出现，加入Insert数组。如果是数字则表示旧数据相同元素的位置，那么将新旧相同数据的record中的index互相设置。

2.遍历旧数据，对每一个元素对应的entry的栈进行pop，记录出栈的的数字。如果不是NSNotFound，那么加入Delete数组。

3.再次遍历新数据，获取每一个元素的record，如果index是数字且和新数据位置不同时，表示进行Move操作，如果和新数据位置相同，则表示进行了Reload操作。

能得到最终Record如下，从中不难得到我们需要的各种操作了。

image

• 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

8 IGList数据流简介

在这一步，IGList有自己独特的处理方式，简单介绍下IGListKit对UICollectionView封装，整体架构组成如下图：

image

中心调度器是Adapter，adapter作为UICollectionView的datasource，每次都会从sectionController中获取cell，同时作为UICollectionView和UIScrollView的delegate，负责向sectionController回调。

IGList的adapter对外提供datasource回调，外界需要提供data数组、sectionController的对象实例、以及empty view，官方demo如下图代码所示：

image

其中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实现。

image image

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 的经验之谈