此文章为本人翻译的译文，版权为原作者所有。
英文原文：A better way to update UICollectionView data in Swift with diff framework

Familiar friends

很难想象一款iOS的APP不使用UITableView和UICollectionView，大多数时候我们从服务器，缓存和过滤器中获取数据然后在列表中展示，当数据发生改变的时候更新列表。

这个时候你就你就会想到你最喜欢的方法reloadData，用reloadData整个列表都会被刷新。当你想用最快速的方式刷新列表这是没有问题的。但CPU会重新计算UITableView的size，这会影响性能。更进一步，如果这些改变应该被凸显出来，并且你想让用户感知到发生了什么，手动插入或删除某一行是更好的选择。

如果你是做安卓开发，或许知道通过使用DiffUtil而不是notifyDataSetChanged来计算变化，以便更容易地更新RecyclerView。不幸的是iOS并不提供这样的接口，但是我们可以学习怎么去做。

这里会用UICollectionView举例，但UITableView实践的方式是一样的。

Drag and Drop

想象一下App需要实现用户可以通过拖拽移动UICollectionView的功能，你可以看看DragAndDrop这个demo，它是用iOS 11中的 drag and drop API接口实现的。
在调用UICollectionView的更新方法之前，必须确保数据更改了。 然后调用deleteItems和insertItems来反映数据变化。 UICollectionView会执行一个很棒的的动画。

0_kCCB1lwaDLCrqTy3.png

func collectionView(_ collectionView: UICollectionView, performDropWith coordinator: UICollectionViewDropCoordinator) {
  let destinationIndexPath = coordinator.destinationIndexPath
  let sourceIndexPath = coordinator.items.last?.dragItem.localObject as! IndexPath
  // remove
  sourceItems.remove(at: sourceIndexPath.item)
  sourceCollectionView.deleteItems(at: [sourceIndexPath])
  // insert
  destinationItems.insert(draggedItem, at: destinationIndexPath.item)
  destinationCollectionView.insertItems(at: [destinationIndexPath])
}

这是一个简单的例子，只需从集合中删除或添加1个item。但在实际项目中，数据要复杂得多，变化并不是那么微不足道。如果从服务器拿到大量的items需要插入和删除，你需要计算正确的IndexPath来调用，这不是一件容易的事。大多数时候你会遇到以下崩溃：

NSInternalInconsistencyException

Terminating app due to uncaught exception ‘NSInternalInconsistencyException’,
reason: ‘Invalid update: invalid number of items in section 0.
The number of items contained in an existing section after the update (213)
must be equal to the number of items contained in that section before
the update (154), plus or minus the number of items inserted or
deleted from that section (40 inserted, 0 deleted) and plus
or minus the number of items moved into or out of
that section (0 moved in, 0 moved out).’

依我的经验来看，这个是随机发生（实际是因为数据和IndexPath不匹配）。

Game of IndexPath

让我们通过一些例子来梳理对IndexPath的了解。通过6个item的数据集，我们执行一些更新操作并找出IndexPath应该是什么。

tems = ["a", "b", "c", "d", "e", "f"]
为了更好的理解，请查看这个demoCollectionUpdateExample

1_aqssz9GRKOt2O9OEQDRPrg (1).png

1. Insert 3 items at the end

items.append(contentsOf: ["g", "h", "i"])
// a, b, c, d, e, f, g, h, i
let indexPaths = Array(6…8).map { IndexPath(item: $0, section: 0) }
collectionView.insertItems(at: indexPaths)

2. Delete 3 items at the end

items.removeLast()
items.removeLast()
items.removeLast()
// a, b, c
let indexPaths = Array(3…5).map { IndexPath(item: $0, section: 0) }
collectionView.deleteItems(at: indexPaths)

3. Update item at index 2

items[2] = “👻”
// a, b, 👻, d, e, f
let indexPath = IndexPath(item: 2, section: 0)
collectionView.reloadItems(at: [indexPath])

