How to merge two arrays of objects EFFICIENTLY in JavaScript and filter duplicate items by attribute?

Question

I haven't mastered JavaScript and I want to do the same thing that is in this question (How to merge two arrays in Javascript and de-duplicate items) but with arrays of objects and filtering duplicates based on a unique ID attribute.

I already did it with one of the answers of that question but it is inefficient.

Here is my solution:

var mezclaArreglo = function (array) {
  var a = array.concat();
  for(var i=0; i<a.length; ++i) {
    for(var j=i+1; j<a.length; ++j) {
      if(a[i].hid === a[j].hid)
        a.splice(j--, 1);
    }
  }

  return a;
};

var old = 
  [{ hid: 'MTQzNTc1OTcyMzk1ODI3OTMyMjI3NDcyNzc0Njg0NDI5',
     number: '1',
     payload: { style: 'WebView', type: 'type1' }},
   { hid: 'MTQzNTc1OTczMDA1MDgwMTcwNzg3NjM4MDUzMjk3OTk3',
     number: '2',
     payload: { style: 'WebView', type: 'type1' }},
   { hid: 'MTQzNTc1OTczNDMxNzQ1NDI2NzUwOTA0ODgwNDY0MDc3',
     number: '3',
     payload: { style: 'WebView', type: 'type1' }}
   ];

var newA =
  [{ hid: 'MTQzNTc1OTczNDMxNzQ1NDI2NzUwOTA0ODgwNDY0MDc3',
     number: '3',
     payload: { style: false, type: false }},
   { hid: 'MTQzNTc1OTc0NzcxNDM1MDUyMzA5MzQ4MjQ3OTQ1MzA5',
     number: '4',
     payload: { style: 'WebView', type: 'type1' }}
  ];

// RESULT ARRAY
  [{ hid: 'MTQzNTc1OTcyMzk1ODI3OTMyMjI3NDcyNzc0Njg0NDI5',
     number: '1',
     payload: { style: 'WebView', type: 'type1' }},
   { hid: 'MTQzNTc1OTczMDA1MDgwMTcwNzg3NjM4MDUzMjk3OTk3',
     number: '2',
     payload: { style: 'WebView', type: 'type1' }},
   { hid: 'MTQzNTc1OTczNDMxNzQ1NDI2NzUwOTA0ODgwNDY0MDc3',
     number: '3',
     payload: { style: 'WebView', type: 'type1' }},
   { hid: 'MTQzNTc1OTc0NzcxNDM1MDUyMzA5MzQ4MjQ3OTQ1MzA5',
     number: '4',
     payload: { style: 'WebView', type: 'type1' }}
  ];

I need the duplicated objects to be eliminated from the new array and not from the old array, in the most efficient way possible.

