search

cujojs / jiff

JSON Patch and diff based on rfc6902
Other
627 stars 41 forks source link

Improve LCS #7

Open briancavalier opened 10 years ago

briancavalier commented 10 years ago

The LCS algorithm for array diffing works well, but could be made more efficient by combining the lcs construction and the subsequent reduce, and by returning early in cases where it's not necessary to create the lcs matrix:

  1. Two passes are done on the common prefix. Could be reduced to 1 pass if lcs() and reduce() are combined.
  2. The LCS matrix construction can be skipped entirely when the common prefix + suffix length === a.length or b.length (or both). When:
    1. prefix+suffix length === a.length === b.length, can return immediately. No work to do.
    2. prefix+suffix length === a.length, can emit remaining span of b as additions
    3. prefix+suffix length === b.length, can emit remaining span of a as removals