IGListKit 学习(1) 一种高效的 diff 算法

本文目录如图：

一、背景

近来因为业务需要，学习下如何更好的展示Feed流，而 IGListKit 是 Instagram 用来重构 Feed 流的开源库，可以实现在Feed流灵活的展示各种类型的数据，其中用到的 diff 算法是用来对比两个不同的数组的，使得可以在设置新数组时，界面只对有变化的数据进行更新。这个算法能做到时间复杂度为线性增长，是比较高效的算法。
下面分别介绍 IGListKit 参考的文献（也可以在这里下载）中介绍的算法以及 IGListKit 是如何用 Objective-C 来实现这个算法的。

二、文献中的算法

我们称原文件(old file)为O，新文件(new file)为N。
把文件中每个基本单元当做一行(line)，可以是个字符，单词，句子，或者段落等
通过修改O可以得到N。
用到的数据结构有3个：一个符号表(symbol table)和两个数组(OA, NA)。

对于符号表，以每行L的文本(text)作为key，value则为一个entry，一个entry包含三个数据：

  • OC(old counter)，表示L在文件O中出现的次数；
  • NC(new counter)，表示L在文件N中出现的次数；
  • OLNO，表示L在文件O中出现的位置，只有当OC=1时才有用。

图1. 符号表的结构

O(N)文件中的每行L都有一个entry，这个entry会存储到数组OA(NA)中。
每个entry要么持有指向符号表的L对应的entry，要么记录了L在文件N(O)中的位置。(and a bit to specify which?)

这个算法有6个pass：
1、遍历文件N的每个line i
- 使得每个line i在符号表都有对应的entry；
- entry中的NC为line i的出现次数；
- 把指向这个entry的指针存储到NA[i]中。

图2. 经过步骤1之后，符号表和NA的结果

2、和1类似，遍历文件O的每个line j
- 使得每个line j在符号表都有对应的entry；
- entry中的OC为line j的出现次数；
- entry中的OLNO为line j在文件O中的行号；
- 把指向这个entry的指针存储到OA[j]中。

图3. 经过步骤2之后，符号表和OA的结果，注意如果某line在O、N都出现了，位置分别为j、i，则OA[j]、NA[i]指向同一个entry

3、找出符号表中满足“OC=NC=1”的entry（比如上图中的entry，对应N中的Line i、O中的Line j），这表示该line在文件修改前后没有变化，则把NA[i]、OA[j]分别改为该line在另一个文件O、N中的行号，即：
NA[i] = j
OA[j] = i

图4. 对于修改前后没变化的line

4、对于步骤3中找出的 NA[i] 与 OA[j] 对应（即 NA[i] = j 且 OA[j] = i）， 如果NA[i+1]、OA[j+1]也指向同一个entry，则说明该line在文件修改前后也没有变化，则使：
NA[i+1] = j+1
OA[j+1] = i+1

5、类似步骤4，检查NA[i-1]、OA[j-1]，如果都指向同一个entry，则：
NA[i-1] = j-1
OA[j-1] = i-1

（这里没理解，在步骤3找到的line没包含步骤4、5中的line么？）

6、输出结果：
- 如果NA[i]指向一个符号表的entry，说明新文件的对应的 line i 是新增的（如图5中NA的10、9）；
- 如果 NA[i] 与 OA[j] 对应（即 NA[i] = j 且 OA[j] = i），但 NA[i+1] 与 OA[j+1] 不对应（即 NA[i+1] 要么指向一个符号表的entry，要么是不等于j的另一个数字），则说明 line i 处于删除或者移动范围的边界（如图5中NA的8）

图5. 新旧文件的对应的两数组(NA, OA)的对比，根据原文的图1简化所得
（这里没理解，NA中的2、6也应该是移动范围的边界？）

三、IGListKit 中 diffable 算法的实现

算法实现是在 IGListDiff.mm 中IGListDiffing函数中：

1
static id IGListDiffing(BOOL returnIndexPaths,
2
                        NSInteger fromSection,
3
                        NSInteger toSection,
4
                        NSArray<id<IGListDiffable>> *oldArray,
5
                        NSArray<id<IGListDiffable>> *newArray,
6
                        IGListDiffOption option,
7
                        IGListExperiment experiments)

作用是：传入新旧两个数组（oldArray、newArray），用算法进行对比，得到具体差异（分别有哪些元素进行了插入(insert)、删除(delete)、移动(move)、更新(move)操作）。
其中更新操作是上面文献的算法没有提到的，因为文献中只对比文案，文案不同则代表不同的元素。

