在IGList中有一个非常神奇的功能，就是可以根据数据源直接算出列表变化，采用update的方式更新列表，不需要每次都调用reloadData。我也想将这个功能引入DDComponent，所以就对diff功能稍微看了看。
由于IGList是数据驱动的，所以他有着天然的前提可以利用，而DDComponent是基于结构来组合的，所以需要一些额外的接口来暴露数据源。这些都是题外话了，现在来看看diff的两种实现。
恰好最近看到一篇文章介绍数据源diff的，他所介绍的是Doppelganger。现在就Doppelganger和IGList里面的算法进行分析。
Doppelganger
diff的结果使用如下结构，这个设计其实有部分冗余，可能作者是为了返回结果的统一性才做成这样的。
typedef NS_ENUM(NSInteger, WMLArrayDiffType) {
WMLArrayDiffTypeMove,
WMLArrayDiffTypeInsert,
WMLArrayDiffTypeDelete
};
@interface WMLArrayDiff : NSObject
@property (nonatomic, readonly) WMLArrayDiffType type;
@property (nonatomic, readonly) NSUInteger previousIndex;
@property (nonatomic, readonly) NSUInteger currentIndex;
@end
算法部分
// delete和insert都比较简单，我们来看move
NSArray *moveDiffs = [self _moveDiffsWithDeletedObjects:deletedObject insertedObjects:insertedObjects];
NSArray *deletionDiffs = [self _deletionsForArray:self.previousArray deletedObjects:deletedObject];
NSArray *insertionDiffs = [self _insertionForArray:self.currentArray insertedObjects:insertedObjects];
__block NSInteger delta = 0;
// 这里的delta代表了被删除的个数，realIndex = originalIndex - delta
NSMutableArray *result = [NSMutableArray array];
[self.previousArray enumerateObjectsUsingBlock:^(id leftObj, NSUInteger leftIdx, BOOL *stop) {
if ([deletedObjects containsObject:leftObj]) {
delta++;
return;
}
NSUInteger localDelta = delta;
// 同时新增一个的个数也会产生偏移, realIndex = originalIndex - deletedDelta + insertDelta
for (NSUInteger rightIdx = 0; rightIdx < self.currentArray.count; ++rightIdx) {
id rightObj = self.currentArray[rightIdx];
if ([insertedObjects containsObject:rightObj]) {
localDelta--;
continue;
}
if (![rightObj isEqual:leftObj]) {
continue;
}
NSInteger adjustedRightIdx = rightIdx + localDelta;
if (leftIdx != rightIdx && adjustedRightIdx != leftIdx) {
[result addObject:[WMLArrayDiff arrayDiffForMoveFromIndex:leftIdx toIndex:rightIdx]];
}
return;
}
}];
作者认为他的算法是o(n^2)，真的是这样吗？
一眼看去这里出现了两个for循环，应该就是o(n^2)，但是别忘了[insertedObjects containsObject:rightObj]，很遗憾这里的复杂度应该为o(n)，所以最终他的算法应该是o(n^3)。
同时在计算delete和insert的时候，复杂度也不是o(n)的。而且在整个算法中大量调用isEqual:也会导致效率降低。
可以说这个如果是少部分场景使用是没有问题的，但是大量内容的时候可能会出现性能问题。
IGList
很多时候，算法优化都是用空间来换取时间，这里来简要说明一下IGList的做法。
- 维护一个局部表table用来保存所有的元素，包括新的和旧的。
- 遍历一次新旧dataSource，加入1中的table，并且再生成两份包含位置信息的对应数组newArray, oldArray。
- 遍历一次newArray，由于元素包含新、旧的位置信息，所以不需要去old查找就可以直接根据index取出，这样就可以判断移动的元素了。
- 同样为了解决insert和delete导致的index偏移，IG采用的方式是创建一个数组，分别存储每个元素位置所对应的insertOffset和deleteOffset，这样也只需要for循环一次就够了。
如果不算table的复杂度，结果为o(n)，如果算table的复杂度，那么就是table的复杂度。
缺点是需要使用hash table，需要一个唯一的key(特定情况下可以是指针值)。
同时IG是用c++编写，大大降低了调用开销。以后DDComponent需要增加auto diff的功能的时候可以参考IG的实现方式。
