数据源Diff算法分析

在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的做法。

1. 维护一个局部表table用来保存所有的元素，包括新的和旧的。
2. 遍历一次新旧dataSource，加入1中的table，并且再生成两份包含位置信息的对应数组newArray, oldArray。
3. 遍历一次newArray，由于元素包含新、旧的位置信息，所以不需要去old查找就可以直接根据index取出，这样就可以判断移动的元素了。
4. 同样为了解决insert和delete导致的index偏移，IG采用的方式是创建一个数组，分别存储每个元素位置所对应的insertOffset和deleteOffset，这样也只需要for循环一次就够了。

如果不算table的复杂度，结果为o(n)，如果算table的复杂度，那么就是table的复杂度。

缺点是需要使用hash table，需要一个唯一的key(特定情况下可以是指针值)。

同时IG是用c++编写，大大降低了调用开销。以后DDComponent需要增加auto diff的功能的时候可以参考IG的实现方式。