Differencekit

💻 A fast and flexible O(n) difference algorithm framework for Swift collection.
Alternatives To Differencekit
Project NameStarsDownloadsRepos Using ThisPackages Using ThisMost Recent CommitTotal ReleasesLatest ReleaseOpen IssuesLicenseLanguage
Difftastic15,447
4 days ago57July 27, 2023143mitRust
a structural diff that understands syntax 🟥🟩
Differencekit3,328
194 months ago21May 07, 202127apache-2.0Swift
💻 A fast and flexible O(n) difference algorithm framework for Swift collection.
Textdistance3,1721442a year ago25September 20, 20229mitPython
📐 Compute distance between sequences. 30+ algorithms, pure python implementation, common interface, optional external libs usage.
Dwifft1,767
263 years ago12October 22, 201818mitSwift
Swift Diff
Diff.swift935
205 years ago7September 30, 20178mitSwift
The fastest Diff and patch library in Swift. Includes UICollectionView/UITableView utils.
Nanomorph710225652 years ago33February 18, 202117mitJavaScript
🚅 - Hyper fast diffing algorithm for real DOM nodes
Diffabledatasources619
2 years ago4June 08, 202113apache-2.0Swift
💾 A library for backporting UITableView/UICollectionViewDiffableDataSource.
Editscript423
6 months ago22August 25, 202211epl-1.0Clojure
A library to diff and patch Clojure/ClojureScript data structures
Vim Diff Enhanced332
3 years agoVim script
Better Diff options for Vim
Diff Lcs263214,363323a year ago16December 23, 20215otherRuby
Generate difference sets between Ruby sequences.
Alternatives To Differencekit
Select To Compare


Alternative Project Comparisons
Readme

A fast and flexible O(n) difference algorithm framework for Swift collection. The algorithm is optimized based on the Paul Heckel's algorithm.

Swift5 Release CocoaPods Carthage Swift Package Manager CI Status Platform Lincense


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.

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.

OSS using DifferenceKit

The list of the awesome OSS which uses this library. They also help to understanding how to use DifferenceKit.

Other diffing libraries

I respect and ️❤️ all libraries involved in diffing.


License

DifferenceKit is released under the Apache 2.0 License.

Popular Algorithms Projects
Popular Diff Projects
Popular Computer Science Categories
Related Searches

Get A Weekly Email With Trending Projects For These Categories
No Spam. Unsubscribe easily at any time.
Swift
Algorithms
Diff
Tableview
Collectionview