E327c5b16428474e8efc1f82d6bd35f2
Diff 算法在 iOS 中的应用(一)

在计算机领域中,Diff 是一个很重要的概念,被广泛的运用于各式各样的场景。比如说,React 利用 Diff 大大减少了刷新导致的性能问题;Git 借助 Diff 算法实现了版本之间的差异化对比;腾讯 Tinker 热修复借助 Diff 算法生成 patch 包等等。

这系列文章,我会以 UICollectionView 为例,结合 IGListKit 、 DeepDiff 等几个优秀开源库,聊一下 Diff 算法在 iOS 中的一些应用和实现原理。

UICollectionView 中的局部刷新

UICollectionView 提供了 insert、delete、reload、move 四个局部刷新的 API,具体如下:

  • 插入(insert)
var items = ["iOS","Weekly","Damonwong"]
items.append(contentsOf: ["Diff","UICollectionView"])
let indexPaths = Array(3...4).map { IndexPath(item: $0, section: 0) }
collectionView.insertItems(at: indexPaths)
  • 删除(delete)
var items = ["iOS","Weekly","Damonwong","Diff","UICollectionView"]
items.removeLast()
items.removeLast()
let indexPaths = Array(3...4).map { IndexPath(item: $0, section: 0) }
collectionView.deleteItems(at: indexPaths)
  • 更新(reload)
var items = ["iOS","Weekly","Damonwong"]
items[2] = "OldDriver"
let indexPath = IndexPath(item: 2, section: 0)
collectionView.reloadItems(at: indexPaths)
  • 移动(move)
var items = ["iOS","Weekly","Damonwong"]
items.remove(at: 1)
items.append("Weekly")
collectionView.moveItem(
  at: IndexPath(item: 1, section: 0),
  to: IndexPath(item: 2, section :0)
)

在实际开发过程中,通常需要通过上面四个基本操作相互组合才能达到效果。但是,我认为苹果在这方面的 API 设计的很不合理。稍微使用不当就会出问题。

Invalid update: invalid number of items in section 0. The number
of items contained in an existing section after the update (11)
must be equal to the number of items contained in that section
before the update (7), plus or minus the number of items inserted
or deleted from that section (1 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 不对应,导致刷新的时候出问题了。所以,通常情况下,如果要在项目中使用局部刷新,建议使用 performBatchUpdates 这个方法。可以减少很多问题。但是对于 performBatchUpdates 这个方法来说,也有一个重点需要关注,就是组合操作有执行步骤。具体文档如下:

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.

大概意思就是,无论你的数据源如何变化(是先删除,后新增,还是先新增,后删除),对于 performBatchUpdates 而言,都需要先执行 deleteItems 再执行 insertItems 并且需要正确的 IndexPath。示例如下:

var items = ["a","b","c","d","e","f"]
items.append(contentsOf: [“g”, “h”, “i”])
items.removeFirst()
items.removeFirst()
items.removeFirst()
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)

总而言之,UICollectionView 提供了局部刷新的方式,但是对于实际使用过程中,还是有不少困难的。特别是找到正确的 IndexPath 和对应操作。

编辑路径

如果我们把刷新之前的数据源叫 Old,经过一系列变化之后变成了 New。我们把这「一系列变化」称之为 编辑路径。前文描述的插入(insert)、删除(delete)、更新(reload、移动(move)则是编辑路径的具体步骤。

举一个例子,从 Wong 变成 VVong 的编辑路径是:

  • 删除 第一位的 W
  • 在第一位 插入 V
  • 在第一位 插入 V

所以,如果想要愉快的使用 performBatchUpdates,那么就要计算出从 OldNew 的编辑路径。

Wagner–Fischer 算法

寻找编辑路径的方式有很多,Wagner–Fischer 算法 就是一种,主要是通过动态规划的思路,限定删除插入替换三种步骤,找到一条最优的编辑路径。

动态规划

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

以 "wong" 变成 "vvong" 为例。

如果要解决 "wong" -> "vvong",其实只需要解决 "won" -> "vvon"
而如果要解决 "won" -> "vvon",其实只需要解决 "wo" -> "vvo"
而如果要解决 "wo" -> "vvo",其实只需要解决 "w" -> "vv"
如果要解决 "w" -> "vv",其实只需要解决 "w" -> "v" + 插入 v
所以最后的答案是替换 w 为 v, 并插入 v。

编辑步骤

  • 替换 : 从 “w” 变成 “v”,需要一次替换。步数长度为 1。
  • 删除 : 从 “w” 变成 “”,需要一次删除。步数长度为 1。
  • 插入 : 从 “” 变成 “v”,需要一次插入。步数长度为 1。

计算最小编辑路径

1. 把问题分解为,从 “wong” -> "" 和 “” -> "vvong" 两个问题,并放到矩阵中。

垂直方向的变化为删除,水平方向的变化为插入。每个方格对应从 A 到 B 的编辑路径。

top Created with Sketch.