Javascript: Merge Two Arrays of Objects, Only If Not Duplicate (Based on Specified Object Key)

Question

Background

Say I have an initial array of objects:

var initialData = [
    {
        'ID': 1,
        'FirstName': 'Sally'
    },
    {
        'ID': 2,
        'FirstName': 'Jim'
    },
    {
        'ID': 3,
        'FirstName': 'Bob'
    }
];

I then get new data (another array of objects):

var newData = [
    {
        'ID': 2,
        'FirstName': 'Jim'
    },
    {
        'ID': 4,
        'FirstName': 'Tom'
    },
    {
        'ID': 5,
        'FirstName': 'George'
    }
];

Goal

I want to merge the new data into initial data. However, I don't want to overwrite any objects in the initial data array. I just want to add in objects that weren't already there.

I know the objects are duplicates based on their 'ID' key.

What I've Tried

I know I can do this by looping through the new data, checking to see if it exists in the initial data, and if not, pushing into initial data.

for ( var i = 0, l = newData.length; i < l; i++  ) {

    if ( ! key_exists( newData[i].key, initialData ) ) {  // key_exists() is a function that uses .filter() to test.

        initialData.push( newData[i] );

    }


}

I'm concerned about performance, though. I know there are lots of new ES6 ways of manipulating arrays, so I'm hoping someone has a better idea.

Question

What is the best way (best as in best performance) of merging the new data into the initial data, while ignoring duplicates in new data?

This isn't really duplicate question, because in that question, when there are two duplicate objects, they want to be merged. In my case, when there are duplicate objects, I want to drop the new one. — Kelderic, Jan 10 '19 at 17:48
Are you assured any ordering with respect to IDs? That could reduce looping as you could optimize the search and make decisions based on the `id` of the current object. Even if not, a simple ordering can be applied prior to looping. — Nick, Jan 10 '19 at 17:49
@Nick, I am not assured ordering. 99% of the time, the order will be different. — Kelderic, Jan 10 '19 at 17:51
I seem to have flagged the wrong ones and I have to nip away so I voted to reopen, but this is **definitely** ground that's been thoroughly covered in previous questions. The usual solution is to build a Map (or object-as-map). I just don't have an example to hand and have to disappear. — T.J. Crowder, Jan 10 '19 at 17:52
@T.J.Crowder, I did look at existing questions before I posted, but all the ones I found just ended up merging the duplicate objects, rather than dropping if duplicate. I may have missed it, though. Apologies if that is the case, and thanks for helping flag things. — Kelderic, Jan 10 '19 at 17:53

slider · Accepted Answer · 2019-01-10T17:51:45.417

88

You can create a set of IDs from initialData and this will make "check if ID is already in initial data" faster - O(1):

var initialData = [{
    'ID': 1,
    'FirstName': 'Sally'
  },
  {
    'ID': 2,
    'FirstName': 'Jim'
  },
  {
    'ID': 3,
    'FirstName': 'Bob'
  }
];

var newData = [{
    'ID': 2,
    'FirstName': 'Jim'
  },
  {
    'ID': 4,
    'FirstName': 'Tom'
  },
  {
    'ID': 5,
    'FirstName': 'George'
  }
];

var ids = new Set(initialData.map(d => d.ID));
var merged = [...initialData, ...newData.filter(d => !ids.has(d.ID))];

console.log(merged);

The final runtime of this approach is O(n + m).

If you want to be slightly more efficient, you can consider looping through newData and pushing any new elements to the final result array manually (instead of using filter and the spread operator).

edited Jan 10 '19 at 17:51

answered Jan 10 '19 at 17:45

slider

12,810
1
26
42

2