IGListDiffing 先处理两种简单的情况：

  • 新数组为空，则说明旧数组的所有元素都进行了删除操作；
    1
        // if no new objects, everything from the oldArray is deleted
    2
        // take a shortcut and just build a delete-everything result
    3
        if (newCount == 0) {
    4
            if (returnIndexPaths) {
    5
                return [[IGListIndexPathResult alloc] initWithInserts:[NSArray new]
    6
                                                              deletes:indexPathsAndPopulateMap(oldArray, fromSection, oldMap)
    7
                                                              updates:[NSArray new]
    8
                                                                moves:[NSArray new]
    9
                                                      oldIndexPathMap:oldMap
    10
                                                      newIndexPathMap:newMap];
    11
            } else {
    12
                ...
    13
                    }
    14
        }
  • 旧数组为空，则说明新数组的所有元素都进行了插入操作；
    1
        // if no old objects, everything from the newArray is inserted
    2
        // take a shortcut and just build an insert-everything result
    3
        if (oldCount == 0) {
    4
            if (returnIndexPaths) {
    5
                return [[IGListIndexPathResult alloc] initWithInserts:indexPathsAndPopulateMap(newArray, toSection, newMap)
    6
                                                              deletes:[NSArray new]
    7
                                                              updates:[NSArray new]
    8
                                                                moves:[NSArray new]
    9
                                                      oldIndexPathMap:oldMap
    10
                                                      newIndexPathMap:newMap];
    11
            } else {
    12
                ...
    13
            }
    14
        }
    接着是在新旧数组都不为空时的对比：
    假设数组的每个元素包含两个值：

图6. 本文例子中的数组元素的结构

其中key对应的值用作符号表中的key，text对应的值用作判断数据是否相等。
现在假设新旧数组分别为：

1
oldArray : (
2
    "key:1, text:UnchangedObj",
3
    "key:2, text:DeletedObj",
4
    "key:3, text:MovedObj1",
5
    "key:4, text:MovedObj2",
6
    "key:5, text:UpdateObjOld",
7
    "key:6, text:SameObj"
8
)
9
 
10
newArray : (
11
    "key:1, text:UnchangedObj",
12
    "key:7, text:InsertedObj",
13
    "key:5, text:UpdateObjNew",
14
    "key:6, text:SameObj",
15
    "key:6, text:SameObj",
16
    "key:3, text:MovedObj1",
17
    "key:4, text:MovedObj2"
18
)

然后对比过程为：
1、先定义一个unordered_map类型的 table 作为文章中的符号表

1
    // symbol table uses the old/new array diffIdentifier as the key and IGListEntry as the value
2
    // using id<NSObject> as the key provided by https://lists.gnu.org/archive/html/discuss-gnustep/2011-07/msg00019.html
3
    unordered_map<id<NSObject>, IGListEntry, IGListHashID, IGListEqualID> table;

新旧数组都用这个 table 来存储对应的 entry，entry的结构为：

1
/// 用来追踪对比过程中的数据状态.
2
struct IGListEntry {
3
    /// 数据在旧数组出现的次数
4
    NSInteger oldCounter = 0;
5
    /// 数据在新数组出现的次数
6
    NSInteger newCounter = 0;
7
    /// 数据在新数组出现的索引
8
    stack<NSInteger> oldIndexes;
9
    /// 通过isEqual:对比对应的数据，判断数据是否有更新
10
    BOOL updated = NO;
11
};

2、进行第一个pass（对应文献中的第一个pass），遍历新数组newArray，记录每个元素的出现情况

1
    // pass 1
2
    // 为新数组的每个元素创建一个entry
3
    vector<IGListRecord> newResultsArray(newCount);
4
    for (NSInteger i = 0; i < newCount; i++) {
5
        id<NSObject> key = IGListTableKey(newArray[i]);
6
        IGListEntry &entry = table[key];
7
8
            // 每出现一次，就将newCounter属性加1
9
        entry.newCounter++;
10
11
        // 往entry的oldIndexes栈push一个NSNotFound
12
        entry.oldIndexes.push(NSNotFound);
13
14
        // 让newResultsArray数组元素的entry变量指向table的一个entry
15
        newResultsArray[i].entry = &entry;
16
    }

newResultsArray 对应上文中的NA，其中的每一个元素类型是IGListRecord：

1
/// 追踪entry和索引。索引默认为NSNotFound
2
struct IGListRecord {
3
    IGListEntry *entry;
4
    mutable NSInteger index;
5
6
    IGListRecord() {
7
        entry = NULL;
8
        index = NSNotFound;
9
    }
10
};

