40

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?

5
  • 1
    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, 2019 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, 2019 at 17:49
  • @Nick, I am not assured ordering. 99% of the time, the order will be different.
    – Kelderic
    Jan 10, 2019 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. Jan 10, 2019 at 17:52
  • 1
    @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, 2019 at 17:53

3 Answers 3

89

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

6
  • 2
    Nit: Another possible performance improvement would be using concat instead of spreading. There is info that concat is a little bit faster. stackoverflow.com/questions/48865710/… Jan 10, 2019 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, 2019 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, 2019 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); May 13, 2021 at 1:57
  • 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. May 14, 2021 at 0:32
3

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

2
  • 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, 2019 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, 2019 at 15:04
0

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

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.