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, Jul 01 '15 at 15:51
@Mike it is preferable to maintain the order, but not necessary. — David Prieto, Jul 01 '15 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 http://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, Jul 01 '15 at 15:57

antoinestv · Accepted Answer · 2015-07-02T08:39:58.773

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 `+`. — Vladimir, Jul 01 '15 at 18:13
I added a version to be able to use multiple properties as unique keys. — antoinestv, Jul 02 '15 at 08:15

SDekov · Answer 2 · 2015-07-01T16:25:20.497

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 01 '15 at 16:25

answered Jul 01 '15 at 15:57

SDekov

9,276
1
20
50

3

This doesn't return an array of objects. Do you mean something like `_.uniq(data1.concat(data2), false, 'hid')`? – Paolo Moretti Jul 01 '15 at 16:05
Well spotted. Updated accordingly. – SDekov Jul 01 '15 at 16:26

Mike Quinlan · Answer 3 · 2015-07-01T17:07:24.053

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 · Answer 4 · 2015-07-02T08:32:33.767

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

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

4 Answers4