4. Move item “c” to the end

items.remove(at: 2)
items.append("c")
// a, b, d, e, f, c
collectionView.moveItem(
  at: IndexPath(item: 2, section: 0),
  to: IndexPath(item: 5, section :0)
)

5. Delete 3 items at the beginning, then insert 3 items at the end

对于多个不同的操作，我们应该使用performBatchUpdates

如果要在一个动画操作中对集合视图进行多次更改，则可以使用此方法，而不是在几个单独的动画中。你可以使用此方法插入，删除，重新加载或移动单元格，或使用它来更改与一个或多个单元格关联的布局参数

items.removeFirst()
items.removeFirst()
items.removeFirst()
items.append(contentsOf: ["g", "h", "i"])
// d, e, f, g, h, i
collectionView.performBatchUpdates({
  let deleteIndexPaths = Array(0…2).map { IndexPath(item: $0, section: 0) }
  collectionView.deleteItems(at: deleteIndexPaths)
  let insertIndexPaths = Array(3…5).map { IndexPath(item: $0, section: 0) }
  collectionView.insertItems(at: insertIndexPaths)
}, completion: nil)

6. Insert 3 items at the end, then delete 3 items at the beginning

items.append(contentsOf: ["g", "h", "i"])
items.removeFirst()
items.removeFirst()
items.removeFirst()
// d, e, f, g, h, i
collectionView.performBatchUpdates({
  let insertIndexPaths = Array(6…8).map { IndexPath(item: $0, section: 0) }
  collectionView.insertItems(at: insertIndexPaths)
  let deleteIndexPaths = Array(0…2).map { IndexPath(item: $0, section: 0) }
  collectionView.deleteItems(at: deleteIndexPaths)
}, completion: nil)

如果你run第6个例子，将会crash

Terminating app due to uncaught exception
‘NSInternalInconsistencyException’,
reason: ‘attempt to insert item 6 into section 0,
but there are only 6 items in section 0 after the update’

performBatchUpdates

这是由performBatchUpdates的工作方式引起的。 看看这里documentation:

Deletes are processed before inserts in batch operations. This means the indexes for the deletions are processed relative to the indexes of the collection view’s state before the batch operation, and the indexes for the insertions are processed relative to the indexes of the state after all the deletions in the batch operation.

无论我们如何调用insert或delete，performBatchUpdates总是先执行删除操作。因此，如果首先发生删除，我们需要使用正确的IndexPath调用deleteItems和insertItems。

items.append(contentsOf: ["g", "h", "i"])
items.removeFirst()
items.removeFirst()
items.removeFirst()
// d, e, f, g, h, i
collectionView.performBatchUpdates({
  let deleteIndexPaths = Array(0…2).map { IndexPath(item: $0, section: 0) }
  collectionView.deleteItems(at: deleteIndexPaths)
  let insertIndexPaths = Array(3…5).map { IndexPath(item: $0, section: 0) }
  collectionView.insertItems(at: insertIndexPaths)
}, completion: nil)

Operation

UICollectionView上有许多操作，还有一些操作可以更新整个section。看看Ordering of Operations and Index

insertItems(at indexPaths: [IndexPath])
deleteItems(at indexPaths: [IndexPath])
reloadItems(at indexPaths: [IndexPath])
moveItem(at indexPath: IndexPath, to newIndexPath: IndexPath)

performBatchUpdates(_ updates, completion)

insertSections(_ sections: IndexSet)
deleteSections(_ sections: IndexSet)
reloadSections(_ sections: IndexSet)
moveSection(_ section: Int, toSection newSection: Int)

0_kBveuRgnlHYlk1YZ.jpeg

Edit distance

手动执行这些计算非常繁琐且容易出错。我们可以使用一些算法构建自己的抽象。 最原始的的算法是Wagner-Fischer，它使用Dynamic_programming（动态规划）来查找两个字符串之间的编辑路径。
编辑路径表示从一个字符串更改为另一个字符串所需的步骤集合。字符串只是一个字符集合，因此我们可以概括这个概念，使其适用于任何项目集合。 我们要求项目符合Hashable，而不是比较字符。

