Description
A fast and flexible O(n) difference algorithm framework for Swift collection. The algorithm is optimized based on the Paul Heckel's algorithm.
DifferenceKit alternatives and similar libraries
Based on the "Utility" category.
Alternatively, view DifferenceKit alternatives based on common mentions on social networks and blogs.
-
SwifterSwift
A handy collection of more than 500 native Swift extensions to boost your productivity. -
R.swift
Strong typed, autocompleted resources like images, fonts and segues in Swift projects -
SwiftGen-Storyboard
The Swift code generator for your assets, storyboards, Localizable.strings, β¦ β Get rid of all String-based APIs! -
SwiftGen
The Swift code generator for your assets, storyboards, Localizable.strings, β¦ β Get rid of all String-based APIs! -
swift-protobuf
Plugin and runtime library for using protobuf with Swift -
Dollar
A functional tool-belt for Swift Language similar to Lo-Dash or Underscore.js in Javascript -
ExSwift
a set of Swift extensions for standard types and classes. -
EZSwiftExtensions
:smirk: How Swift standard types and classes were supposed to work. -
Result
Swift type modelling the success/failure of arbitrary operations. -
DeepDiff
π¦Amazingly incredible extraordinary lightning fast diffing in Swift -
Device
Light weight tool for detecting the current device and screen size written in swift. -
SwiftLinkPreview
It makes a preview from an URL, grabbing all the information such as title, relevant texts and images. -
WhatsNew
Showcase new features after an app update similar to Pages, Numbers and Keynote. -
Codextended
Extensions giving Swift's Codable API type inference super powers π¦ΈββοΈπ¦ΉββοΈ -
Popsicle
Delightful, extensible Swift value interpolation framework. -
SwiftyJSONAccelerator
macOS app to generate Swift 5 code for models from JSON (with Codeable) -
Playbook
πA library for isolated developing UI components and automatically taking snapshots of them. -
ReadabilityKit
Preview extractor for news, articles and full-texts in Swift -
Compass
:earth_africa: Compass helps you setup a central navigation system for your application -
ObjectiveKit
Swift-friendly API for a set of powerful Objective C runtime functions. -
Delegated
π·ββοΈ Closure-based delegation without memory leaks -
Bow
πΉ Bow is a cross-platform library for Typed Functional Programming in Swift -
Solar
A Swift micro library for generating Sunrise and Sunset times. -
Pythonic.swift
Pythonic tool-belt for Swift β a Swift implementation of selected parts of Python standard library. -
SwiftyUtils
All the reusable code that we need in each project -
Rugby
π Cache CocoaPods for faster rebuild and indexing Xcode project -
Prototope
Swift library of lightweight interfaces for prototyping, bridged to JS. -
BetterSafariView
A better way to present a SFSafariViewController or start a ASWebAuthenticationSession in SwiftUI.
Appwrite - The Open Source Firebase alternative introduces iOS support
* Code Quality Rankings and insights are calculated and provided by Lumnify.
They vary from L1 to L5 with "L5" being the highest.
Do you think we are missing an alternative of DifferenceKit or a related project?
README
A fast and flexible O(n) difference algorithm framework for Swift collection. The algorithm is optimized based on the Paul Heckel's algorithm.
Made with β€οΈ by Ryo Aoyama and Contributors
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
}
[See More Usage]
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 | Myers | O(ND) |
Swift.CollectionDifference | Myers | O(ND) |
* Heckel algorithm
* Myers algorithm
- Supported Collection
Linear | Sectioned | Duplicate element/section | |
---|---|---|---|
DifferenceKit | β | β | β |
RxDataSources | β | β | β |
FlexibleDiff | β | β | β |
IGListKit | β | β | β |
DeepDiff | β | β | β |
Differ | β | β | β |
Dwifft | β | β | β |
Swift.CollectionDifference | β | β | β |
* Linear means 1-dimensional collection
* Sectioned means 2-dimensional collection
- Supported Element Diff
Delete | Insert | Move | Reload | Move across sections | |
---|---|---|---|---|---|
DifferenceKit | β | β | β | β | β |
RxDataSources | β | β | β | β | β |
FlexibleDiff | β | β | β | β | β |
IGListKit | β | β | β | β | β |
DeepDiff | β | β | β | β | β |
Differ | β | β | β | β | β |
Dwifft | β | β | β | β | β |
Swift.CollectionDifference | β | β | β | β | β |
- Supported Section Diff
Delete | Insert | Move | Reload | |
---|---|---|---|---|
DifferenceKit | β | β | β | β |
RxDataSources | β | β | β | β |
FlexibleDiff | β | β | β | β |
IGListKit | β | β | β | β |
DeepDiff | β | β | β | β |
Differ | β | β | β | β |
Dwifft | β | β | β | β |
Swift.CollectionDifference | β | β | β | β |
Requirements
- Swift 4.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 to your Podfile
:
pod 'DifferenceKit/Core'
iOS / tvOS
To use DifferenceKit with UIKit extension, add the following to your Podfile
:
pod 'DifferenceKit'
or
pod 'DifferenceKit/UIKitExtension'
macOS
To use DifferenceKit with AppKit extension, add the following to your Podfile
:
pod 'DifferenceKit/AppKitExtension'
watchOS
There is no UI extension for watchOS.
To use only algorithm without extensions for UI, add the following to your Podfile
:
pod 'DifferenceKit/Core'
Carthage
Add the following to your Cartfile
:
github "ra1028/DifferenceKit"
Swift Package Manager for Apple platforms
Select Xcode menu File > Swift Packages > Add Package Dependency
and enter repository URL with GUI.
Repository: https://github.com/ra1028/DifferenceKit
Swift Package Manager
Add the following to the dependencies of your Package.swift
:
.package(url: "https://github.com/ra1028/DifferenceKit.git", from: "version")
Contribution
Pull requests, bug reports and feature requests are welcome π
Please see the CONTRIBUTING file for learn how to contribute to DifferenceKit.
Credit
Bibliography
DifferenceKit was developed with reference to the following excellent materials and framework.
- A technique for isolating differences between files (by Paul Heckel)
- DifferenceAlgorithmComparison (by @horita-yuya)
OSS using DifferenceKit
The list of the awesome OSS which uses this library. They also help to understanding how to use DifferenceKit.
- Carbon (by @ra1028)
- DiffableDataSources (by @ra1028)
- Rocket.Chat.iOS (by RocketChat)
- wire-ios (by Wire Swiss GmbH)
- ReactiveLists (by PlanGrid)
- ReduxMovieDB (by @cardoso)
- TetrisDiffingCompetition (by @skagedal)
Other diffing libraries
I respect and οΈβ€οΈ all libraries involved in diffing.
- RxDataSources (by @kzaher, RxSwift Community)
- IGListKit (by Instagram)
- FlexibleDiff (by @andersio, RACCommunity)
- DeepDiff (by @onmyway133)
- Differ (by @tonyarnold)
- Dwifft (by @jflinter)
- Changeset (by @osteslag)
License
DifferenceKit is released under the Apache 2.0 License.
*Note that all licence references and agreements mentioned in the DifferenceKit README section above
are relevant to that project's source code only.