因为上文的NA中的元素NA[i]可以指向一个entry，也可以存储另一个文件的对应数据的行号，这两个值在这里分别用entry、index来表示

在这个例子中，第一个pass结束后的结果如图7：

图7. 红色部分是在第一个pass中，对符号表中的entry的修改。NF是NSNotFound的缩写。

3、进行第二个pass（对应文献中的第二个pass），遍历旧数组oldArray，记录每个元素的出现情况

1
    // pass 2
2
    // 为新数组的每个元素创建一个entry（如果符号表里没有对的entry的话）
3
    vector<IGListRecord> oldResultsArray(oldCount);
4
    for (NSInteger i = oldCount - 1; i >= 0; i--) {
5
        id<NSObject> key = IGListTableKey(oldArray[i]);
6
        IGListEntry &entry = table[key];
7
8
            // 每出现一次，就将newCounter属性加1
9
        entry.oldCounter++;
10
11
        // 往entry的oldIndexes栈push i, 存储在旧数组的位置
12
        entry.oldIndexes.push(i);
13
14
        // 让oldResultsArray数组元素的entry变量指向table的一个entry
15
        oldResultsArray[i].entry = &entry;
16
    }

在这个例子中，第二个pass结束后的结果如图8：

图8. 红色部分是在第二个pass中，对符号表中的entry的修改。和第一个pass得到的结果相比，除了最后一个entry是新增的（对应旧数组中被delete的元素），其他entry都是用已有的。

4、进行第三个pass（对应文献中的第三个pass），处理在新旧数组都出现的元素，这里做了两件事：
（1）对比这两个元素是否相等，不等的话把对应的entry的updated设置为YES;
（2）类似文献中的把NA[i] 与 OA[j] 对应起来（即 NA[i] = j 且 OA[j] = i），这里是把该元素在新旧数组的位置分别存储到oldResultsArray、newResultsArray对应的元素的index中。

代码实现为：

1
    // pass 3
2
    // 遍历新数组，处理在新旧数组都出现的元素
3
    for (NSInteger i = 0; i < newCount; i++) {
4
// 取newResultsArray中对应的元素的entry
5
        IGListEntry *entry = newResultsArray[i].entry;
6
7
        // 取该entry的oldIndexes的栈顶数字，如果是新插入的，则该数字为NSNotFound
8
        NSCAssert(!entry->oldIndexes.empty(), @"Old indexes is empty while iterating new item %li. Should have NSNotFound", (long)i);
9
        const NSInteger originalIndex = entry->oldIndexes.top();
10
        // 用了该entry的oldIndexes的栈顶数字，将其出栈
11
        entry->oldIndexes.pop();
12
13
        // 如果originalIndex不为NSNotFound，说明和该entry对应的元素在旧数组也出现，则这个元素是在新旧数组都出现的元素
14
        // 对比这两个元素是否相等，不等的话把对应的entry的updated设置为YES;
15
        // 对比策略有两种，一是直接对比地址，二是让数组的元素实现 IGListDiffable 协议的 -isEqualToDiffableObject :方法
16
        if (originalIndex < oldCount) {
17
            const id<IGListDiffable> n = newArray[i];
18
            const id<IGListDiffable> o = oldArray[originalIndex];
19
            switch (option) {
20
                case IGListDiffPointerPersonality:
21
                    // 这里是直接对比新旧元素
22
                    if (n != o) {
23
                        entry->updated = YES;
24
                    }
25
                    break;
26
                case IGListDiffEquality:
27
                    // 如果新旧两个元素地址不同，则用 -[IGListDiffable isEqualToDiffableObject:] 方法进行对比
28
                    if (n != o && ![n isEqualToDiffableObject:o]) {
29
                        entry->updated = YES;
30
                    }
31
                    break;
32
            }
33
        }
34
35
        // 对于新旧数组都出现的元素，类似文献中的把NA[i] 与 OA[j] 对应起来（即 NA[i] = j 且 OA[j] = i）
36
        if (originalIndex != NSNotFound
37
            && entry->newCounter > 0
38
            && entry->oldCounter > 0) {
39
            newResultsArray[i].index = originalIndex;
40
            oldResultsArray[originalIndex].index = i;
41
        }
42
    }

从代码可以看到，为什么是遍历新数组而不是遍历旧数组呢？因为entry中的oldIndexes存储的就是该entry对应的元素在旧数组的位置，这样就可以在遍历新数组的时候，也能获取旧数组中对应的元素了。

在这个例子中，第三个pass结束后的结果如图9：