"kit" to "kat"

我们怎样才能将"kit"这个词改为"kat"？ 我们需要执行哪些操作？ 你可以告诉"只需将字母i更改为a"，但这个简单的示例可帮助您理解算法，让我们开始吧。

0_YB9HNWh-W_RSSy49.jpeg

Deletions

如果我们将"kit"修改为字符串""，需要3个删除操作

0_CWTVVW4_OriCrwlA.png

"kit" -> "" 👉 3次删除操作

"ki" -> "" 👉 2次删除操作

"k" -> "" 👉 1次删除操作

Insertions

如果我们将空字符串""变为"kit"，需要3次插入操作

0_XfqiIXOZ4eSr_2OQ.png

"" -> "k" 👉 1次插入操作

"" -> "ka" 👉 2次插入操作

"" -> "kat" 👉 3次插入操作

If equal, take value from the top left

你可以将算法视为从源字符串 -> 空字符串 -> 目标字符串。我们尝试找到要更新的最小步骤。水平移动意味着插入，垂直意味着删除，对角意味着替换。

这样我们就可以构建我们的矩阵，逐行逐列地迭代。首先，源集合中的字母"k"与目标集合中的字母"k"相同，我们只需从左上角取值，即0替换

0_xrFKcGJkr38NKt0C.png

If not equal

我们继续看目标结合上的下一个字母。 这里"k"和"a"不一样。 我们从左，上，左上取最小值。 然后增加一个

0_d9B7IDqkP-tjyX4_.png

这里我们从左边取值，这是水平的，所以我们增加1次插入。

"k" to "kat" 👉 2 insertions

继续，"t"和"k"不一样，所以我们从左边水平取值。 在这里你可以看到它某种意义上是说得通的，从"k"到"kat"，我们需要2个插入，即插入字母"a"和"t"。

0_ZRyek7fZgFF2na8d.png

The bottom right value

一行一行的继续，直到我们达到右下角的值，这样就可以得到编辑路径。 这里1个替换意味着我们需要执行1次替换以从"kit"变为"kat"，这是用"a"更新"i"。

1_KfUkGg_KZWGwDRAhxAIaFg.png

您可以很容易地看到需要更新索引1，但是我们怎么知道它是索引1🤔

DeepDiff

这个算法显示了两个字符串之间的变化，但由于字符串只是字符的集合。 我们可以概括这个概念，使其适用于任何item集合。

1_w5n7s2u_eXRN_F9DdwIdIA.gif

DeepDiff的实现在GitHub上。 以下是它的使用方法。 假设一个old的和new的数组，它计算转换所需的更改。 更改包括：更改类型(insert, delete, replace, move)和更改的index。

let old = Array("abc")
let new = Array("bcd")
let changes = diff(old: old, new: new)
// Delete "a" at index 0
// Insert "d" at index 2

代码是解释的最好方式。但在接下来的部分中，我将概述库中的一些技术要点，以便你轻松遵循。 你可以看看here

Complexity

我们遍历矩阵，其中m和n分别是源和目标集合的长度。 所以我们可以看到这个算法的复杂度是O(mn)。

此外，性能在很大程度上取决于集合的大小以及项目的复杂程度。 您想要执行的更复杂和更深的Equatable会极大地影响性能。

如果你查看wiki page ，会提示我们可以采取一些措施来提高性能。

“We can adapt the algorithm to use less space, O(m) instead of O(mn), since it only requires that the previous row and current row be stored at any one time.”

看到我们一次只操作一行，存储整个矩阵是低效的，而我们可以只使用2个数组来计算，这也减少了内存占用。

Change

由于每种change都是互斥的，因此它们非常适合用作枚举

public enum Change<T> {
  case insert(Insert<T>)
  case delete(Delete<T>)
  case replace(Replace<T>)
  case move(Move<T>)
}

