Name: DeepDiff
Owner: Wire Swiss GmbH
Description: ? Very fast diffing in Swift
Created: 2018-05-08 14:58:57.0
Updated: 2018-05-08 14:58:59.0
Pushed: 2018-04-12 07:40:15.0
Size: 7314
Language: Swift
GitHub Committers
User | Most Recent Commit | # Commits |
---|
Other Committers
User | Most Recent Commit | # Commits |
---|
DeepDiff tells the difference between 2 collections and the changes as edit steps. It works on any collection of Equatable
and Hashable
items.
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 indexBy 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
old = Array("abc")
new = Array("bcd")
changes = diff(old: old, new: new)
elete "a" at index 0
nsert "d" at index 2
wift
old = Array("abcd")
new = Array("adbc")
changes = diff(old: old, new: new)
ove "d" from index 3 to index 1
wift
old = [
ty(name: "New York"),
ty(name: "Imagine City"),
ty(name: "London")
new = [
ty(name: "New York"),
ty(name: "Oslo"),
ty(name: "London"),
changes = diff(old: old, new: new)
eplace "Imagine City" with "Oslo" at index 1
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.
oldItems = items
s = DataSet.generateNewItems()
changes = diff(old: oldItems, new: items)
ectionView.reload(changes: changes, section: 2, completion: { _ in })
Take a look at Demo where changes are made via random number of items, and the items are shuffled.
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
Hashable
to quickly check that 2 items are not equalThe 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.
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
deleteOffset
There are other algorithms that are interesting
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
Here are several popular diffing frameworks to compare
? From 2000 items to 2100 items (100 deletions, 200 insertions)
(old, new) = generate(count: 2000, removeRange: 100..<200, addRange: 1000..<1200)
hmark(name: "DeepDiff", closure: {
= DeepDiff.diff(old: old, new: new)
hmark(name: "Dwifft", closure: {
= Dwifft.diff(old, new)
hmark(name: "Changeset", closure: {
= Changeset.edits(from: old, to: new)
hmark(name: "Differ", closure: {
= old.diffTraces(to: new)
hmark(name: "ListDiff", closure: {
= ListDiff.List.diffing(oldArray: old, newArray: new)
Result
Diff: 0.0450611114501953s
er: 0.199673891067505s
ft: 149.603884935379s
geset: 77.5895738601685s
Diff: 0.105544805526733s
Here is how DeepDiff
handles large number of items and changes
? From 10000 items to 11000 items (1000 deletions, 2000 insertions)
Diff: 0.233131170272827s
? From 20000 items to 22000 items (2000 deletions, 4000 insertions)
Diff: 0.453393936157227s
? From 50000 items to 55000 items (5000 deletions, 10000 insertions)
Diff: 1.04128122329712s
? From 100000 items to 1000000 items
you sure?
DeepDiff is available through CocoaPods. To install it, simply add the following line to your Podfile:
'DeepDiff'
DeepDiff is also available through Carthage. To install just write into your Cartfile:
ub "onmyway133/DeepDiff"
DeepDiff can also be installed manually. Just download and drop Sources
folders in your project.
Khoa Pham, onmyway133@gmail.com
We would love you to contribute to DeepDiff, check the CONTRIBUTING file for more info.
DeepDiff is available under the MIT license. See the LICENSE file for more info.