1
$\begingroup$

in the past few days I've been working on a diff algorithm for a UI library I'm working on.

My use case only target lists with unique elements.

The main goal is to find the minimum amount of operations needed to transform list A into list B.

Here you can find the current version of the algo:
https://github.com/cruijs/crui/blob/diff/packages/reactive/rx/list/diff/generic/index.ts

It's in typescript. In case you are not familiar with it, here is a rough explanation:

  • Build an index Map for both A and B, where key is the list's item and value is the index position in the list
  • Initialise two sets:
    • one for elements we'll need to add later
    • one for elements we'll need to remove later
  • Compare elements from list A and B

    • both elements match: move both forward
    • element doesn't exist in list A or is in set shouldAdd
      • add it
      • move to next B
    • element doesn't exist in list B or is in set shouldRemove
      • remove it
      • move to next A
    • otherwise:

      • given a the current element in A
      • given b the current element in B
      • di = distance in B between b and a.
      • dj = distance in A between a and b.

      • if di >= dj (element b is closer in A and could possibly require no change):

        • remove a
        • add it in shouldAdd
        • move to next A
      • else:

        • add b
        • add it in shouldRemove
        • move to next B
  • If we add all elements of B, then A and B have nothing in common

    • early return with a full Replace
  • If there are items unchecked at the end of A
    • remove all of them
  • If there are items unchecked at the end of B
    • add all of them
  • Squash all remove and add operations to be more efficient

All in all, this should be a O(n+m) complexity in both space and time, where n is the initial list size while m is the target list size.

I wonder, is there a more efficient or elegant solution?

Allowed operations are:

  • Insert one or more elements at index i:
    • given [1, 2, 3]
    • when insert [6, 7] at index 1
    • then [1, 6, 7, 2, 3]
  • Remove one or more elements at index i:
    • given [1, 6, 7, 2, 3]
    • when remove 2 elements at index 1
    • then [1, 2, 3]
  • Insert & Remove elements at index i:
    • given [1, 2, 3]
    • when insert [6, 7] and remove 1 elements at index 1
    • then [1, 6, 7, 3]
  • Replace list:
    • given [1, 2, 3]
    • replace with [4, 5, 6]
    • then [4, 5, 6]
  • Replace single element at index i:
    • given [1, 2, 3]
    • replace with 1 at index 2
    • then [1, 2, 1]

Current algorithm do not use the single item replace and initially produce just remove and insert, which then tries to collapse as much as possible.

Thanks to everybody who will take time to review it :)

$\endgroup$
  • 2
    $\begingroup$ What is $n$? What is $m$? What operations are allowed to transform a list? $\endgroup$ – orlp Aug 1 at 23:42
  • $\begingroup$ Why not go with the classic algorithm for computing the Levenshtein distance instead of having to use a thousand different maps and sets? $\endgroup$ – Tassle Aug 2 at 22:07
  • $\begingroup$ @Tassle Please correct me if I'm wrong, but Levenshtein distance have an algo complexity in both time and space of O(n*m), while this algorithm is O(n+m), where n is the size of the initial list and m is the size of the target/desired list. $\endgroup$ – Iazel Aug 3 at 8:38
  • $\begingroup$ @orlp thanks for asking, I'll add this info in the main post. Anyway, n is the initial list size, while m is the target list size. Operations allowed are: * Insert one or more elements at $i-th$ position * Delete one or more elements at $i-th$ position * Insert and delete elements at $i-th$ position (eg: delete 3 elements at position 0 and also add another two elements) * Replace all elements of the list with a new list * Replace a single element at $i-th$ position The algorithm currently do not use the single element replace, but try to merge operations at the end. $\endgroup$ – Iazel Aug 3 at 8:44
  • $\begingroup$ One thing that I forgot mention is that this algorithm (and the use case I've develop it for) only works with lists that have unique elements. $\endgroup$ – Iazel Aug 3 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.