CODEWITHSUNDEEP
javascript
Solo
Solo

Reputation: 6967

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

Given:

How to determine which objects

In this case:

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.

Upvotes: 3

Views: 79

Answers (6)

Abion47
Abion47

Reputation: 24726

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));

Upvotes: 1

hgb123
hgb123

Reputation: 14891

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)

Upvotes: 1

Sascha A.
Sascha A.

Reputation: 4626

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);

Upvotes: 0

JoshG
JoshG

Reputation: 6745

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;}));

Upvotes: 0

Seblor
Seblor

Reputation: 7146

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.

Upvotes: 1

Tatarize
Tatarize

Reputation: 10806

  • 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.

Upvotes: 1

Related Questions