Diff.swift

此库生成任意两个 Collection（和字符串）之间的差异。它使用一个快速算法 (O((N+M)*D))。

文档

文档在这里可用here

特点

• Diff.swift 支持三种类型的操作
  • 插入
  • 删除
  • 移动（使用 ExtendedDiff）

• 对 Patch 的任意排序
• 为 UITableView 和 UICollectionView 提供的 utility（如果您只想使用这些，请跳转到例子中)）
• ⚡️ 快速
• 支持 NestedDiff 包含多个集合的集合比较

我为什么需要它？

差异不仅仅是轻松执行 UITableView 动画。

无论你在哪里有代码促进了从你的模型到UI的 added/removed/moved 回调，使用 diffing 库都是好的。你得到的是清晰的分离和更声明式的方法。模型只是执行状态转换，UI代码根据 diff 输出执行相应的 UI 操作。

差异与补丁（排序）比较

让我们考虑一个简单的例子：将字符串 "a" 转换为 "b" 的补丁。

1. 在索引 0 处删除项目（我们得到 ""）
2. 在索引 0 处插入 b（我们得到 "b"）

如果我们想以不同的顺序执行这些操作，简单的步骤重排不起作用。

1. 在索引 0 处插入 b（我们得到 "ba"）
2. 在索引 0 处删除项目（我们得到 "a"）

… ooooops

我们需要调整插入和删除，以便得到这个

1. 在索引 1 处插入 b（我们得到 "ab"）
2. 在索引 0 处删除项目（我们得到 "b"）

解决方案

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

• 差异
  • 一串删除、插入和移动（如果使用 ExtendedDiff），其中删除指向源中要删除的项目位置，而插入指向输出中的项目。 Diff.swift 仅生成一个 Diff。
• 补丁
  • 将第二个序列从第一个序列中获得的步骤的有序序列。它基于 Diff，但可以进行任意排序。

实践中的排序

在实践中，这意味着将字符串 "1234" 转换为 "1" 的差 "D(1)D(2)D(3)"，默认补丁为 "D(1)D(1)D(1)"。然而，如果我们决定首先排序以删除和较大的索引，我们得到的补丁为： "D(3)D(2)D(1)"。

如何使用

UITableView/UICollectionView

// It will automatically animate deletions, insertions, and moves
tableView.animateRowChanges(
            oldData: old,
            newData: new)

collectionView.animateItemChanges(
    oldData: old,
    newData: new,
    completion: {_ in}) 

// Works with sections, too

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

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

请参考示例来查看工作示例。

使用补丁和Diff

当你想得到将一个序列转换为另一个序列的步骤时（例如，你想根据模型的变化来动画 UI）

let from: T
let to: T

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

// Patch + moves
// Returns [ExtendedPatch<T.Iterator.Element>]
let patch = extendedPatch(
                from: from,
                to: to
            )

当你需要更多的排序控制时

let insertionsFirst = { fst, snd -> 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 [Patch] with insertions preceeding deletions
let patch = patch(
                from: from,
                to: to,
                sort: insertionsFirst
            )

更高级 - 你想首先计算 diff 然后生成补丁。在某些情况下，这是一个很好的性能改进。生成排序补丁需要 O(D^2) 的时间。默认顺序的生成时间为 O(D)。 D 是 diff 的长度。

// Generate diff first
let diff = from.diff(to)
let patch = diff.patch(from: from, to: to)

性能说明

这个库速度快。其他大多数库使用一个简单的 O(n*m) 算法，它分配一个二维数组和遍历所有元素。它消耗 大量 内存。在基准测试中，它与前者相比是一个数量级的差异。

源代码可以在这里找到。测量的结果是在iPhone 6上运行10次跑的平均diff时间（秒）。

此算法对于具有 小型 差异的集合效果极佳。我的意思是，即使是对于大的差异，它也比简单的算法要好。然而，如果您需要良好的性能并且输入之间存在较大的差异，请考虑另一种差异算法。查看 Hunt & Szymanski 的作品和/或 Hirschberg 的作品。

安装

Cocoapods

// podfile
pod 'Diff'

联系

如果您有任何问题，您可以在Twitter上找到我。

杂项

如果您想了解它是如何工作的，请从 Graph.playground 开始。