图9. 红色部分是在第三个pass中新增的修改。

此时可以看到：
1）对于在新旧数组（newArray、oldArray）都出现的元素，在newResultArray、oldResultArray中对应的元素的index变量都分别记录了oldArray、newArray中的位置；
2）对于在新旧数组（newArray、oldArray）都出现的元素，如果两者的key相同、text不同，则对应的entry的updated为YES，表示该元素有更新操作；
3）对于只在新（newArray）都出现的元素，在这个pass中只是把对应的entry的oldIndexes栈的栈顶数字pop了出来；
4）对于只在旧（oldArray）都出现的元素，在这个pass中没有修改对应的entry。

5、分析结果

就是将前面得到结果，转化为具体的diff信息（insert、delete、move、update）。
（1）遍历oldResultArray数组，如果某个元素的index为NSNotFound，则说明它没出现在新数组中，也就是被删除了：

1
    for (NSInteger i = 0; i < oldCount; i++) {
2
        // 记录当前位置之前有多少元素被删除了的，后面计算move数组会用到
3
        deleteOffsets[i] = runningOffset;
4
5
        const IGListRecord record = oldResultsArray[i];
6
        if (record.index == NSNotFound) {
7
                // 把在旧数组的位置添加到delete数组里
8
            addIndexToCollection(returnIndexPaths, mDeletes, fromSection, i);
9
            runningOffset++;
10
        }
11
12
        addIndexToMap(returnIndexPaths, fromSection, i, oldArray[i], oldMap);
13
    }

（2）遍历newResultArray数组，可以找到增加、移动、更新了的元素：

1
    for (NSInteger i = 0; i < newCount; i++) {
2
        insertOffsets[i] = runningOffset;
3
        const IGListRecord record = newResultsArray[i];
4
5
        const NSInteger oldIndex = record.index;
6
        // 如果index为NSNotFound，说明该元素是新增的
7
        if (record.index == NSNotFound) {
8
                // 把在新数组的位置添加到insert数组里
9
            addIndexToCollection(returnIndexPaths, mInserts, toSection, i);
10
                // 记录新增的元素的数字加1
11
            runningOffset++;
12
13
        } else {
14
            // 走到这里，说明index不为NSNotFound，则该元素是在新旧数组都出现的元素，有三种可能：不变，移动了位置，更新了值
15
            // 如果updated为YES，说明该元素有更新其值
16
            if (record.entry->updated) {
17
                    // 把在旧数组的位置添加到update数组里
18
                addIndexToCollection(returnIndexPaths, mUpdates, fromSection, oldIndex);
19
            }
20
21
            // 如果除去该位置之前的insert、delete了的元素的影响，在新旧数组位置不一样的话，则说明位置有所移动
22
            const NSInteger insertOffset = insertOffsets[i];
23
            const NSInteger deleteOffset = deleteOffsets[oldIndex];
24
            if ((oldIndex - deleteOffset + insertOffset) != i) {
25
                id move;
26
                if (returnIndexPaths) {
27
                    NSIndexPath *from = [NSIndexPath indexPathForItem:oldIndex inSection:fromSection];
28
                    NSIndexPath *to = [NSIndexPath indexPathForItem:i inSection:toSection];
29
                    move = [[IGListMoveIndexPath alloc] initWithFrom:from to:to];
30
                } else {
31
                    move = [[IGListMoveIndex alloc] initWithFrom:oldIndex to:i];
32
                }
33
                // 把记录了移动的前后位置的信息添加到move数组里
34
                [mMoves addObject:move];
35
            }
36
        }
37
38
        addIndexToMap(returnIndexPaths, toSection, i, newArray[i], newMap);
39
    }

在这个例子中，最后得到的结果是：

变化类型 位置数组 记录的位置在哪个数组
insert [1, 4] 新数组
delete [1] 旧数组
update [4] 旧数组
move [(from: 4, to: 2), (from: 5, to: 3)，(from: 2, to: 5), (from: 3, to: 6)] from是旧数组，to 是新数组

也可以表示为图10：

图10. 本文例子中新旧两个数组对比得到的具体差异

四、讨论

1、文献的算法和 IGListKit 实现的算法对比
前者会关注move的范围，后者没有；
后者会关注元素是否有update操作，前者没有（因为对比的只是文本）。

2、时间复杂度
平均情况都是O(m+n)。

3、空间复杂度
平均情况都是O(m+n)。

参考资料：

IGListKit
https://instagram.github.io/IGListKit/

A technique for isolating differences between files
https://dl.acm.org/citation.cfm?id=359467&dl=ACM&coll=DL