此文章為本人翻譯的譯文，版權(quán)為原作者所有吼虎。
英文原文：A better way to update UICollectionView data in Swift with diff framework
Familiar friends
很難想象一款iOS的APP不使用UITableView和UICollectionView叨叙，大多數(shù)時(shí)候我們從服務(wù)器重付，緩存和過(guò)濾器中獲取數(shù)據(jù)然后在列表中展示玄组，當(dāng)數(shù)據(jù)發(fā)生改變的時(shí)候更新列表整以。
這個(gè)時(shí)候你就你就會(huì)想到你最喜歡的方法reloadData胧辽，用reloadData整個(gè)列表都會(huì)被刷新。當(dāng)你想用最快速的方式刷新列表這是沒(méi)有問(wèn)題的公黑。但CPU會(huì)重新計(jì)算UITableView的size邑商，這會(huì)影響性能。更進(jìn)一步凡蚜，如果這些改變應(yīng)該被凸顯出來(lái)人断，并且你想讓用戶感知到發(fā)生了什么，手動(dòng)插入或刪除某一行是更好的選擇朝蜘。
如果你是做安卓開(kāi)發(fā)恶迈，或許知道通過(guò)使用DiffUtil而不是notifyDataSetChanged來(lái)計(jì)算變化，以便更容易地更新RecyclerView谱醇。不幸的是iOS并不提供這樣的接口暇仲，但是我們可以學(xué)習(xí)怎么去做。
這里會(huì)用UICollectionView舉例副渴，但UITableView實(shí)踐的方式是一樣的熔吗。
Drag and Drop
想象一下App需要實(shí)現(xiàn)用戶可以通過(guò)拖拽移動(dòng)UICollectionView的功能，你可以看看DragAndDrop這個(gè)demo佳晶，它是用iOS 11中的 drag and drop API接口實(shí)現(xiàn)的桅狠。
在調(diào)用UICollectionView的更新方法之前，必須確保數(shù)據(jù)更改了。 然后調(diào)用deleteItems和insertItems來(lái)反映數(shù)據(jù)變化中跌。 UICollectionView會(huì)執(zhí)行一個(gè)很棒的的動(dòng)畫(huà)咨堤。
func collectionView(_ collectionView: UICollectionView, performDropWith coordinator: UICollectionViewDropCoordinator) {
let destinationIndexPath = coordinator.destinationIndexPath
let sourceIndexPath = coordinator.items.last?.dragItem.localObject as! IndexPath
// remove
sourceItems.remove(at: sourceIndexPath.item)
sourceCollectionView.deleteItems(at: [sourceIndexPath])
// insert
destinationItems.insert(draggedItem, at: destinationIndexPath.item)
destinationCollectionView.insertItems(at: [destinationIndexPath])
}
這是一個(gè)簡(jiǎn)單的例子，只需從集合中刪除或添加1個(gè)item漩符。但在實(shí)際項(xiàng)目中一喘，數(shù)據(jù)要復(fù)雜得多，變化并不是那么微不足道嗜暴。如果從服務(wù)器拿到大量的items需要插入和刪除凸克，你需要計(jì)算正確的IndexPath來(lái)調(diào)用，這不是一件容易的事闷沥。大多數(shù)時(shí)候你會(huì)遇到以下崩潰：
NSInternalInconsistencyException
Terminating app due to uncaught exception ‘NSInternalInconsistencyException’,
reason: ‘Invalid update: invalid number of items in section 0.
The number of items contained in an existing section after the update (213)
must be equal to the number of items contained in that section before
the update (154), plus or minus the number of items inserted or
deleted from that section (40 inserted, 0 deleted) and plus
or minus the number of items moved into or out of
that section (0 moved in, 0 moved out).’
依我的經(jīng)驗(yàn)來(lái)看萎战，這個(gè)是隨機(jī)發(fā)生（實(shí)際是因?yàn)閿?shù)據(jù)和IndexPath不匹配）。
Game of IndexPath
讓我們通過(guò)一些例子來(lái)梳理對(duì)IndexPath的了解舆逃。通過(guò)6個(gè)item的數(shù)據(jù)集蚂维，我們執(zhí)行一些更新操作并找出IndexPath應(yīng)該是什么。
tems = ["a", "b", "c", "d", "e", "f"]
為了更好的理解路狮，請(qǐng)查看這個(gè)demoCollectionUpdateExample
1. Insert 3 items at the end
items.append(contentsOf: ["g", "h", "i"])
// a, b, c, d, e, f, g, h, i
let indexPaths = Array(6…8).map { IndexPath(item: $0, section: 0) }
collectionView.insertItems(at: indexPaths)
2. Delete 3 items at the end
items.removeLast()
items.removeLast()
items.removeLast()
// a, b, c
let indexPaths = Array(3…5).map { IndexPath(item: $0, section: 0) }
collectionView.deleteItems(at: indexPaths)
3. Update item at index 2
items[2] = “??”
// a, b, ??, d, e, f
let indexPath = IndexPath(item: 2, section: 0)
collectionView.reloadItems(at: [indexPath])
4. Move item “c” to the end
items.remove(at: 2)
items.append("c")
// a, b, d, e, f, c
collectionView.moveItem(
at: IndexPath(item: 2, section: 0),
to: IndexPath(item: 5, section :0)
)
5. Delete 3 items at the beginning, then insert 3 items at the end
對(duì)于多個(gè)不同的操作虫啥，我們應(yīng)該使用performBatchUpdates
如果要在一個(gè)動(dòng)畫(huà)操作中對(duì)集合視圖進(jìn)行多次更改，則可以使用此方法奄妨，而不是在幾個(gè)單獨(dú)的動(dòng)畫(huà)中涂籽。你可以使用此方法插入，刪除砸抛，重新加載或移動(dòng)單元格评雌，或使用它來(lái)更改與一個(gè)或多個(gè)單元格關(guān)聯(lián)的布局參數(shù)
items.removeFirst()
items.removeFirst()
items.removeFirst()
items.append(contentsOf: ["g", "h", "i"])
// d, e, f, g, h, i
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)
6. Insert 3 items at the end, then delete 3 items at the beginning
items.append(contentsOf: ["g", "h", "i"])
items.removeFirst()
items.removeFirst()
items.removeFirst()
// d, e, f, g, h, i
collectionView.performBatchUpdates({
let insertIndexPaths = Array(6…8).map { IndexPath(item: $0, section: 0) }
collectionView.insertItems(at: insertIndexPaths)
let deleteIndexPaths = Array(0…2).map { IndexPath(item: $0, section: 0) }
collectionView.deleteItems(at: deleteIndexPaths)
}, completion: nil)
如果你run第6個(gè)例子，將會(huì)crash
Terminating app due to uncaught exception
‘NSInternalInconsistencyException’,
reason: ‘a(chǎn)ttempt to insert item 6 into section 0,
but there are only 6 items in section 0 after the update’
performBatchUpdates
這是由performBatchUpdates的工作方式引起的锰悼。 看看這里documentation:
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.
無(wú)論我們?nèi)绾握{(diào)用insert或delete柳骄，performBatchUpdates總是先執(zhí)行刪除操作。因此箕般，如果首先發(fā)生刪除耐薯，我們需要使用正確的IndexPath調(diào)用deleteItems和insertItems。
items.append(contentsOf: ["g", "h", "i"])
items.removeFirst()
items.removeFirst()
items.removeFirst()
// d, e, f, g, h, i
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)
Operation
UICollectionView上有許多操作丝里，還有一些操作可以更新整個(gè)section曲初。看看Ordering of Operations and Index
insertItems(at indexPaths: [IndexPath])
deleteItems(at indexPaths: [IndexPath])
reloadItems(at indexPaths: [IndexPath])
moveItem(at indexPath: IndexPath, to newIndexPath: IndexPath)
performBatchUpdates(_ updates, completion)
insertSections(_ sections: IndexSet)
deleteSections(_ sections: IndexSet)
reloadSections(_ sections: IndexSet)
moveSection(_ section: Int, toSection newSection: Int)
Edit distance
手動(dòng)執(zhí)行這些計(jì)算非常繁瑣且容易出錯(cuò)杯聚。我們可以使用一些算法構(gòu)建自己的抽象臼婆。 最原始的的算法是Wagner-Fischer，它使用Dynamic_programming（動(dòng)態(tài)規(guī)劃）來(lái)查找兩個(gè)字符串之間的編輯路徑幌绍。
編輯路徑表示從一個(gè)字符串更改為另一個(gè)字符串所需的步驟集合颁褂。字符串只是一個(gè)字符集合故响，因此我們可以概括這個(gè)概念，使其適用于任何項(xiàng)目集合颁独。 我們要求項(xiàng)目符合Hashable彩届，而不是比較字符。
"kit" to "kat"
我們?cè)鯓硬拍軐?kit"這個(gè)詞改為"kat"誓酒？ 我們需要執(zhí)行哪些操作樟蠕？ 你可以告訴"只需將字母i更改為a"，但這個(gè)簡(jiǎn)單的示例可幫助您理解算法靠柑，讓我們開(kāi)始吧寨辩。
Deletions
如果我們將"kit"修改為字符串""，需要3個(gè)刪除操作
"kit" -> "" ?? 3次刪除操作
"ki" -> "" ?? 2次刪除操作
"k" -> "" ?? 1次刪除操作
Insertions
如果我們將空字符串""變?yōu)?kit"歼冰，需要3次插入操作
"" -> "k" ?? 1次插入操作
"" -> "ka" ?? 2次插入操作
"" -> "kat" ?? 3次插入操作
If equal, take value from the top left
你可以將算法視為從源字符串 -> 空字符串 -> 目標(biāo)字符串靡狞。我們嘗試找到要更新的最小步驟。水平移動(dòng)意味著插入停巷，垂直意味著刪除耍攘，對(duì)角意味著替換榕栏。
這樣我們就可以構(gòu)建我們的矩陣畔勤，逐行逐列地迭代。首先扒磁，源集合中的字母"k"與目標(biāo)集合中的字母"k"相同庆揪，我們只需從左上角取值，即0替換
If not equal
我們繼續(xù)看目標(biāo)結(jié)合上的下一個(gè)字母妨托。 這里"k"和"a"不一樣缸榛。 我們從左，上兰伤，左上取最小值内颗。 然后增加一個(gè)
這里我們從左邊取值，這是水平的敦腔，所以我們?cè)黾?次插入均澳。
"k" to "kat" ?? 2 insertions
繼續(xù)，"t"和"k"不一樣符衔，所以我們從左邊水平取值找前。 在這里你可以看到它某種意義上是說(shuō)得通的，從"k"到"kat"判族，我們需要2個(gè)插入躺盛，即插入字母"a"和"t"。
The bottom right value
一行一行的繼續(xù)形帮，直到我們達(dá)到右下角的值槽惫，這樣就可以得到編輯路徑周叮。 這里1個(gè)替換意味著我們需要執(zhí)行1次替換以從"kit"變?yōu)?kat"，這是用"a"更新"i"界斜。
您可以很容易地看到需要更新索引1则吟，但是我們?cè)趺粗浪撬饕???
DeepDiff
這個(gè)算法顯示了兩個(gè)字符串之間的變化，但由于字符串只是字符的集合锄蹂。 我們可以概括這個(gè)概念氓仲，使其適用于任何item集合。
DeepDiff的實(shí)現(xiàn)在GitHub上得糜。 以下是它的使用方法敬扛。 假設(shè)一個(gè)old的和new的數(shù)組，它計(jì)算轉(zhuǎn)換所需的更改朝抖。 更改包括：更改類(lèi)型(insert, delete, replace, move)和更改的index啥箭。
let old = Array("abc")
let new = Array("bcd")
let changes = diff(old: old, new: new)
// Delete "a" at index 0
// Insert "d" at index 2
代碼是解釋的最好方式。但在接下來(lái)的部分中治宣，我將概述庫(kù)中的一些技術(shù)要點(diǎn)急侥，以便你輕松遵循。 你可以看看here
Complexity
我們遍歷矩陣侮邀，其中m和n分別是源和目標(biāo)集合的長(zhǎng)度坏怪。 所以我們可以看到這個(gè)算法的復(fù)雜度是O(mn)。
此外绊茧，性能在很大程度上取決于集合的大小以及項(xiàng)目的復(fù)雜程度铝宵。 您想要執(zhí)行的更復(fù)雜和更深的Equatable會(huì)極大地影響性能。
如果你查看wiki page 华畏，會(huì)提示我們可以采取一些措施來(lái)提高性能鹏秋。
“We can adapt the algorithm to use less space, O(m) instead of O(mn), since it only requires that the previous row and current row be stored at any one time.”
看到我們一次只操作一行，存儲(chǔ)整個(gè)矩陣是低效的亡笑，而我們可以只使用2個(gè)數(shù)組來(lái)計(jì)算侣夷，這也減少了內(nèi)存占用。
Change
由于每種change都是互斥的仑乌，因此它們非常適合用作枚舉
public enum Change<T> {
case insert(Insert<T>)
case delete(Delete<T>)
case replace(Replace<T>)
case move(Move<T>)
}
- insert：item被插入到一個(gè)index下
- delete：item從一個(gè)index下移除
- replace：一個(gè)index下的item被另一個(gè)替換
- move：一個(gè)item從一個(gè)index下移到另一個(gè)index下
如上所述百拓，我們只需要一次跟蹤2行即可運(yùn)行。每行的slots都是一組改變绝骚。這里diff是一個(gè)泛型函數(shù)耐版，它接受Hashable類(lèi)型的任何集合，包括字符串压汪。
public func diff<T: Hashable>(old: Array<T>, new: Array<T>) -> [Change<T>] {
let previousRow = Row<T>()
previousRow.seed(with: new)
let currentRow = Row<T>()
…
}
我喜歡分離關(guān)注點(diǎn)粪牲，所以每一行都應(yīng)該自己管理狀態(tài)。首先聲明一個(gè)持有slots數(shù)組的Row對(duì)象
class Row<T> {
/// Each slot is a collection of Change
var slots: [[Change<T>]] = []
}
回想一下我們逐行逐列的算法止剖。所以我們使用2個(gè)循環(huán)
old.enumerated().forEach { indexInOld, oldItem in
new.enumerated().forEach { index, item in
}
}
我們的工作只是比較舊數(shù)組和新數(shù)組中的items腺阳，并正確更新Row對(duì)象中的slots落君。
Hashable vs Equatable
我們需要巧妙地進(jìn)行equation check，因?yàn)楫?dāng)對(duì)象很復(fù)雜時(shí)亭引，Equatable函數(shù)可能需要時(shí)間绎速。我們知道Hashable符合Equatable，并且2個(gè)相同的對(duì)象具有相同的哈希值焙蚓。 因此纹冤，如果它們沒(méi)有相同的哈希值，則它們不是等同的购公。 反轉(zhuǎn)并不能保證萌京，但這足以減少對(duì)Equatable函數(shù)的調(diào)用次數(shù)。
private func isEqual<T: Hashable>(oldItem: T, newItem: T) -> Bool {
// Same items must have same hashValue
if oldItem.hashValue != newItem.hashValue {
return false
} else {
// Different hashValue does not always mean different items
return oldItem == newItem
}
}
算法還有其他一些細(xì)節(jié)宏浩，但你應(yīng)該看一下代碼知残，它會(huì)告訴你更多。
How about the Move
到目前為止比庄，你已經(jīng)注意到我們剛剛更新了插入求妹，刪除和替換的步驟。 那移動(dòng)呢佳窑？事實(shí)證明這并不困難制恍。移動(dòng)只是插入相同item后的刪除。 你可以看看MoveReducer华嘹，它的實(shí)現(xiàn)效率不高吧趣，但至少它會(huì)給你一些提示法竞。
Inferring IndexPath for UICollectionView
使用DeepDiff返回的更改數(shù)組耙厚，我們可以推斷出要提供給UICollectionView以執(zhí)行更新的所需IndexPath集合。
從Change到IndexPath的轉(zhuǎn)換幾乎是不言自明的岔霸。 您可以查看UICollectionViewextension薛躬。
有一點(diǎn)需要注意，否則你會(huì)得到熟悉的NSInternalInconsistencyException呆细。那就是在performBatchUpdates之外調(diào)用reloadItems型宝。 這是因?yàn)榇怂惴ǚ祷氐?code>Replace步驟包含更新集合后的狀態(tài)的IndexPath，但UICollectionView期望它們?cè)谠摖顟B(tài)之前絮爷。
除此之外趴酣，它非常簡(jiǎn)單。你可以通過(guò)這個(gè)例子對(duì)這些changes的速度和有用信息感到驚訝坑夯。
Where to go from here
完成這個(gè)指南后岖寞，你將了解如何通過(guò)手動(dòng)計(jì)算IndexPath手動(dòng)更新到UICollectionView。在遇到異常后柜蜈，你知道這個(gè)庫(kù)給你提供了多少幫助仗谆。你還了解算法以及如何用Swift實(shí)現(xiàn)指巡。你還知道如何使用Hashable和Equatable。
DeepDiff的當(dāng)前版本現(xiàn)在使用Heckel算法隶垮，該算法以線性時(shí)間運(yùn)行并且執(zhí)行速度更快藻雪。 測(cè)試結(jié)果如下圖
IGListKit也實(shí)現(xiàn)了Heckel算法，但是用Objective C++中并對(duì)其進(jìn)行了優(yōu)化狸吞。在下一篇文章中勉耀，我將介紹Heckel算法以及如何在Swift中實(shí)現(xiàn)它，以及如何為這些diff算法編寫(xiě)單元測(cè)試蹋偏。 敬請(qǐng)關(guān)注瑰排！
與此同時(shí)，如果你覺(jué)得有冒險(xiǎn)精神暖侨，這里有一些據(jù)說(shuō)非常高效的其他算法：
最后個(gè)人補(bǔ)充
感興趣的也可以看看這個(gè)項(xiàng)目DifferenceKit椭住，也是我們公司項(xiàng)目中在使用的，據(jù)它gitlab上個(gè)提供的數(shù)據(jù)顯示字逗，它是以下幾個(gè)項(xiàng)目中各方面性能最好的
- DifferenceKit
- RxDataSources
- FlexibleDiff
- IGListKit
- ListDiff
- DeepDiff
- Differ
- Dwifft