• insert：item被插入到一个index下
• delete：item从一个index下移除
• replace：一个index下的item被另一个替换
• move：一个item从一个index下移到另一个index下

如上所述，我们只需要一次跟踪2行即可运行。每行的slots都是一组改变。这里diff是一个泛型函数，它接受Hashable类型的任何集合，包括字符串。

public func diff<T: Hashable>(old: Array<T>, new: Array<T>) -> [Change<T>] {
  let previousRow = Row<T>()
  previousRow.seed(with: new)
  let currentRow = Row<T>()
  …
}

我喜欢分离关注点，所以每一行都应该自己管理状态。首先声明一个持有slots数组的Row对象

class Row<T> {
  /// Each slot is a collection of Change
  var slots: [[Change<T>]] = []
}

回想一下我们逐行逐列的算法。所以我们使用2个循环

old.enumerated().forEach { indexInOld, oldItem in
  new.enumerated().forEach { index, item in
    
  }
}

我们的工作只是比较旧数组和新数组中的items，并正确更新Row对象中的slots。

Hashable vs Equatable

我们需要巧妙地进行equation check，因为当对象很复杂时，Equatable函数可能需要时间。我们知道Hashable符合Equatable，并且2个相同的对象具有相同的哈希值。 因此，如果它们没有相同的哈希值，则它们不是等同的。 反转并不能保证，但这足以减少对Equatable函数的调用次数。

private func isEqual<T: Hashable>(oldItem: T, newItem: T) -> Bool {
  // Same items must have same hashValue
  if oldItem.hashValue != newItem.hashValue {
    return false
  } else {
    // Different hashValue does not always mean different items
    return oldItem == newItem
  }
}

算法还有其他一些细节，但你应该看一下代码，它会告诉你更多。

How about the Move

到目前为止，你已经注意到我们刚刚更新了插入，删除和替换的步骤。 那移动呢？事实证明这并不困难。移动只是插入相同item后的删除。 你可以看看MoveReducer，它的实现效率不高，但至少它会给你一些提示。

Inferring IndexPath for UICollectionView

使用DeepDiff返回的更改数组，我们可以推断出要提供给UICollectionView以执行更新的所需IndexPath集合。

从Change到IndexPath的转换几乎是不言自明的。 您可以查看UICollectionViewextension。

有一点需要注意，否则你会得到熟悉的NSInternalInconsistencyException。那就是在performBatchUpdates之外调用reloadItems。 这是因为此算法返回的Replace步骤包含更新集合后的状态的IndexPath，但UICollectionView期望它们在该状态之前。

除此之外，它非常简单。你可以通过这个例子对这些changes的速度和有用信息感到惊讶。

Where to go from here

完成这个指南后，你将了解如何通过手动计算IndexPath手动更新到UICollectionView。在遇到异常后，你知道这个库给你提供了多少帮助。你还了解算法以及如何用Swift实现。你还知道如何使用Hashable和Equatable。

DeepDiff的当前版本现在使用Heckel算法，该算法以线性时间运行并且执行速度更快。 测试结果如下图

0_6lsIlvbAErwQNbXn.png

IGListKit也实现了Heckel算法，但是用Objective C++中并对其进行了优化。在下一篇文章中，我将介绍Heckel算法以及如何在Swift中实现它，以及如何为这些diff算法编写单元测试。 敬请关注！

与此同时，如果你觉得有冒险精神，这里有一些据说非常高效的其他算法：

• An O(ND) Difference Algorithm and Its Variations
• An O(NP) Sequence Comparison Algorithm

最后个人补充

感兴趣的也可以看看这个项目DifferenceKit，也是我们公司项目中在使用的，据它gitlab上个提供的数据显示，它是以下几个项目中各方面性能最好的

• DifferenceKit
• RxDataSources
• FlexibleDiff
• IGListKit
• ListDiff
• DeepDiff
• Differ
• Dwifft