Diffing 2 arrays, i.e which items to add and remove

user_5383767 0
Viewed 67

Given:

  • array of "current" objects [{id: '1'},{id: '2'},{id: '3'},{id: '4'},{id: '5'}]
  • array of "new" objects [{id: '1'},{id: '5'},{id: '6'},{id: '7'},{id: '8'}]

How to determine which objects

  • to add (not in "current") and
  • to remove (not in "new")?

In this case:

  • {id: '2'},{id: '3'},{id: '4'} should be removed
  • {id: '6'},{id: '7'},{id: '8'} should be added

Performance is not extremely important, my dataset is usually around 200.

Edit: I need to know about elements to be added/removed because "current" array correlates to DOM nodes and I don't just want to delete them all and add from scratch - already tried that and performance is far from perfect.

javascript
6 Answers
  • For each item in current that is not found in new. That item is deleted.
  • For each item in new that is not in current. That item is added.

You run the run these checks in two different loops one after the other.

user_6319110

You could use Set data structure to calculate the different and filter the expeced values (using its has method). Time complexity for this approach will be linear (O(n))

Set use hash table so complexity for retrival/lookup is O(1) (doc, Theory > Lookup Speed)

const prev = [{ id: "1" }, { id: "2" }, { id: "3" }, { id: "4" }, { id: "5" }] // length n
const current = [
  { id: "1" },
  { id: "5" },
  { id: "6" },
  { id: "7" },
  { id: "8" },
] // length m

const prevIdSet = new Set(prev.map((o) => o.id)) // O(n)
const currentIdSet = new Set(current.map((o) => o.id)) // O(m)

function difference(setA, setB) {
  let _difference = new Set(setA)
  for (let elem of setB) {
    _difference.delete(elem)
  }
  return _difference
}

const removedIdSet = difference(prevIdSet, currentIdSet) // O(m)
const addedIdSet = difference(currentIdSet, prevIdSet) // O(n)

const removed = prev.filter((o) => removedIdSet.has(o.id)) // O(n)
const added = current.filter((o) => addedIdSet.has(o.id)) // O(m)

console.log("removed", removed)
console.log("added", added)

// Total complexity O(constantA * n + constantB * m) ~ O(n + m)

user_66551600

You could go with something like this :

const currentElements = [{id: '1'},{id: '2'},{id: '3'},{id: '4'},{id: '5'}]

const newElements = [{id: '1'},{id: '5'},{id: '6'},{id: '7'},{id: '8'}]

const elementsToAdd = newElements.filter(e1 => !currentElements.find(e2 => e2.id === e1.id))
const elementsToRemove = currentElements.filter(e1 => !newElements.find(e2 => e2.id === e1.id))

console.log({elementsToAdd, elementsToRemove})

Basically, I take an array, and find the elements not contained in the other array.

For the elements to add, check the elements in newElements that are not in currentElements, and vice versa.

user_36701320

In both cases, this is a classic use case of the set operation "difference". All you need to do is define a difference function, and then apply it with current.difference(new) and new.difference(current).

function difference(a, b, compare) {
  let diff = [];
  for (let ai = 0; ai < a.length; ai++) {
    let exists = false;
    for (let bi = 0; bi < b.length; bi++) {
      if (compare(a[ai], b[bi])) {
        exists = true;
        break;
      }
    }
    if (!exists) diff.push(a[ai]);
  }

  return diff;
}

function getRemoved(oldA, newA) {
  return difference(oldA, newA, (a, b) => a.id == b.id);
}

function getAdded(oldA, newA) {
  return difference(newA, oldA, (a, b) => a.id == b.id);
}

let current = [{id: '1'}, {id: '2'}, {id: '3'}, {id: '4'}, {id: '5'}];
let newArr = [{id: '1'}, {id: '5'}, {id: '6'}, {id: '7'}, {id: '8'}];

console.log(getRemoved(current, newArr));
console.log(getAdded(current, newArr));

user_12558730

You could use filter. Something like this for items to remove:

arr1.filter(function(i) {return arr2.indexOf(i) < 0;});

And swap the arrays for items to add. For example:

let arr1 = [{id: '1'},{id: '2'},{id: '3'},{id: '4'},{id: '5'}];
let arr2 = [{id: '1'},{id: '5'},{id: '6'},{id: '7'},{id: '8'}];

arr1 = arr1.map((obj) => obj.id);
arr2 = arr2.map((obj) => obj.id);

console.log("Remove these IDs: ", arr1.filter(function(i) {return arr2.indexOf(i) < 0;}));
console.log("Add these IDs: ", arr2.filter(function(i) {return arr1.indexOf(i) < 0;}));

user_9271720

You you only needs the ids: You could extract the ids with flatMap and than filter with every for not incudes.

let old = [{id: '1'},{id: '2'},{id: '3'},{id: '4'},{id: '5'}];
let act = [{id: '1'},{id: '5'},{id: '6'},{id: '7'},{id: '8'}];

let oldIds = old.flatMap(el => el.id);
let actIds = act.flatMap(el => el.id);

let add = actIds.filter(id => oldIds.every(old=> !old.includes(id)));
let del = oldIds.filter(id => actIds.every(act=> !act.includes(id)));
console.log('Add: ', add);
console.log('Del: ', del);

user_53245110
Related