Most efficient way to merge two arrays of objects

Question

I've already solved this out. However I'm looking for a faster solution since my variables has thousands of objects.

I have two arrays like this:

var full = [{a:'aa1',b:'bb1'},{a:'aa3',b:'bb2'},{a:'aa3',b:'bb3'},{a:'aa2',b:'bb3'}],
some = [{a:'aa1',b:'bb1'},{a:'aa3',b:'bb3'}];

I'm trying to flag in a new attribute called c in full if the object exist on some. Expected result:

 [{a:'aa1',b:'bb1',c:true},{a:'aa3',b:'bb2'},{a:'aa3',b:'bb3',c:true},{a:'aa2',b:'bb3'}]

Some important tips:

some always has less elements than full
both arrays are sorted equal

My current approach is:

var getIndexByAB = function(arr, a,b){
     var initialIndex =  getIndexByAB.initialIndex || 0,
     len = arr.length;
     for(initialIndex; initialIndex < len ;initialIndex++ ){
         var el = arr[initialIndex];
         if( el.b === b && el.a === a ){
             getIndexByAB.initialIndex = initialIndex;
             return initialIndex;
         }
     }
     return -1;
}

var len = some.length;
for(var i = 0; i < len ; i++){
 var el=some[i],
 index = getIndexByAB(full,el.a,el.b);
 if(index > -1) full[index].c = true;
}

UPDADE: original solution improved using Juan comment.

Ruan Mendes · Accepted Answer · 2013-02-21T21:44:44.870

Since they are sorted, you can just pass an index to start the search from, that will avoid the O(n^2). You were already doing it, but by storing the index in a global variable. Instead, you should pass it as an argument to getIndexByAB.

function getIndexByAB(arr, a,b , initialIndex){
    // Was tracking last index by storing it in a global 'this.initialIndex'. 
    // 'this' points to 'window' in global functions. That's bad, it 
    // means this function can't be called on different arrays without
    // resetting the global 

    // var initialIndex =  this.initialIndex || 0,

    initialIndex = initialIndex || 0;
    var len = arr.length;
    for(initialIndex; initialIndex < len ; initialIndex++ ){
        var el = arr[initialIndex];
        if( el.b === b && el.a === a ){
            // Bad globals
            // this.initialIndex = initialIndex;
            return initialIndex;
        }
    }
    return -1;
}

var len = some.length;
var lastValidIndex = 0;
for(var i = 0; i < len ; i++){
    var el = some[i];
    // Pass the index here, so it doesn't start from scratch
    var index = getIndexByAB(full, el.a, el.b, lastValidIndex);
    if(index > -1) {
        full[index].c = true;
        lastValidIndex = index;
    }
}

By the way, if you do want a function to cache some values, here's how to do it avoiding globals. (Not that you should use it in this case)

var getIndexByAB = (function(){
     // This will only be executed once, and is private
     // to getIndexByAB (all invocations)
     var lastGoodIndex = 0;

     return function(arr, a,b, resetIndex){
         if (resetIndex) {
            lastGoodIndex = 0;
         }

         var len = arr.length;
         for(var index = lastGoodIndex; index < len ; index++ ){
             var el = arr[index];
             if( el.b === b && el.a === a ){                 
                 lastGoodIndex = index;
                 return index;
             }
         }
         return -1;
    };
})();

Alternatively, you could achieve the following by caching it in getIndexByAB.initialIndex but it's not very elegant. The main reason for avoiding this is the fact that getIndexByAB.initialIndex can be modified by anybody else

@jrajav Thanks, fixed it.... Actually, the code was already saving the current index using a global variable `this.currentIndex`. That was pretty bad, therefore, this is the same code, without relying on a global variable. Which means that it can now be called on multiple arrays, multiple times — Ruan Mendes, Feb 21 '13 at 19:49
Thanks Juan, I understand your point of globals. I though that this.XXX works as an attribute of the function, I had been using this to save function cache for many time. However, I cant understand why you are passing "i" to getIndexByAB insted "index". It suppose that index will grow faster than i. — Martin Borthiry, Feb 21 '13 at 20:05
@MartinBorthiry That was incorrect, I should have been passing the last value of `index`, fixed it — Ruan Mendes, Feb 21 '13 at 21:28
What if I replace `this.initialIndex` by `getIndexByAB.initialIndex` in my original approach ? should it works ? — Martin Borthiry, Feb 21 '13 at 21:30
@MartinBorthiry Yes, it will work, but your solution already worked. I don't think it's a good solution. I've provided a more elegant solution that would allow you to do the same thing — Ruan Mendes, Feb 21 '13 at 21:38
ok, thanks, I accepted your answer. But, it is no clear for me this assignation `initialIndex = initialIndex;` :-/ — Martin Borthiry, Feb 21 '13 at 21:41
@MartinBorthiry There, I had made another mistake, fixed it now! — Ruan Mendes, Feb 21 '13 at 21:45

score 0 · Answer 2 · answered Feb 21 '13 at 19:42

0

Since the arrays are both sorted and some is strictly smaller than full, you could save some time by traversing both arrays at the same time with different indexes. As it is, you are traversing full to get the index of the matching element each time, so you have O(N^2) running time, but you only need to continue the search from the last element you matched.

answered Feb 21 '13 at 19:42

jonvuri

5,738
3
24
32

Let me know if you need me to make it any clearer or give an example. – jonvuri Feb 21 '13 at 19:43

score 0 · Answer 3 · answered Feb 22 '13 at 11:18

Not as efficient as @Juan's answer (which takes advantage of the sorted nature, among other things), but I thought I'd still present my solution as it incidentally forced me to come up with a solution for cloning and comparing Javacript objects.

Utilities

// Create a copy of x without reference back to x
function clone(x){
  return JSON.parse(JSON.stringify(x));
}

// Pass any number of arguments of any type. Returns true if they are all identical.
function areEqual(){
  for(var i = 1, l = arguments.length, x = JSON.stringify(arguments[0]); i < arguments.length; ++i){
    if(x !== JSON.stringify(arguments[i])){
      return false;
    }
  }

  return true;
}

Flagging function

// Your flagLabel being 'c'
function matchAndFlagWith(flagLabel,aFull,aSome){
  var aFlagged = clone(aFull);

  for(var i1 = 0, l1 = aSome.length, oSome; oSome = aSome[i1], i1 < l1; ++i1){
    for(var i2 = 0, l2 = aFlagged.length, oFlagged; oFlagged = aFlagged[i2], i2 < l2; ++i2){
      if(areEqual(oFlagged,oSome)){
        oFlagged[flagLabel] = true;
      }
    }
  }

  return aFlagged;
}

Demo

http://jsfiddle.net/barney/p2qsG/

Most efficient way to merge two arrays of objects

3 Answers3

Utilities

Flagging function

Demo

Linked