Differ

Differ 生成 Collection 实例之间的差异（这包括字符串！）。

它使用一个 快速算法 (O((N+M)*D)) 来实现这一点。

特性

• ⚡️ 它非常快
• Differ 支持三种类型的操作
  • 插入
  • 删除
  • 移动（在使用 ExtendedDiff 时）
• 任意排序补丁（Patch）
• 更新 UITableView 和 UICollectionView 的实用工具
• 计算包含集合的集合之间的差异（使用 NestedDiff）

为什么我需要它？

计算差异比简单地实现 UITableView 动画要复杂得多！

无论在哪里，你都有将 added/removed/moved 回调从你的模型传递到用户界面的代码，你应该考虑使用一个可以计算差异的库。通常，动画一小批更改会比重新加载所有数据要快，并提供更响应的体验。

计算并采取差异行动应该也有助于你在数据和用户界面之间做出明显的区分，并可能提供一个更声明式的方法：你的模型执行状态转换，然后你的 UI 代码基于计算出的差异执行适当的操作。

差异、补丁和排序

让我们考虑一个使用补丁将字符串 "a" 转换为 "b" 的简单例子。以下步骤描述了在这些状态之间移动所需的补丁

如果我们想以不同的顺序执行这些操作，简单地重新排序现有的补丁就不会起作用

...哦！

要达到正确的结果，我们需要调整插入和删除的顺序，以便我们得到以下内容

解决方案

为了减轻这个问题，有两种类型的输出

• 差异
  • 一系列删除、插入和移动操作（如果使用 ExtendedDiff），其中删除指向源中要删除的项目位置，插入指向输出中的项目。Differ 仅生成一个 Diff。
• 补丁
  • 一系列用于将源集合转换为第二个集合的步骤，这是一个基于 Diff 的有序步骤集合。它可以任意排序。

实际排序

在实践中，这意味着将字符串 1234 转换为 1 的差异可以描述如下一系列步骤

DELETE 1
DELETE 2
DELETE 3

描述相同更改的补丁会是这样的

DELETE 1
DELETE 1
DELETE 1

然而，如果我们决定排序它，以便先处理删除和更高索引，我们就得到以下补丁

DELETE 3
DELETE 2
DELETE 1

使用方法

UITableView/UICollectionView

// The following will automatically animate deletions, insertions, and moves:

tableView.animateRowChanges(oldData: old, newData: new)

collectionView.animateItemChanges(oldData: old, newData: new)

// It can work with sections, too!

tableView.animateRowAndSectionChanges(oldData: old, newData: new)

collectionView.animateItemAndSectionChanges(oldData: old, newData: new)

请参阅附带的示例，以了解如何使用。

使用补丁和差异

当您要确定将一个集合转换为另一个集合的步骤时（例如，您想根据模型的变化来动画化用户界面），您可以按照以下步骤操作

let from: T
let to: T

// patch() only includes insertions and deletions
let patch: [Patch<T.Iterator.Element>] = patch(from: from, to: to)

// extendedPatch() includes insertions, deletions and moves
let patch: [ExtendedPatch<T.Iterator.Element>] = extendedPatch(from: from, to: to)

当您需要更多控制排序时，您可以使用以下方法

let insertionsFirst = { element1, element2 -> Bool in
    switch (element1, element2) {
    case (.insert(let at1), .insert(let at2)):
        return at1 < at2
    case (.insert, .delete):
        return true
    case (.delete, .insert):
        return false
    case (.delete(let at1), .delete(let at2)):
        return at1 < at2
    default: fatalError() // Unreachable
    }
}

// Results in a list of patches with insertions preceding deletions
let patch = patch(from: from, to: to, sort: insertionsFirst)

高级示例：您想首先计算差异，然后生成补丁。在某些情况下，这可以提高性能。

D是差异的长度

• 生成排序好的补丁需要O(D^2)的时间。
• 默认排序需要O(D)的时间来生成。

// Generate the difference first
let diff = from.diff(to)

// Now generate the list of patches utilising the diff we've just calculated
let patch = diff.patch(from: from, to: to)

如果您想了解更多关于此库的工作原理，请从Graph.playground开始。

性能说明

Differ非常快。许多其他Swift差异库使用简单的O(n*m)算法，该算法分配一个二维数组然后遍历每个元素。这会占用很多内存。

在以下基准测试中，您应该会在两种算法的计算时间上看到一个数量级的差异。

每次测量都是在iPhone 6上重复10次计算差异化所需平均时间的秒数。

您可以通过检查Diff性能套件来运行这些基准测试。

以上几点说明，Diff算法对于元素之间差异较小的集合工作得最好。然而，即使对于差异较大的情况，此库的速度也可能比使用简单O(n*m)算法的库快。如果您需要在集合之间存在较大的差异时获得更好的性能，请考虑实现更合适的方法，例如Hunt & Szymanski算法和/或Hirschberg算法。

要求

Diff需要Swift 4 / Xcode 9或更高版本编译

安装

您可以使用Carthage、CocoaPods、Swift Package Manager或将Differ作为Xcode子项目添加到项目中。

Carthage

github "tonyarnold/Differ"

CocoaPods

pod 'Differ'

致谢

Differ是Wojtek Czekalski的 Diff.swift的修改分支——Wojtek应得到原始实现的全部 Credit，我只是现在的维护者。

请在此仓库中在此分支中提交问题，而不是在Wojtek的原始仓库中。