一个快速且灵活的用于 Swift 集合的差异算法框架。
该算法基于 Paul Heckel 的算法进行了优化。

用❤️由 Ryo Aoyama 和 贡献者 制作

特性

💡最快 O(n) diffing algorithm optimized for Swift collection

💡为 UIKit、AppKit 以及 Texture 中的列表 UI 批量更新计算差异

💡支持包含重复项的线性分区集合

💡支持动画 UI 批量更新中的所有类型差异

算法

这是一个为 Carbon 开发的 diffing 算法，可以单独使用。
该算法基于 Paul Heckel 的算法进行了优化。
参见他于 1978 年发布的论文 "A technique for isolating differences between files"。
它允许以线性时间 O(n) 计算所有类型的差异。
RxDataSources 和 IGListKit 也是基于他的算法实现的。

然而，在 UITableView、UICollectionView 等的 performBatchUpdates 中，当同时应用组合的变化时会导致崩溃。
为了解决这个问题，DifferenceKit 采用了一种方法，将差异集合分成最小的可以不崩溃地进行批量更新的阶段。

实现代码见 这里。

开始使用

• API 文档
• 示例应用
• 基准测试
• 实验场

基本用法

要取差的元素类型必须符合 Differentiable 协议。
differenceIdentifier 的类型是泛型关联类型

struct User: Differentiable {
    let id: Int
    let name: String

    var differenceIdentifier: Int {
        return id
    }

    func isContentEqual(to source: User) -> Bool {
        return name == source.name
    }
}

在上述定义的情况下，id 可唯一标识元素，并可以通过比较源和目标元素中 name 的相等性来了解用户是否更新。

对于符合 Equatable 或 Hashable 的类型，已有 Differentiable 的默认实现：

// If `Self` conforming to `Hashable`.
var differenceIdentifier: Self {
    return self
}

// If `Self` conforming to `Equatable`.
func isContentEqual(to source: Self) -> Bool {
    return self == source
}

因此，您可以很简单地

extension String: Differentiable {}

通过从符合 Differentiable 的两个元素集合创建 StagedChangeset 来计算差分。

let source = [
    User(id: 0, name: "Vincent"),
    User(id: 1, name: "Jules")
]
let target = [
    User(id: 1, name: "Jules"),
    User(id: 0, name: "Vincent"),
    User(id: 2, name: "Butch")
]

let changeset = StagedChangeset(source: source, target: target)

如果您想将多个符合 Differentiable 的类型包含在集合中，请使用 AnyDifferentiable。

let source = [
    AnyDifferentiable("A"),
    AnyDifferentiable(User(id: 0, name: "Vincent"))
]

在分节集合的情况下，节本身必须有一个唯一的标识符并能比较是否有更新。
因此，每个节都必须符合 DifferentiableSection 协议，但在大多数情况下，您可以使用符合其的一般类型 ArraySection。
ArraySection 需要一个符合 Differentiable 的模型从其他部分进行比较。

enum Model: Differentiable {
    case a, b, c
}

let source: [ArraySection<Model, String>] = [
    ArraySection(model: .a, elements: ["A", "B"]),
    ArraySection(model: .b, elements: ["C"])
]
let target: [ArraySection<Model, String>] = [
    ArraySection(model: .c, elements: ["D", "E"]),
    ArraySection(model: .a, elements: ["A"]),
    ArraySection(model: .b, elements: ["B", "C"])
]

let changeset = StagedChangeset(source: source, target: target)

您可以使用创建的 StagedChangeset 执行 UITableView 和 UICollectionView 的批量更新。

⚠️ 请别忘了 以同步的方式通过 setData 闭包更新数据源引用的数据。差分是分阶段应用的，如果不这样做，则肯定会崩溃

tableView.reload(using: changeset, with: .fade) { data in
    dataSource.data = data
}

使用过多的差分进行批量更新可能会对性能产生不利影响。
如果通过 interrupt 闭包返回 true，则回退到 reloadData

