Fast Diff

通用、快速的 Diff 算法，支持 [m] 级别的嵌套 Diff。

时间复杂度

线性，即 O(n)

为什么？

比主流算法更快。大多数Diff算法是 O(nlogn) 或 O(n.m)。这个是线性的 O(n)。
大多数算法解决了最长公共子序列问题，该问题的实现难以理解。该算法使用 6 个简单的循环过程。
支持嵌套 Diff (如果需要)

安装

通过 Cocoapods

pod 'FastDiff'

然后在终端中执行 pod update。如果您是 Cocoapods 的新手，请查看Cocoapods 安装

通过 Swift Package Manager

在 swift Package.swift 文件中声明依赖，如下所示

dependencies: [
  ///.... other deps
  .package(url: "https://www.github.com/kandelvijaya/FastDiff", from: "1.0.0"),
]

执行更新命令 swift package update，然后执行 swift package generate-xcodeproj。

运行测试

转到源目录，然后运行

$ swift test

用法

算法 & 验证

let oldModels = ["apple", "microsoft"]
let newModels = ["apple", "microsoft", "tesla"]


/// Algorithm
let changeSet = diff(oldModels, newModels)
// [.addition("tesla", at: 2)]


/// Verification
oldModels.merged(with: changeSet) == newModels 
// true

请注意，diff 产生的变更集通常无法合并到旧集合中。变更集必须按ordered顺序排列才能成功合并。如果你想将变更集应用到UITableView或UICollectionView，这也很有用。

let chnageSet = diff(["A","B"], [“C”,"D"])
// [.delete("A",0), .delete("B",1), .add("C",0), .add(“D",1)]

let orderedChangeSet = orderedOperation(from: changeSet)
// [.delete("B",1), .delete("A",0), .add("C",0), .add("D",1)]

高级用法 & 注意事项

此算法可以准确地处理值类型 Struct。请避免使用引用类型（Class 实例）。当您必须使用类实例/对象时，您可能会获得比预期更多的更新。如果您想为您的用例解决此问题，请私信我 www.twitter.com/kandelvijaya
可以进行树形 Diff。但是，由于增加了复杂度 O(n^2)，因此该库不鼓励这样做。如果您选择进行 Diff，请使用 diffAllLevel(,)
图 Diff 的复杂性取决于图的结构。对于树，其复杂度为 O(n^2)。请注意，此变更集无法合并到原始树中。要规避此限制，请使用带有索引或 indepath 的节点，这些索引或 indepath 隐式指向图的位置。

列表视图控制器 (iOS) 中的概念和高级用法

请查看我在 @mobiconf 2018 上给出的演示幻灯片

为什么嵌套 Diff 很重要？教程/操作方法

假设您有一个组件列表，每个组件定义为

struct Component {
  let title: String 
  let footer: FooterViewModel?  // useful on top levels 
  let children: [Component]?  // nil when its a leaf. 
  let icons_sf: [String] 
}

假设我们在 UI 中使用 CollectionView 部分表示此模型。 Today 和 Tomorrow 由 SectionHeaderSupplemenratyViews 表示，相应的页脚也是如此。 internalItems 由 TaskCell 表示。用户可以使用 NavBar Button 添加新任务。

let old = [

  Component(title: "Today", footer: .init(), icons_sf: ["1.fill", "2.circle"], children: [
    Component(title: "Go to supermarket", footer: nil, icons_sf: ["sf.cucumber"], children: nil), 
    Component(title: "Make breakfast", footer: nil, icons_sf: ["sf.avocado"], children: nil)
  ]), 

  Component(title: "Tomorrow", footer: .init(), icons_sf: ["1.fill", "2.circle"], children: [
    Component(title: "Work on FastDiff", footer: nil, icons_sf: ["sf.chopsticks"], children: nil), 
    Component(title: "SwiftUI TODO list for macos", footer: nil, icons_sf: ["sf.pen"], children: nil)
  ])

]

假设用户向 Todays 条目添加了一个新任务项，因此新模型变为

let new = [

  Component(title: "Today", footer: .init(), icons_sf: ["1.fill", "2.circle"], children: [
    Component(title: "Go to supermarket", footer: nil, icons_sf: ["sf.cucumber"], children: nil), 
    Component(title: "Make breakfast", footer: nil, icons_sf: ["sf.avocado"], children: nil), 

    /// newly added
    Component(title: "Buy PS5 from amazon", footer: nil, icons_sf: ["sf.play"], children: nil), 
  ]), 

  Component(title: "Tomorrow", footer: .init(), icons_sf: ["1.fill", "2.circle"], children: [
    Component(title: "Work on FastDiff", footer: nil, icons_sf: ["sf.chopsticks"], children: nil), 
    Component(title: "SwiftUI TODO list for macos", footer: nil, icons_sf: ["sf.pen"], children: nil)
  ])

]

我们假设 Component: Diffable

当您执行 `diff(old, new)` 时，您有什么期望？

可能有 2 种潜在的解决方案

[.delete(item: old.0, at: 0), insert(item: new.0, at 0)]
- diffable 一致性可能如下所示
```
extension Component: Diffable {}
```
- UI 端：您将删除整个第 1 部分，构造新部分并插入它。当我们知道 2 个内部项目（单元格）在旧的和新的之间没有更改时，这会丢弃整个部分。
- 我们浪费了一些资源。
- 我们将不会获得精确更改的插入动画。
[.update(at: 0, old: old.0, new: new.0)]
- diffable 一致性将如下所示
```
extension Component: Diffable, Equatable {
  
  var diffHash: Int {
    /// excludes innerDiffItems 
    return title.hashValue ^ footer.hashValue ^ icons_sf.hashValue
  }

  var innerDiffableItems: [Component] {
    return children ?? []
  }

}
```
  - UI 端：当在 section 级别收到 .update(,,,) 时，我们可以对内部项目执行 diff，如下所示 diff(old.innerDiffableItems, new.innerDiffableItems) 以接收单元格级别的确切更改，然后可以将其修补到 section.performBatchUpdate
  - 新任务添加已动画化，这是 UI 上唯一更改的内容
  - 有效率地修补更改的内容。

作者

@kandelvijaya (https://twitter.com/kandelvijaya)

许可证

该项目已获得 MIT 许可证的许可 - 有关详细信息，请参阅LICENSE.md 文件

鸣谢

灵感来自 Paul Heckel 的论文和算法