Find differences between two arrays

Question

I have to identify added and deleted items between two objects with the same structure.

function difference(arr1, arr2) {
  return arr1.filter((x) => !arr2.includes(x));
}

function compute_differences(before, after) {
  let result = {
    added: {},
    removed: {},
  };

  const keys = [
    ...new Set(Object.keys(before).concat(Object.keys(after))),
  ].sort();

  for (const key of keys) {
    if (!before[key]) {
      result.added[key] = after[key];
      continue;
    }
    if (!after[key]) {
      result.remove[key] = before[key];
      continue;
    }

    const removed = difference(before[key], after[key]);
    const added = difference(after[key], before[key]);

    if (removed.length) result.removed[key] = removed;
    if (added.length) result.added[key] = added;
  }

  return result;
}

Example usage:

const obj1 = {
  one: [1, 3, 5],
  two: [2, 3, 4],
  three: [5, 7, 8],
};

const obj2 = {
  one: [4, 5, 6],
  two: [1, 2, 3],
  three: [6, 7, 8, 9],
  four: [1, 2],
};
const result = compute_differences(obj1, obj2);

console.log(result);

This yields the expected result:

{
  added: { four: [ 1, 2 ], one: [ 4, 6 ], three: [ 6, 9 ], two: [ 1 ] },
  removed: { one: [ 1, 3 ], three: [ 5 ], two: [ 4 ] }
}

This solution works, but doesn't have a great performance. How could I improve it?

Answer 1

1st improvement: Do you really need the sort on your key array? Not really necessary, is it?

2nd improvement: Given, that your arrays are sorted use a shift approach instead of filtering the whole array.

Result:

function compute_differences(before, after) {
  let result = {
    added: {},
    removed: {},
  };

  const keys = [
    ...new Set(Object.keys(before).concat(Object.keys(after))),
  ];

  for (const key of keys) {
    if (!before[key]) {
      result.added[key] = after[key];
      continue;
    }
    if (!after[key]) {
      result.remove[key] = before[key];
      continue;
    }

    const removed = [];
    const added = [];
      
    // you maybe want to copy before[key] and after[key], since those are altered here
    do {
      if (before[key][0] < after[key][0]){
        removed.push(before[key].shift());   
      }
      else if (before[key][0] > after[key][0]) {
        added.push(after[key].shift());
      }
      else {
        before[key].shift();
        after[key].shift();
      }
    } while(before[key].length && after[key].length);
    
    // add remaining
    removed.push(...before[key]);
    added.push(...after[key]);

    if (removed.length) result.removed[key] = removed;
    if (added.length) result.added[key] = added;
  }

  return result;
}

const obj1 = {
  one: [1, 3, 5],
  two: [2, 3, 4],
  three: [5, 7, 8],
};

const obj2 = {
  one: [4, 5, 6],
  two: [1, 2, 3],
  three: [6, 7, 8, 9],
  four: [1, 2],
};

console.log(compute_differences(obj1, obj2));

Answer 2

First one little detail. Use const result instead of let. You're probably confused there. You're never modifying the result variable, you're modifying the properties of the object stored in that variable. Const is fine there.

Now to your performance problem. Let's define n1 to be the number of keys of the first object. Similarly, n2 for the second object. Let's define n as sum of the two, or in other words maximum possible number of keys of both objects combined. Let's define m as the average length of an array under a key in any of the objects. You can actually think of n as the number of keys of the union and m as mean or maximum too. The performance will in general vary depending on the relations between n, n1, n2 and m. But we can at least come up with an approximation for average case, worst case etc.

To create the array of all keys you need O(n) time and this is probably not a bottleneck.

Then you sort it at cost of O(n log(n)) but that's still probably not bottleneck although it's actually useless unless you want to sort it for the output.

Then we have a for over the keys which means we have O(n) times whatever is inside the for.

There is a bunch of constant complexity checks, we can ignore that.

And then you call difference function which is O(m) for filtering times O(m) for includes check giving you O(m^2) in total for the difference function. And this is probably your problem and it gets worse the larger m then n.

You can easily fix this by converting the arrays to sets which is O(m) and the difference of two sets is also O(m)=O(m1+m2) where m1 and m2 are sizes of the two sets. But here the complexities don't multiply, just sum, giving us complexity of just O(m).

This will reduce the overall complexity from O(nm^2) to O(nm). As usual, this will be negligible or even counterproductive for small m inputs, but it will be the major improvement for large m inputs. You can probably make other improvements but they won't cut down the big-O time complexity any further (at least not for at most O(n) memory cost) and unless targeted on specific input distribution characteristic (ie. targeting large n and small m which may or may not be your case) it will have less significant impact.

// m1 = arr1.length
// m2 = arr2.length
// O(m1 * m2)
// O(1) if arr1 is empty
// O(m1) if arr2 is empty
// combined call to difference(a,b) and difference(b,a) is therefore O(m1+m2) if at least one of the arrays is empty
// and it may even perform better than difference_using_set if one of the arrays is empty (or maybe actually just small) most of the time
function difference(arr1, arr2) {
  return arr1.filter((x) => !arr2.includes(x));
}

// O(m1 + m2) no matter if any of the arrays is empty
// O(m2) if arr1 is empty
// O(m1) if arr2 is empty
function difference_using_set(arr1, arr2) {
  // O(m2)
  const set2 = new Set(arr2)
  // O(m1) * O(1) = O(m1)
  return arr1.filter((x) => !set2.has(x))
}

function compute_differences(before, after) {
  const result = {
    added: {},
    removed: {},
  };

  // n1 = Object.keys(before).length
  // n2 = Object.keys(after).length
  // O(n1+n2)
  const allKeys = Object.keys(before).concat(Object.keys(after))
  // O(n1+n2)
  const allKeysSet = new Set(allKeys)
  // O(n)
  const keys = [...allKeysSet]
  // n = keys.length
  // O(n log(n))
  const sortedKeys = keys.sort()


  // n = keys.length (at most n1+n2)
  // O(n) times complexity of the inner code
  // = O(nm^2) when using difference function
  // = O(nm) when using difference_using_set function
  for (const key of sortedKeys) {
    // O(1)
    if (!before[key] || !before[key].length) {
      // notice added check for empty array because the effect is the same
      // and we avoid call to difference (_using_set) function which would be O(m) as described for empty arrays
      // even beating the advantage of difference function over difference_using_set function when one array is empty

      // O(1)
      result.added[key] = after[key];
      continue;
    }
    // O(1)
    if (!after[key] || !after[key].length) {
      // O(1)
      result.remove[key] = before[key];
      continue;
    }

    // O(m1*m2) ~ O(m^2)
    // const removed = difference(before[key], after[key]);
    // O(m2*m1) ~ O(m^2)
    // const added = difference(after[key], before[key]);

    // O(m1+m2) ~ O(m)
    const removed = difference_using_set(before[key], after[key]);
    // O(m2+m1) ~ O(m)
    const added = difference_using_set(after[key], before[key]);

    // O(1)
    if (removed.length) result.removed[key] = removed;
    // O(1)
    if (added.length) result.added[key] = added;
  }

  return result;
}