2017-04-18

快速计算两组数据源的变化的方法 - Doppelganger 源码剖析

Doppelganger 源码剖析

性能优化系列一：如何快速的计算UITableView的数据量变换。

今天要介绍的是一个比较精简但是很实用的库：Doppelganger。平时我们经常会和UITableView或者UICollectionView打交道，所以数据源（dataSource）及其变化就非常重要。

如何高效的求解两次数据源之间的删除、增加以及移动（交换位置）就成为了一个可以显著加速的地方。

备注：这里指的是将一定量的数据计算放在客户端来进行，而不是通过多次发送网络请求获取数据然后整体重新刷新。有人会问，什么情况下会有这样的需求呢？比如，你有个用户选项，可以支持按照倒序或者正序的方式进行布局，那这个时候，你直接在本地进行计算并展示差量布局计算，就要比从网络请求多次拉取整体重新刷新的效果赞很多。

本文提到的Doppelganger其实就是一种对于上述需求的封装，提供了及其简化的数据源更新机制。抛开其性能不谈，我们先来看看其实现。

数据结构

从需求不难看出，我们的数据结构需要支持如下潜在数据记录：

改动类型：增加、删除、移动
改动索引：增加的话，是插入到哪行、删除的话是删除哪行、移动的话是从哪行移动到哪行。

基于此，数据结构的定义就很显而易见了：

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

其中，有些字段在某些类型下可以为空。

计算变动

我们先简化下我们的模型，我们就是两个数组A和B，里面各自一堆不重复的数字，分别代表之前的数据源和现在的数据源。现在我们需要求得这两个数组之前提到的三种变化。

首先是删除的计算，非常简单，只要计算在A中不在B中就可以：

NSSet *deletedObject = ({
    NSMutableSet *set = [previousSet mutableCopy];
    [set minusSet:currentSet];
    [set copy];
});

然后是增加的计算，同样简单，只要计算在B中不在A中的：

NSSet *insertedObjects = ({
    NSMutableSet *set = [currentSet mutableCopy];
    [set minusSet:previousSet];
    [set copy];
});

最后就是计算那些即在A中又在B中的改变，对于这种计算，我们要得到在A中的原索引和现在的新索引。

- (NSArray *)_moveDiffsWithDeletedObjects:(NSSet *)deletedObjects insertedObjects:(NSSet *)insertedObjects {    
    // TODO: Improve on O(n^2)
    __block NSInteger delta = 0;
    NSMutableArray *result = [NSMutableArray array];
    [self.previousArray enumerateObjectsUsingBlock:^(id leftObj, NSUInteger leftIdx, BOOL *stop) {
        if ([deletedObjects containsObject:leftObj]) {
            delta++;
            return; 
        }
        NSUInteger localDelta = delta;
        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;
            // 首先如果前后索引一致，没有变化的区别，没有必要做diff变化
            // 或者如果你前面删除了一条，自身索引是1，然后这边是0，那也没必要做move变化。
            if (leftIdx != rightIdx && adjustedRightIdx != leftIdx) {
                [result addObject:[WMLArrayDiff arrayDiffForMoveFromIndex:leftIdx toIndex:rightIdx]];
            }
            return;
        }
    }];
    return [result copy];
}

上述代码一开始我看了也是懵逼了，我觉得直接二重遍历计算同样数在不同两组数据源中的索引区别不就行了？在读了代码一遍以后确定了，作者的思路是这样的：

如果在旧数组中和新数组中的数据源一样，那就不更新了，也即leftIdx != rightIdx的判断。
如果在旧数组中，索引为1，但是之前的0索引位置的数据删除了；然后这个索引为1的数据在新数据中位置为索引0，那么也不需要改了，因为之前计算删除变化的时候已经做了这个相同的效果。

时间复杂度

虽然不知道苹果内部的数据结构代码实现是如何的，但是我们可以进行数据模拟，同时也可以看看苹果WWDC的文章来进行时间复杂度估算。

而从上面实现的计算变动源代码来看，整个库的实现时间复杂度还是有所欠缺的，到达了O(mn) + O(n) ≈ O(mn)的级别，因此我们可以进行一些优化。

备注：O(mn)就是二重循环遍历的问题。其中m是数据源A的数据个数，n是数据源b的数据个数。简单来看就是O(n^2)级别的运算耗时。

怎么优化呢，答案很简单，就是利用动态规划思想来求解最小编辑距离。

我们举个简单的例子，还是没有重复数组的数组，A = [1, 3, 5, 6, 8]以及B = [1, 5, 6, 9, 2]。

怎么样最小变化才能从A变成B呢？

我们列一个二维的矩阵先，如下图：

备注：蓝色为原数据，绿色为新数据，黄色的为最小变化的开销。

不难看出，这个算法的时间复杂度就是填满整张表的O(mn)。

看到这，有人会问，你的Big(O) 复杂度都是O(mn)啊，这你优化在什么地方啊。

从时间复杂度分析上看，最大数值都是O(mn)没错，但是在大数量的情况下，还是会有比较大的区别。

究竟原因在于作者的算法做了很多重复性的劳动，而利用动态规划的特征可以合理的储存状态，避免重复性的劳动。

一些细节

在查看源码的时候，查看过一个代码，

NSSet *deletedObject = ({
    NSMutableSet *set = [previousSet mutableCopy];
    [set minusSet:currentSet];
    [set copy];
});

这里非常有意思，利用了Statements and Declarations in Expressions，具体不多说了，非常巧妙，大开眼界。

The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct

啥意思呢？就是说这种符合表达式的最后一句必须是一个用分号结尾的表达式，并且这个表达式必须有返回值。而这个返回值就作为整个符号表达式的返回值。