写在前面
在上一篇文章从LCS到IGListKit框架中的Diff算法（上）中我们详细讲了 $LCS$ 是什么、怎么使用动态规划来求解 $LCS$ ，最后我们也抛出了 $LCS$ 还存在的两个问题，本篇文章我们就主要来分析IGListKit框架中的Diff是如何来解决这两个问题的。
温馨提示：本文主要剖析IGListKit框架中的Diff算法，不会讲IGListKit框架的具体使用。
$LCS$ 存在的问题带来的思考
上一篇文章我们提出了 $LCS$ 存在的两个问题：
- 但是当n特别大的时候，$O(n^2)$ 这个时间复杂度依然比较可怕。
- 希望对新、旧数据都存在的元素的Move进行一些优化，而不是简单的Delete、Insert操作。
Instagram团队的IGListKit框架结合Paul Heckel’s Diff（1978年）的一篇论文做了进一步的优化，使用一些额外的内存空间，把时间复杂度降低到了$O(n)$ ，并且能够准确获取数据元素的Move/Insert等操作。
这里，我们还以上一篇文章的两个序列为例：
$X = <A,D,F,G,T>$
$Y = <A,T,O,X,F>$
求 $X$ 和 $Y$ 的 $LCS$
我们首先需要处理的是避免使用二维数组，我们结合上图会发现重要的只是我们标记的这条线路，其他位置我们并没有用到，那么需要走一遍的距离就是：$m + n - LCS的长度$
所以，肯定要走过所有去重之后的元素，仔细思考一下，对于每个元素，我们需要的是什么？
IGListKit框架的刷新流程
到这里，我们已经跟踪到IGListKit框架刷新机制的核心部分：IGListDiff类中的IGListDiffing函数，接下来就是本文的重点了：IGListDiff是如何实现的？
IGListDiff算法详解
在理解Diff算法之前我们先来熟悉几个数据结构、函数体：IGListIndexSetResult、IGListEntry、IGListRecord、IGListDiffable、IGListMoveIndex。
IGListMoveIndex
IGListMoveIndex 封装的是一个移动的操作，from是旧数组的索引，to是新数组的索引：
@interface IGListMoveIndex : NSObject
@property (nonatomic, assign, readonly) NSInteger from;
@property (nonatomic, assign, readonly) NSInteger to;
@end
|
IGListIndexSetResult
IGListIndexSetResult封装的是一个关于插入、删除等操作的集合：
@interface IGListIndexSetResult : NSObject
@property (nonatomic, strong, readonly) NSIndexSet *inserts;
@property (nonatomic, strong, readonly) NSIndexSet *deletes;
@property (nonatomic, strong, readonly) NSIndexSet *updates;
@property (nonatomic, copy, readonly) NSArray<IGListMoveIndex *> *moves;
@property (nonatomic, assign, readonly) BOOL hasChanges;
@end
|
IGListDiffable
IGListDiffable是一个协议，要求数组里的对象都需要遵循这个协议才能有效地使用diff函数：
@protocol IGListDiffable
- (nonnull id<NSObject>)diffIdentifier;
- (BOOL)isEqualToDiffableObject:(nullable id<IGListDiffable>)object;
@end
|
IGListEntry
IGListEntry是用于标记元素状态的结构体：
struct IGListEntry {
NSInteger oldCounter = 0;
NSInteger newCounter = 0;
stack<NSInteger> oldIndexes;
BOOL updated = NO;
};
|
IGListRecord
ICListRecord是封装entry结构体和它所在的索引，主要用于插入和删除（如果index有值，则代表该元素需要插入或者更新，否则为NSNotFound，则是需要删除）
struct IGListRecord {
IGListEntry *entry;
mutable NSInteger index;
IGListRecord() {
entry = NULL;
index = NSNotFound;
}
};
|
IGListDiffing函数的算法流程
变量的声明：
const NSInteger newCount = newArray.count;
const NSInteger oldCount = oldArray.count;
NSMapTable *oldMap = [NSMapTable strongToStrongObjectsMapTable];
NSMapTable *newMap = [NSMapTable strongToStrongObjectsMapTable];
|
处理特殊情况:
如果newcount == 0 或 oldcount == 0，即是删除所有旧元素或新增所有新元素，直接返回IGListIndexSetResult集合，不需要走下面的diff算法流程。
if (newCount == 0) {
return [[IGListIndexSetResult alloc] initWithInserts:[NSIndexSet new]
deletes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, oldCount)]
updates:[NSIndexSet new]
moves:[NSArray new]
oldIndexMap:oldMap
newIndexMap:newMap];
}
if (oldCount == 0) {
[newArray enumerateObjectsUsingBlock:^(id<IGListDiffable> obj, NSUInteger idx, BOOL *stop) {
addIndexToMap(returnIndexPaths, toSection, idx, obj, newMap);
}];
return [[IGListIndexSetResult alloc] initWithInserts:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, newCount)]
deletes:[NSIndexSet new]
updates:[NSIndexSet new]
moves:[NSArray new]
oldIndexMap:oldMap
newIndexMap:newMap];
}
|
Diff算法第一步：
先定义一个无序去重unordered_map的table，以diffIdentifier为Key，entry为Value，其查找复杂度为$O(1)$。
unordered_map<id<NSObject>, IGListEntry, IGListHashID, IGListEqualID> table;
|
正序遍历新数组：
vector<IGListRecord> newResultsArray(newCount);
for (NSInteger i = 0; i < newCount; i++) {
id<NSObject> key = IGListTableKey(newArray[i]);
IGListEntry &entry = table[key];
entry.newCounter++;
entry.oldIndexes.push(NSNotFound);
newResultsArray[i].entry = &entry;
}
|
Diff算法第二步：
倒序遍历旧数组：
vector<IGListRecord> oldResultsArray(oldCount);
for (NSInteger i = oldCount - 1; i >= 0; i--) {
id<NSObject> key = IGListTableKey(oldArray[i]);
IGListEntry &entry = table[key];
entry.oldCounter++;
entry.oldIndexes.push(i);
oldResultsArray[i].entry = &entry;
}
|
温馨提示：这里采用倒序遍历是为了保证，当存在多个key相同的时候，oldIndexes会有一系列的索引入栈，保证栈顶的索引是最小的。
分析：
在上面两部之后，会建立一个用于存放IGListRecord的oldResultsArray，此时每个IGListRecord仍为NSNotFound，对于oldResultsArray和 newResultsArray中的entry，会有三种情况：
- 该元素只有新数组有，则
entry的newCounter>0，oldCounter=0,oldIndexes栈顶为NSNotFound。
- 该元素只有旧数组有，则
entry的newCounter=0，oldCounter>0,oldIndexes栈顶不为NSNotFound，而是元素在旧数组中的最小索引。
- 该元素新旧数组都有，则
entry的newCounter>0，oldCounter>0,oldIndexes栈顶不为NSNotFound，而是元素在旧数组中的最小索引,而oldResultsArray和newResultsArray都指向同一个entry。
Diff算法第三步：
处理同时出现在新、旧数组里面的都存在的元素(注意：这里所说的存在的元素不是指两个元素的值相，而是我们指定的identifier相等，这一点大家要注意一下)，其IGListRecord的index会赋上新、旧数据的索引：
for (NSInteger i = 0; i < newCount; i++) {
IGListEntry *entry = newResultsArray[i].entry;
NSCAssert(!entry->oldIndexes.empty(), @"Old indexes is empty while iterating new item %li. Should have NSNotFound", (long)i);
const NSInteger originalIndex = entry->oldIndexes.top();
entry->oldIndexes.pop();
if (originalIndex < oldCount) {
const id<IGListDiffable> n = newArray[i];
const id<IGListDiffable> o = oldArray[originalIndex];
switch (option) {
case IGListDiffPointerPersonality:
if (n != o) {
entry->updated = YES;
}
break;
case IGListDiffEquality:
if (n != o && ![n isEqualToDiffableObject:o]) {
entry->updated = YES;
}
break;
}
}
if (originalIndex != NSNotFound && entry->newCounter > 0 && entry->oldCounter > 0) {
newResultsArray[i].index = originalIndex;
oldResultsArray[originalIndex].index = i;
}
}
|
Diff算法第四步：
遍历老数据，处理需要删除的元素：
id mInserts, mMoves, mUpdates, mDeletes;
if (returnIndexPaths) {
mInserts = [NSMutableArray<NSIndexPath *> new];
mMoves = [NSMutableArray<IGListMoveIndexPath *> new];
mUpdates = [NSMutableArray<NSIndexPath *> new];
mDeletes = [NSMutableArray<NSIndexPath *> new];
} else {
mInserts = [NSMutableIndexSet new];
mMoves = [NSMutableArray<IGListMoveIndex *> new];
mUpdates = [NSMutableIndexSet new];
mDeletes = [NSMutableIndexSet new];
}
vector<NSInteger> deleteOffsets(oldCount), insertOffsets(newCount);
NSInteger runningOffset = 0;
for (NSInteger i = 0; i < oldCount; i++) {
deleteOffsets[i] = runningOffset;
const IGListRecord record = oldResultsArray[i];
if (record.index == NSNotFound) {
addIndexToCollection(returnIndexPaths, mDeletes, fromSection, i);
runningOffset++;
}
addIndexToMap(returnIndexPaths, fromSection, i, oldArray[i], oldMap);
}
|
Diff算法第五步：
runningOffset = 0;
for (NSInteger i = 0; i < newCount; i++) {
insertOffsets[i] = runningOffset;
const IGListRecord record = newResultsArray[i];
const NSInteger oldIndex = record.index;
if (record.index == NSNotFound) {
addIndexToCollection(returnIndexPaths, mInserts, toSection, i);
runningOffset++;
} else {
if (record.entry->updated) {
addIndexToCollection(returnIndexPaths, mUpdates, fromSection, oldIndex);
}
const NSInteger insertOffset = insertOffsets[i];
const NSInteger deleteOffset = deleteOffsets[oldIndex];
if ((oldIndex - deleteOffset + insertOffset) != i) {
id move;
if (returnIndexPaths) {
NSIndexPath *from = [NSIndexPath indexPathForItem:oldIndex inSection:fromSection];
NSIndexPath *to = [NSIndexPath indexPathForItem:i inSection:toSection];
move = [[IGListMoveIndexPath alloc] initWithFrom:from to:to];
} else {
move = [[IGListMoveIndex alloc] initWithFrom:oldIndex to:i];
}
[mMoves addObject:move];
}
}
|
Diff算法第六步：
处理完插入、删除、更新、移动之后，返回IGListIndexSetResult类型的值，到这里，IGListKit框架中整个Diff 核心部分就结束了，只讲原理肯定很空洞，我们这里举一个实际的例子来走一遍这个Diff的流程，加深印象和理解。
实际刷新举例说明
一、现在比如一个UICollectionView列表中的初始数据为oldDatasource，数据如下：
BasicModel *model0 = [[BasicModel alloc] init];
model0.modelId = @"123";
model0.title = @"A";
BasicModel *model1 = [[BasicModel alloc] init];
model1.modelId = @"234";
model1.title = @"B";
BasicModel *model2 = [[BasicModel alloc] init];
model2.modelId = @"345";
model2.title = @"C";
[self.oldDatasource addObjectsFromArray:@[model0,model1,model2]];
|
二、刷新后的数据为freshDatasource，数据如下：
BasicModel *model3 = [[BasicModel alloc] init];
model3.modelId = @"123";
model3.title = @"D";
BasicModel *model4 = [[BasicModel alloc] init];
model4.modelId = @"345";
model4.title = @"C";
BasicModel *model5 = [[BasicModel alloc] init];
model5.modelId = @"456";
model5.title = @"E";
[self.freshDatasource addObjectsFromArray:@[model3,model4,model5]];
|
三、在BasicModel中遵守<IGListDiffable>协议，实现下面两个方法：
@implementation BasicModel
- (id<NSObject>)diffIdentifier {
if (self.modelId) {
return self.modelId;
}
return self;
}
- (BOOL)isEqualToDiffableObject:(BasicModel <IGListDiffable>*)object {
return [self isEqual:object];
}
@end
|
四、经过Diff核心算法第一步之后的结构如下：
newResultsArray里面有三个 IGListRecord 类型的元素，元素里面的entry情况如下：
entry[D].newCounter = 1;
entry[D].oldIndexes.pop() = NSNotFound;
entry[D].updated = NO;
entry[C].newCounter = 1;
entry[C].oldIndexes.pop() = NSNotFound;
entry[C].updated = NO;
entry[E].newCounter = 1;
entry[E].oldIndexes.pop() = NSNotFound;
entry[E].updated = NO;
|
五、经过Diff核心算法第二步之后的结构如下：
oldResultsArray里面有三个 IGListRecord 类型的元素，元素里面的entry情况如下：
entry[C].oldCounter = 1;
entry[C].oldIndexes.pop() = 2;
entry[C].updated = NO;
entry[B].oldCounter = 1;
entry[B].oldIndexes.pop() = 1;
entry[B].updated = NO;
entry[A].oldCounter = 1;
entry[A].oldIndexes.pop() = 0;
entry[A].updated = NO;
|
六、经过Diff核心算法第三步之后的结构如下：
entry[D].updated = YES;
entry[C].updated = YES;
newResultsArray[0].index = 0;
oldResultsArray[0].index = 0;
newResultsArray[1].index = 2;
oldResultsArray[2].index = 1;
|
七、经过Diff核心算法第四步之后的结构如下：
因为 oldResultsArray[1].index = NSNotFound，所以老数据中这个位置元素需要被删除，即是数据B。
|
八、经过Diff核心算法第五步之后的结构如下：
因为 newResultsArray[2].index = NSNotFound，所以新数据中这个位置元素需要插入，即是数据E。
D元素是更新，C元素是移动。
|
九、最后的结论：
Insert: E
Update: D(A -> D)
Move: C
Delete: B
|
总结
看到这里，相信大家对IGListKit框架中Diff算法实现原理有了一个更加清晰的了解，这个算法的时间复杂度就变成了$O(n)$，ICListKit框架就是通过这种刷新机制来提升了APP的整体性能。
微信
支付宝
