The algorithm is optimized based on the Paul Heckel's algorithm.
A fast and flexible O(n) difference algorithm framework for Swift collection.
Features
Sample app is imitated from DataSources
Algorithm
The algorithm used in DifferenceKit is optimized based on the Paul Heckel's algorithm.
See also his paper "A technique for isolating differences between files" released in 1978.
RxDataSources and IGListKit are also implemented based on his algorithm.
This allows all types of differences to be computed in linear time O(n).
However, in performBatchUpdates
of UITableView
and UICollectionView
, there are combinations of operations that cause crash when applied simultaneously.
To solve this problem, DifferenceKit
takes an approach of split the set of differences at the minimal stages that can be perform batch-updates with no crashes.
Implementation is here.
Documentation
See docs in GitHub Pages.
Documentation is generated by jazzy.
Getting Started
Example codes
The type of the element that to take the differences must be conform to the Differentiable
protocol.
The differenceIdentifier
's type is determined generic by the 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 conformed to Equatable
or Hashable
๏ผ
// If `Self` conform to `Hashable`.
var differenceIdentifier: Self {
return self
}
// If `Self` conform to `Equatable`.
func isContentEqual(to source: Self) -> Bool {
return self == source
}
So, you can simply:
extension String: Differentiable {}
Calculates the differences 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 conformed 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 conform to DifferentiableSection
protocol, but in most cases you can use ArraySection
that general type conformed to it.
ArraySection
requires a model conforming to Differentiable
for differentiate 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 incremental updates on UITableView
and UICollectionView
using the created StagedChangeset
.
setData
closure. The differences 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 differences 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 features and performance 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) - 3.0.2
- FlexibleDiff - 0.0.5
- IGListKit - 3.4.0
- ListDiff - 0.1.0
- DeepDiff - 1.2.0
- Differ (Diff.swift) - 1.2.3
- Dwifft - 0.8
Features comparison
- Supported collection
Linear | Sectioned | Duplicate Element/Section | |
---|---|---|---|
DifferenceKit | |||
RxDataSources | |||
FlexibleDiff | |||
IGListKit | |||
ListDiff | |||
DeepDiff | |||
Differ | |||
Dwifft |
Linear
means 1-dimensional collection.
Sectioned
means 2-dimensional collection.
- Supported element differences
Delete | Insert | Move | Reload | Move across sections | |
---|---|---|---|---|---|
DifferenceKit | |||||
RxDataSources | |||||
FlexibleDiff | |||||
IGListKit | |||||
ListDiff | |||||
DeepDiff | |||||
Differ | |||||
Dwifft |
- Supported section differences
Delete | Insert | Move | Reload | |
---|---|---|---|---|
DifferenceKit | ||||
RxDataSources | ||||
FlexibleDiff | ||||
IGListKit | ||||
ListDiff | ||||
DeepDiff | ||||
Differ | ||||
Dwifft |
Performance comparison
Performance was measured using XCTestCase.measure
on iPhoneX simulator with -O -whole-module-optimization
.
Use Foundation.UUID
as an element.
- From 5,000 elements to 500 deleted and 500 inserted
Time(second) | |
---|---|
DifferenceKit | 0.0022 |
RxDataSources | 0.0078 |
FlexibleDiff | 0.0168 |
IGListKit | 0.0412 |
ListDiff | 0.0388 |
DeepDiff | 0.0150 |
Differ | 0.3260 |
Dwifft | 33.600 |
- From 10,000 elements to 1,000 deleted and 1,000 inserted
Time(second) | |
---|---|
DifferenceKit | 0.0049 |
RxDataSources | 0.0143 |
FlexibleDiff | 0.0305 |
IGListKit | 0.0891 |
ListDiff | 0.0802 |
DeepDiff | 0.0300 |
Differ | 1.3450 |
Dwifft |
- From 100,000 elements to 10,000 deleted and 10,000 inserted
Time(second) | |
---|---|
DifferenceKit | 0.057 |
RxDataSources | 0.179 |
FlexibleDiff | 0.356 |
IGListKit | 1.329 |
ListDiff | 1.026 |
DeepDiff | 0.334 |
Differ | |
Dwifft |
Requirements
- Swift4.2+
- iOS 9.0+
- tvOS 9.0+
- OS X 10.9+
- watchOS 2.0+ (only algorithm)
Installation
CocoaPods
To use only algorithm without extensions for UI, add the following:
use_frameworks!
target 'TargetName' do
pod 'DifferenceKit/Core'
end
iOS/tvOS
To use DifferenceKit with UIKit extension, add the following to your Podfile
:
target 'TargetName' do
pod 'DifferenceKit'
end
or
target 'TargetName' do
pod 'DifferenceKit/UIKitExtension'
end
macOS
To use DifferenceKit with AppKit extension, add the following to your Podfile
:
target 'TargetName' do
pod 'DifferenceKit/AppKitExtension'
end
watchOS
There is no UI extension for watchOS.
You can use only the algorithm.
Carthage
Add the following to your Cartfile
:
github "ra1028/DifferenceKit"
And run
carthage update
Swift Package Manager
To use DifferenceKit in a project with SPM, add the following to your Package.swift
:
import PackageDescription
let package = Package(
name: "YourProjectName",
products: [
.executable(name: "yourexecutable", targets: ["yourexecutable"]),
],
dependencies: [
.package(url: "https://github.com/ra1028/DifferenceKit.git", from: "any version")
],
targets: [
.target(name: "yourexecutable", dependencies: ["DifferenceKit"])
]
)
The SPM version does not include the UIKit and AppKit extensions.
Contribution
Welcome to fork and submit pull requests.
Before submitting pull request, please ensure you have passed the included tests.
If your pull request including new function, please write test cases for it.
License
DifferenceKit is released under the MIT License.