[New Algorithm] Adding Myers Difference Algorithm#693
[New Algorithm] Adding Myers Difference Algorithm#693kelvinlauKL merged 10 commits intokodecocodes:masterfrom horita-yuya:master
Conversation
|
This is a reference. Thank you 🙏 |
kelvinlauKL
left a comment
There was a problem hiding this comment.
I love the well-commented code 👍
So far, I've done a partial read through and left a comment on how the MDA generates the edit graph. Could you address that?
Myers Difference Algorithm/README.md
Outdated
|
|
||
| Myers Difference Algorithm is an algorithm that finds a longest common subsequence or shortest edit scripts (LCS/SES dual probrem) of two sequences. MDA can accomplish this in O(ND) time, where N is the sum of the lengths of the two sequences. The common subsequence of two sequences is the sequence of elements that appear in the same order in both sequences. The edit scripts will be discussed below. | ||
|
|
||
| For example, assuming that sequence `A = ["1", "2", "3"]` and sequence `B = ["2", "3", "4"]`, `["2"], ["2", "3"]` are common sequences. Furthermore, the latter `["2", "3"]` is the longest common subsequence. But `["1", "2"], ["3", "2"]` are not. Because, `["1", "2"]` contains `"1"` that is not included in `B`, `["3", "2"]` has elements are included in both, but the appearing order is not correct. |
There was a problem hiding this comment.
This paragraph doesn't make sense. Could you reword it?
| Y = [C, B, A, B, A, C] | ||
| ``` | ||
|
|
||
| MDA generates the edit graph through the following steps: |
There was a problem hiding this comment.
These steps are hard to understand. It seems worthwhile to explain what the blue line, green dots, dotted lines, and red number represents, just to give the reader more context before diving into the steps.
There was a problem hiding this comment.
Thank you for reviewing.
Yes, it is necessary. Understanding edit graph is important for understanding MDA.
I'll add more explanation 👍
|
It just occurred to me that we have an article on finding the longest common subsequence already: https://github.com/raywenderlich/swift-algorithm-club/tree/master/Longest%20Common%20Subsequence Could you check it out to see if it makes sense to add your ideas to the current topic? |
|
I have known that there is an article for finding the LCS. (https://github.com/raywenderlich/swift-algorithm-club/tree/master/Longest%20Common%20Subsequence) My topic, or MDA is faster than this algorithm. It runs for loop twice like below. for i in self.characters {
for j in other.characters {
}
}I takes O(N * M) times for the worst case 😱 |
|
One more, the LCS algorithm can get only LCS. This may make it easy that , for example, difference refreshing for UITableView or UICollectionView. |
|
@kelvinlauKL and I added some explanation about figure. |
|
Please 🙏 |
|
Anything else is required? |
kelvinlauKL
left a comment
There was a problem hiding this comment.
Sorry for the wait! I took a look at this and ran this code on Swift 5. Runs as expected on Xcode 10.2.
Merging!
Checklist
Description
It seems that some algorithm finding shortest edit script are included in this. This Myers algorithm is same type algorithm. It improves calculation time and space, but simple.
Android's DiffUtil are implemented by Myers Algorithm. So it is practical.
To understand the mechanism is good and I hope this PR supports for that.
I also add the description about Edit Graph, it is useful for understand Myers Algorithm.
Thank you.