在IGList中有一個非常神奇的功能，就是可以根據(jù)數(shù)據(jù)源直接算出列表變化，采用update的方式更新列表，不需要每次都調(diào)用reloadData。我也想將這個功能引入DDComponent，所以就對diff功能稍微看了看。

由于IGList是數(shù)據(jù)驅(qū)動的，所以他有著天然的前提可以利用，而DDComponent是基于結(jié)構(gòu)來組合的，所以需要一些額外的接口來暴露數(shù)據(jù)源。這些都是題外話了，現(xiàn)在來看看diff的兩種實現(xiàn)。

恰好最近看到一篇文章介紹數(shù)據(jù)源diff的，他所介紹的是Doppelganger?，F(xiàn)在就Doppelganger和IGList里面的算法進行分析。

Doppelganger

diff的結(jié)果使用如下結(jié)構(gòu)，這個設(shè)計其實有部分冗余，可能作者是為了返回結(jié)果的統(tǒng)一性才做成這樣的。

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代表了被刪除的個數(shù)，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;
        // 同時新增一個的個數(shù)也會產(chǎn)生偏移, 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)，真的是這樣嗎？

一眼看去這里出現(xiàn)了兩個for循環(huán)，應(yīng)該就是o(n^2)，但是別忘了[insertedObjects containsObject:rightObj]，很遺憾這里的復(fù)雜度應(yīng)該為o(n)，所以最終他的算法應(yīng)該是o(n^3)。

同時在計算delete和insert的時候，復(fù)雜度也不是o(n)的。而且在整個算法中大量調(diào)用isEqual:也會導(dǎo)致效率降低。

可以說這個如果是少部分場景使用是沒有問題的，但是大量內(nèi)容的時候可能會出現(xiàn)性能問題。

IGList

很多時候，算法優(yōu)化都是用空間來換取時間，這里來簡要說明一下IGList的做法。

1. 維護一個局部表table用來保存所有的元素，包括新的和舊的。
2. 遍歷一次新舊dataSource，加入1中的table，并且再生成兩份包含位置信息的對應(yīng)數(shù)組newArray, oldArray。
3. 遍歷一次newArray，由于元素包含新、舊的位置信息，所以不需要去old查找就可以直接根據(jù)index取出，這樣就可以判斷移動的元素了。
4. 同樣為了解決insert和delete導(dǎo)致的index偏移，IG采用的方式是創(chuàng)建一個數(shù)組，分別存儲每個元素位置所對應(yīng)的insertOffset和deleteOffset，這樣也只需要for循環(huán)一次就夠了。

如果不算table的復(fù)雜度，結(jié)果為o(n)，如果算table的復(fù)雜度，那么就是table的復(fù)雜度。

缺點是需要使用hash table，需要一個唯一的key(特定情況下可以是指針值)。

同時IG是用c++編寫，大大降低了調(diào)用開銷。以后DDComponent需要增加auto diff的功能的時候可以參考IG的實現(xiàn)方式。