DeepDiff alternatives and similar libraries
Based on the "Data Structures / Algorithms" category.
Alternatively, view DeepDiff alternatives based on common mentions on social networks and blogs.
-
KeyPathKit
KeyPathKit is a library that provides the standard functions to manipulate data along with a call-syntax that relies on typed keypaths to make the call sites as short and clean as possible. -
BinaryKit
💾🔍🧮 BinaryKit helps you to break down binary data into bits and bytes, easily access specific parts and write data to binary. -
RandMyMod
RandMyMod base on your own struct or class create one or a set of instance, which the variable's value in the instance is automatic randomized. -
OneWaySynchronizer
The simplest abstraction to synchronize local data with remote source. For iOS, wirtten in swift.
CodeRabbit: AI Code Reviews for Developers
* 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 DeepDiff or a related project?
README
DeepDiff
❤️ Support my apps ❤️
- Push Hero - pure Swift native macOS application to test push notifications
- PastePal - Pasteboard, note and shortcut manager
- Quick Check - smart todo manager
- Alias - App and file shortcut manager
- My other apps
❤️❤️😇😍🤘❤️❤️
[](Screenshots/Banner.png)
DeepDiff tells the difference between 2 collections and the changes as edit steps. It also supports Texture, see Texture example
- Read more A better way to update UICollectionView data in Swift with diff framework
- Checkout Micro Fast diffing and type safe SwiftUI style data source for UICollectionView
Usage
Basic
The result of diff
is an array of changes, which is [Change]
. A Change
can be
.insert
: The item was inserted at an index.delete
: The item was deleted from an index.replace
: The item at this index was replaced by another item.move
: The same item has moved from this index to another index
By default, there is no .move
. But since .move
is just .delete
followed by .insert
of the same item, it can be reduced by specifying reduceMove
to true
.
Here are some examples
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
let old = Array("abcd")
let new = Array("adbc")
let changes = diff(old: old, new: new)
// Move "d" from index 3 to index 1
let old = [
User(id: 1, name: "Captain America"),
User(id: 2, name: "Captain Marvel"),
User(id: 3, name: "Thor"),
]
let new = [
User(id: 1, name: "Captain America"),
User(id: 2, name: "The Binary"),
User(id: 3, name: "Thor"),
]
let changes = diff(old: old, new: new)
// Replace user "Captain Marvel" with user "The Binary" at index 1
DiffAware protocol
Model must conform to DiffAware
protocol for DeepDiff to work. An model needs to be uniquely identified via diffId
to tell if there have been any insertions or deletions. In case of same diffId
, compareContent
is used to check if any properties have changed, this is for replacement changes.
public protocol DiffAware {
associatedtype DiffId: Hashable
var diffId: DiffId { get }
static func compareContent(_ a: Self, _ b: Self) -> Bool
}
Some primitive types like String
, Int
, Character
already conform to DiffAware
Animate UITableView and UICollectionView
Changes to DataSource
can be animated by using batch update, as guided in Batch Insertion, Deletion, and Reloading of Rows and Sections
Since Change
returned by DeepDiff
follows the way batch update works, animating DataSource
changes is easy.
For safety, update your data source model inside updateData
to ensure synchrony inside performBatchUpdates
let oldItems = items
let newItems = DataSet.generateNewItems()
let changes = diff(old: oldItems, new: newItems)
collectionView.reload(changes: changes, section: 2, updateData: {
self.items = newItems
})
Take a look at Demo where changes are made via random number of items, and the items are shuffled.
How does it work
Wagner–Fischer
If you recall from school, there is Levenshtein distance which counts the minimum edit distance to go from one string to another.
Based on that, the first version of DeepDiff
implements Wagner–Fischer, which uses dynamic programming to compute the edit steps between 2 strings of characters. DeepDiff
generalizes this to make it work for any collection.
Some optimisations made
- Check empty old or new collection to return early
- Use
diffId
to quickly check that 2 items are not equal - Follow "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." to use 2 rows, instead of matrix to reduce memory storage.
The performance greatly depends on the number of items, the changes and the complexity of the equal
function.
Wagner–Fischer algorithm
has O(mn) complexity, so it should be used for collection with < 100 items.
Heckel
The current version of DeepDiff
uses Heckel algorithm as described in A technique for isolating differences between files. It works on 2 observations about line occurrences and counters. The result is a bit lengthy compared to the first version, but it runs in linear time.
Thanks to
- Isolating Differences Between Files for explaining step by step
- HeckelDiff for a clever move reducer based on tracking
deleteOffset
More
There are other algorithms that are interesting
Benchmarks
Benchmarking is done on real device iPhone 6, with random items made of UUID strings (36 characters including hyphens), just to make comparisons more difficult.
You can take a look at the code Benchmark. Test is inspired from DiffUtil
Among different frameworks
Here are several popular diffing frameworks to compare
💪 From 2000 items to 2100 items (100 deletions, 200 insertions)
let (old, new) = generate(count: 2000, removeRange: 100..<200, addRange: 1000..<1200)
benchmark(name: "DeepDiff", closure: {
_ = DeepDiff.diff(old: old, new: new)
})
benchmark(name: "Dwifft", closure: {
_ = Dwifft.diff(old, new)
})
benchmark(name: "Changeset", closure: {
_ = Changeset.edits(from: old, to: new)
})
benchmark(name: "Differ", closure: {
_ = old.diffTraces(to: new)
})
benchmark(name: "ListDiff", closure: {
_ = ListDiff.List.diffing(oldArray: old, newArray: new)
})
Result
DeepDiff: 0.0450611114501953s
Differ: 0.199673891067505s
Dwifft: 149.603884935379s
Changeset: 77.5895738601685s
ListDiff: 0.105544805526733s
[](Screenshots/benchmark3d.png)
Increasing complexity
Here is how DeepDiff
handles large number of items and changes
💪 From 10000 items to 11000 items (1000 deletions, 2000 insertions)
DeepDiff: 0.233131170272827s
💪 From 20000 items to 22000 items (2000 deletions, 4000 insertions)
DeepDiff: 0.453393936157227s
💪 From 50000 items to 55000 items (5000 deletions, 10000 insertions)
DeepDiff: 1.04128122329712s
💪 From 100000 items to 1000000 items
Are you sure?
Installation
CocoaPods
Add the following to your Podfile
pod 'DeepDiff'
Carthage
Add the following to your Cartfile
github "onmyway133/DeepDiff"
Swift Package Manager
Add the following to your Package.swift file
.package(url: "https://github.com/onmyway133/DeepDiff.git", .upToNextMajor(from: "2.3.0"))
DeepDiff can also be installed manually. Just download and drop Sources
folders in your project.
Author
Khoa Pham, [email protected]
Contributing
We would love you to contribute to DeepDiff, check the CONTRIBUTING file for more info.
License
DeepDiff is available under the MIT license. See the LICENSE file for more info.
*Note that all licence references and agreements mentioned in the DeepDiff README section above
are relevant to that project's source code only.