Maybe the solution is to use the filter method like in this answer? (https://stackoverflow.com/a/23080662/4275425) How can I implement that for my problem?

So you need to change var new = because new is a reserved word. Also, do you ned to maintain the order of your results? — Mike Quinlan
– Mike Quinlan, Commented Jul 1, 2015 at 15:51
@Mike it is preferable to maintain the order, but not necessary. — David Prieto
– David Prieto, Commented Jul 1, 2015 at 15:56
ES6 has Set which is what you're looking for I think, checkout this answer especially the sidebar where there's a link to a polyfill and some other prebuilt tools stackoverflow.com/a/7958422/1370442 in your case you could use the hid property as a key and then the object as the value — Luke Baughan
– Luke Baughan, Commented Jul 1, 2015 at 15:57

antoinestv · Accepted Answer · 2015-07-02 08:39:58Z

Your solution complexity is n² when you could use a 3n complexity :

var mergeWithoutDouble = function(array1, array2) {
    var mapHuidElement = {};

    for(var i = 0; i < array1.length; i ++){
        if(!mapHuidElement[array1[i]['huid']]){
            mapHuidElement[array1[i]['huid']] = array1[i];
        }
    }

    for(var i = 0; i < array2.length; i ++){
        if(!mapHuidElement[array2[i]['huid']]){
            mapHuidElement[array2[i]['huid']] = array2[i];
        }
    }

    var arrayMerged = Object.keys(mapHuidElement).map(function (key) {return mapHuidElement[key]});

    return arrayMerged;
}

Note : You could put huid as parameter to make it more generic and i think we can optimise it a little bit too.

Exemple :

mergeWithoutDouble([{huid: 1}, {huid: 3}], [{huid: 2}, {huid: 3}]);

=> [{huid: 1}, {huid: 2}, {huid: 3}]

Edit : With multiple properties as unique key : If we want to use multiple properties as unique key.

var mergeWithoutDouble = function(array1, array2, uniqueKeys) {
    var mapHuidElement = {};

    for(var i = 0; i < Math.max( array1.length, array2.length ) ; i ++){
        var a = i < array1.length,
            b = i < array2.length,
            key;
        if(a){
            key = "";
            for(var k = 0; k < uniqueKeys.length; k++){
                key += uniqueKeys[k]+":"+array1[i][uniqueKeys[k]]+";";
            }
            if(!mapHuidElement[key]){
                mapHuidElement[key] = array1[i];
            }
        } 
        if(b){
            key = "";
            for(var k = 0; k < uniqueKeys.length; k++){
                key += uniqueKeys[k]+":"+array2[i][uniqueKeys[k]]+";";
            }
            if(!mapHuidElement[key]){
                mapHuidElement[key] = array2[i];
            }
        }
    }

    return Object.keys(mapHuidElement).map(function (key) {return mapHuidElement[key]});
}

Example :

mergeWithoutDouble([{huid: 1, name: 'A'}, {huid: 1, name: 'B'}, {huid: 3, name:'A'}], [{huid: 2, name: 'A'}, {huid: 3, name: 'A'}], ['huid', 'name']);

=> [{huid: 1, name: 'A'}, {huid: 1, name: 'B'}, {huid: 3, name:'A'}, {huid: 2, name: 'A'}]

Compact version :

var mergeWithoutDouble=function(t,e,r){for(var n={},a=0;a<Math.max(t.length,e.length);a++){var h,f=a<t.length,g=a<e.length;if(f){h="";for(var l=0;l<r.length;l++)h+=r[l]+":"+t[a][r[l]]+";";n[h]||(n[h]=t[a])}if(g){h="";for(var l=0;l<r.length;l++)h+=r[l]+":"+e[a][r[l]]+";";n[h]||(n[h]=e[a])}}return Object.keys(n).map(function(t){return n[t]})};

Let's now see the performances :

2 arrays of 10 000 elements, 10 repetitions (1 key : huid).

On my machine
versionAntoinev1: 15.000ms
versionAntoinev2: 54.000ms
versionVladimir: 1749.000ms

That's why it is important to avoid n² complexity.

Plunker

I agree, writing array to object is faster way, but what if you need to merge not only with id? So my solution is more compact and extensible. But giving you a +.
I added a version to be able to use multiple properties as unique keys.

SD. · Accepted Answer · 2015-07-01 16:25:20Z

1

UPDATED as per @Paolo Moretti 's comment.

Take a look at underscore.js

A simple and efficient solution is to use _.uniq like this

_.uniq(data1.concat(data2), false, 'hid')

See this DEMO.

edited Jul 1, 2015 at 16:25

answered Jul 1, 2015 at 15:57

SD.

9,6071 gold badge27 silver badges57 bronze badges

2 Comments

Paolo Moretti Over a year ago

This doesn't return an array of objects. Do you mean something like _.uniq(data1.concat(data2), false, 'hid')?

SD. Over a year ago

Well spotted. Updated accordingly.

Mike Quinlan · Accepted Answer · 2015-07-01 17:07:24Z

First, I love problems like this so thanks for asking. I like to think of this as a hash collision problem (where the hid is the "hash"). You could make a function that looks like this:

function mergeWithoutDups() {
  var merged = [],
    map = {};
  for(var i = 0; i < arguments.length; i++) {
    for(var j = 0; j < array.length; j++) {
      var item = array[j];
      var hid = item.hid;

      if(!map[hid]) {
        map[hid] = true;
        merged.push(item);
      }
    }
  }

  return merged;
}

Basically what this does is makes the unique identifier the key of an arbitrary map object and lets us know internally that an object with the same hid has been placed in the array. If an object with a certain hid hasn't been placed then it's pushed into the resulting array and the map object is updated to reflect the change. This function also allows for an arbitrary number of arrays to be passed to it:

mergeWithoutDups(ar1, ar2, ar3, ar4, ...)

The result is an array where order is maintained and items within are unique by the hid. Also, it should be performant due to the fact that all arrays are iterated over exactly once. Note: You should call it with newer arrays being at the front of the argument list if you want newer items to take precedence over older ones. e.g.

mergeWithoutDups(newArray, oldArray)

In regard to @Stoyan's response though, Underscore.js is widely supported and probably has a fairly optimized uniq function. I would suggest using that if your project allows for it.

Cheers!

Vladimir · Accepted Answer · 2015-07-02 08:32:33Z

function merge(o, n) {
  return n.concat(o).filter(function(x, i, all) {
    return !all.some(function(y, j) {
      return x.hid == y.hid && j > i;
    });
  });
}

var old = [{
  hid: 'MTQzNTc1OTcyMzk1ODI3OTMyMjI3NDcyNzc0Njg0NDI5',
  number: '1',
  payload: {
    style: 'WebView',
    type: 'type1'
  }
}, {
  hid: 'MTQzNTc1OTczMDA1MDgwMTcwNzg3NjM4MDUzMjk3OTk3',
  number: '2',
  payload: {
    style: 'WebView',
    type: 'type1'
  }
}, {
  hid: 'MTQzNTc1OTczNDMxNzQ1NDI2NzUwOTA0ODgwNDY0MDc3',
  number: '3',
  payload: {
    style: 'WebView',
    type: 'type1'
  }
}];

var ne = [{
  hid: 'MTQzNTc1OTczNDMxNzQ1NDI2NzUwOTA0ODgwNDY0MDc3',
  number: '3',
  payload: {
    style: false,
    type: false
  }
}, {
  hid: 'MTQzNTc1OTc0NzcxNDM1MDUyMzA5MzQ4MjQ3OTQ1MzA5',
  number: '4',
  payload: {
    style: 'WebView',
    type: 'type1'
  }

}];

document.write('<pre>' + JSON.stringify(merge(ne, old), null, '\t') + '</pre>');

Collectives™ on Stack Overflow

How to merge two arrays of objects EFFICIENTLY in JavaScript and filter duplicate items by attribute?

4 Answers 4

2 Comments

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related