collectionView.reload(using: changeset, interrupt: { $0.changeCount > 100 }) { data in
    dataSource.data = data
}

[查看更多用法]

与其他框架的比较

在性能和功能方面尽可能与其他流行且优秀的框架进行了公平的比较。
这并不决定框架的优劣。
我知道每个框架都有自己的优点。
以下为比较的框架及其版本。

• DifferenceKit - master
• RxDataSources (Differentiator) - 4.0.1
• FlexibleDiff - 0.0.8
• IGListKit - 3.4.0
• DeepDiff - 2.2.0
• Differ (Diff.swift) - 1.4.3
• Dwifft - 0.9
• Swift.CollectionDifference - Swift 5.1

性能比较

基准项目在这里：这里.
性能是通过使用 Xcode11.1 和 Swift 5.1 编译的代码，并带有 -O 优化on 在 iPhone11 Pro 模拟器 上运行来衡量的。
使用 Foundation.UUID 作为集合的元素。

从5,000个元素到1,000个删除、1,000个插入和200个随机排列

从100,000个元素到10,000个删除、10,000个插入和2,000个随机排列

功能比较

- 算法

* Heckel算法
* Myers算法

- 支持的集合

* 线性意味着一维集合
* 分段意味着二维集合

- 支持元素差异

- 支持分段差异

需求

• Swift 4.2+
• iOS 9.0+
• tvOS 9.0+
• OS X 10.9+
• watchOS 2.0+ (仅算法)

安装

CocoaPods

仅使用算法而不使用UI扩展，请在您的Podfile中添加以下内容：

pod 'DifferenceKit/Core'

iOS / tvOS

要使用包含UIKit扩展的DifferenceKit，请在您的Podfile中添加以下内容：

pod 'DifferenceKit'

或者

pod 'DifferenceKit/UIKitExtension'

macOS

要使用包含AppKit扩展的DifferenceKit，请在您的Podfile中添加以下内容：

pod 'DifferenceKit/AppKitExtension'

watchOS

watchOS没有UI扩展。
仅使用算法而不使用UI扩展，请在您的Podfile中添加以下内容：

pod 'DifferenceKit/Core'

Carthage

请在您的Cartfile中添加以下内容：

github "ra1028/DifferenceKit"

Swift Package Manager for Apple platforms

在Xcode菜单中选择文件 > Swift Packages > 添加包依赖项，并通过GUI输入仓库URL。

Repository: https://github.com/ra1028/DifferenceKit

Swift Package Manager

将以下内容添加到您的 Package.swift 的依赖中：

.package(url: "https://github.com/ra1028/DifferenceKit.git", from: "version")

贡献

欢迎提交拉取请求、错误报告和功能请求🚀
请参阅 CONTRIBUTING 文件，了解如何为 DifferenceKit 贡献。

致谢

参考文献

DifferenceKit 开发时参考了以下优秀的材料和框架。

• 文件之间差异隔离技术（作者 Paul Heckel）
• DifferenceAlgorithmComparison（作者 @horita-yuya）

使用 DifferenceKit 的 OSS

列出使用此库的精彩 OSS 列表。它们也有助于了解如何使用 DifferenceKit。

• Carbon（作者 @ra1028）
• DiffableDataSources（作者 @ra1028）
• Rocket.Chat.iOS（作者 RocketChat）
• wire-ios（作者 Wire Swiss GmbH）
• ReactiveLists（作者 PlanGrid）
• ReduxMovieDB（作者 @cardoso）
• TetrisDiffingCompetition（由 @skagedal 开发）

其他差分库

我尊重和 ️❤️所有参与差分的库。

• RxDataSources（由 @kzaher，RxSwift Community 开发）
• IGListKit（由 Instagram 开发）
• FlexibleDiff（由 @andersio，RACCommunity 开发）
• DeepDiff（由 @onmyway133 开发）
• Differ（由 @tonyarnold 开发）
• Dwifft（由 @jflinter 开发）
• Changeset（由 @osteslag 开发）

许可证

differencekit 在以下 Apache 2.0 许可证下发布。