DifferenceKit
💻 A fast and flexible O(n) difference algorithm framework for Swift collection.
Install / Use
/learn @ra1028/DifferenceKitREADME
Features
💡 Fastest O(n) diffing algorithm optimized for Swift collection
💡 Calculate diffs for batch updates of list UI in UIKit, AppKit and Texture
💡 Supports both linear and sectioned collection even if contains duplicates
💡 Supports all kind of diffs for animated UI batch updates
Algorithm
This is a diffing algorithm developed for Carbon, works stand alone.
The algorithm optimized based on the Paul Heckel's algorithm.
See also his paper "A technique for isolating differences between files" released in 1978.
It allows all kind of diffs to be calculated in linear time O(n).
RxDataSources and IGListKit are also implemented based on his algorithm.
However, in performBatchUpdates of UITableView, UICollectionView, etc, there are combinations of diffs that cause crash when applied simultaneously.
To solve this problem, DifferenceKit takes an approach of split the set of diffs at the minimal stages that can be perform batch updates with no crashes.
Implementation is here.
Getting Started
Basic Usage
The type of the element that to take diffs must be conform to the Differentiable protocol.
The differenceIdentifier's type is generic associated type:
struct User: Differentiable {
let id: Int
let name: String
var differenceIdentifier: Int {
return id
}
func isContentEqual(to source: User) -> Bool {
return name == source.name
}
}
In the case of definition above, id uniquely identifies the element and get to know the user updated by comparing equality of name of the elements in source and target.
There are default implementations of Differentiable for the types that conforming to Equatable or Hashable：
// If `Self` conforming to `Hashable`.
var differenceIdentifier: Self {
return self
}
// If `Self` conforming to `Equatable`.
func isContentEqual(to source: Self) -> Bool {
return self == source
}
Therefore, you can simply:
extension String: Differentiable {}
Calculate the diffs by creating StagedChangeset from two collections of elements conforming to Differentiable:
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)
If you want to include multiple types conforming to Differentiable in the collection, use AnyDifferentiable:
let source = [
AnyDifferentiable("A"),
AnyDifferentiable(User(id: 0, name: "Vincent"))
]
In the case of sectioned collection, the section itself must have a unique identifier and be able to compare whether there is an update.
So each section must conforming to DifferentiableSection protocol, but in most cases you can use ArraySection that general type conforming to it.
ArraySection requires a model conforming to Differentiable for diffing from other sections:
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)
You can perform diffing batch updates of UITableView and UICollectionView using the created StagedChangeset.
⚠️ Don't forget to synchronously update the data referenced by the data-source, with the data passed in the setData closure. The diffs are applied in stages, and failing to do so is bound to create a crash:
tableView.reload(using: changeset, with: .fade) { data in
dataSource.data = data
}
Batch updates using too large amount of diffs may adversely affect to performance.
Returning true with interrupt closure then falls back to reloadData:
collectionView.reload(using: changeset, interrupt: { $0.changeCount > 100 }) { data in
dataSource.data = data
}
Comparison with Other Frameworks
Made a fair comparison as much as possible in performance and features with other popular and awesome frameworks.
This does NOT determine superiority or inferiority of the frameworks.
I know that each framework has different benefits.
The frameworks and its version that compared is below.
- 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
Performance Comparison
Benchmark project is here.
Performance was mesured by code compiled using Xcode11.1 and Swift 5.1 with -O optimization and run on iPhone11 Pro simulator.
Use Foundation.UUID as an element of collections.
- From 5,000 elements to 1,000 deleted, 1,000 inserted and 200 shuffled
| |Time(sec) |
|:-------------------------|-------------------------:|
|DifferenceKit |0.0019 |
|RxDataSources |0.0074 |
|IGListKit |0.0346 |
|FlexibleDiff |0.0161 |
|DeepDiff |0.0373 |
|Differ |1.0581 |
|Dwifft |0.4732 |
|Swift.CollectionDifference|0.0620 |
- From 100,000 elements to 10,000 deleted, 10,000 inserted and 2,000 shuffled
| |Time(sec) |
|:-------------------------|-------------------------:|
|DifferenceKit |0.0348 |
|RxDataSources |0.1024 |
|IGListKit |0.7002 |
|FlexibleDiff |0.2189 |
|DeepDiff |0.5537 |
|Differ |153.8007 |
|Dwifft |187.1341 |
|Swift.CollectionDifference|5.0281 |
Features Comparison
- Algorithm
| |Base algorithm|Order| |:-------------------------|-------------:|----:| |DifferenceKit |Heckel |O(N) | |RxDataSources |Heckel |O(N) | |FlexibleDiff |Heckel |O(N) | |IGListKit |Heckel |O(N) | |DeepDiff |Heckel |O(N) | |Differ |Myers |O(ND)| |Dwifft
Related Skills
node-connect
337.4kDiagnose OpenClaw node connection and pairing failures for Android, iOS, and macOS companion apps
frontend-design
83.2kCreate distinctive, production-grade frontend interfaces with high design quality. Use this skill when the user asks to build web components, pages, or applications. Generates creative, polished code that avoids generic AI aesthetics.
openai-whisper-api
337.4kTranscribe audio via OpenAI Audio Transcriptions API (Whisper).
commit-push-pr
83.2kCommit, push, and open a PR