Nit: Another possible performance improvement would be using concat instead of spreading. There is info that concat is a little bit faster. https://stackoverflow.com/questions/48865710/spread-operator-vs-array-concat – GreenTeaCake Jan 10 '19 at 17:56
Thanks! Follow up question about your answer, what is the reason for creating a `Set` rather than an `Array` of the `ids`? – Kelderic Jan 10 '19 at 18:22
@AndyMercer With a `Set`, the check for whether or not an ID is in it (`ids.has(d.ID)`) is constant time. Whereas in an array, it would be linear time (`includes` or `filter` will have to go through each element in the list). This advantage of `Set` is essential in this case to improve efficiency. – slider Jan 10 '19 at 18:54
Nice succinct answer, but I had a time of this working out why it was not combining the data! I found I had to `return` the callback on the filter `var ids = new Set(initialData.map(d => d.ID)); var merged = [...initialData, ...newData.filter(d => return !ids.has(d.ID))]; console.log(merged); ` – Beerswiller May 13 '21 at 01:57
@Beerswiller that should not be necessary as in arrow functions when you don't use the curly braces, the return is implied: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/Arrow_functions#comparing_traditional_functions_to_arrow_functions – slider May 13 '21 at 14:48
1

@slider thanks for the heads up on the `{ }`. The code I'm working on has a slightly different flow and my merged array was missing all the newData until I returned the filter arrow function, as my code had braces! Always learning. – Beerswiller May 14 '21 at 00:32

score 3 · Answer 2 · answered Jan 11 '19 at 02:44

Actually, if you are interested on performance, you could think on changing your initialData structure to something like this:

var initialData = {
    "1": {'FirstName': 'Sally'},
    "2": {'FirstName': 'Jim'},
    "3": {'FirstName': 'Bob'}
};

In other words, we use the IDs as the keys of an object, this will give you O(1) on access the data, and O(1) in the exists test. You can get this structure using the next approach with reduce():

var initialData = [
    {'ID': 1, 'FirstName': 'Sally'},
    {'ID': 2, 'FirstName': 'Jim'},
    {'ID': 3, 'FirstName': 'Bob'}
];

let newInitialData = initialData.reduce((res, {ID, FirstName}) =>
{
    res[ID] = {FirstName : FirstName};
    return res;
}, {});

console.log(newInitialData);

Using this new structure, you can make a O(n) algorithm to insert the new data that is not already there:

var initialData = {
    "1": {'FirstName': 'Sally'},
    "2": {'FirstName': 'Jim'},
    "3": {'FirstName': 'Bob'}
};

var newData = [
    {'ID': 2, 'FirstName': 'Jim'},
    {'ID': 4, 'FirstName': 'Tom'},
    {'ID': 5, 'FirstName': 'George'}
];

newData.forEach(({ID, FirstName}) =>
{
    initialData[ID] = initialData[ID] || {FirstName: FirstName};
});

console.log(initialData);

I like this, but I'm not sure how it would impact the sorting that I'm doing (which is out of scope for the initial question). I resort relatively frequently using `Array.sort()`, which wouldn't work (I think) if I mutate the array into an object. — Kelderic, Jan 11 '19 at 14:33
Objects can't be sorted, you will have to convert it again to an array before sorting. Like a general rule, your data structure should be optimized for the type of operations you are using more often on it. — Shidersz, Jan 11 '19 at 15:04

score 0 · Answer 3 · answered Jun 30 '20 at 02:22

I think the alternative solution proposed by @slider in the accepted answer, would be something like this:

const oldData = [
  { id: 1, name: 'John' },
  { id: 2, name: 'Jane' },
  { id: 3, name: 'Mike' },
];

const newData = [
  { id: 2, name: 'Jane' },
  { id: 4, name: 'Rick' },
  { id: 5, name: 'Jim' },
];

const usersMap = new Map();

oldData.forEach(user => usersMap.set(user.id, user));

newData.forEach(user => {
  const exists = usersMap.has(user.id);
  
  if (!exists) {
    usersMap.set(user.id, user);
  }
})

usersMap.forEach(user => console.log(user))

Javascript: Merge Two Arrays of Objects, Only If Not Duplicate (Based on Specified Object Key)

Background

Goal

What I've Tried

Question

3 Answers3

Linked