Tutorial :What's the fastest way to merge Array's in JavaScript where comparisons are expensive?


I want to merge two Array's in JavaScript. Unfortunately, comparisons of the particular data I am using is expensive. What is the best algorithm to merge my to lists with the least amount of comparisons?

EDIT: I should note that the two Array's are sorted and I would like the merged content to be sorted and have only unique values.

EDIT: By request I will give you my current code, but it really doesn't help..

// Merges arr1 and arr2 (placing the result in arr1)  merge = function(arr1,arr2) {      if(!arr1.length) {          Array.prototype.push.apply(arr1,arr2);          return;      }      var j, lj;      for(var s, i=0, j=0, li=arr1.length, lj=arr2.length; i<li && j<lj;) {          s = compare(arr1[i], arr2[j]);          if(s<0) ++i;          else if(s==0) ++i, ++j;          else arr1.splice(i,0, arr2[j++]);      }      if(j<lj) Array.prototype.push.apply(arr1, arr2.slice(j));  };  


This is exactly what merge sort does in the merging step with a minor addition that duplicate elements will be dropped off. Here's the algorithm:

function merge(left,right)      var list result      while length(left) > 0 and length(right) > 0          if first(left) ≤ first(right)              append first(left) to result              left = rest(left)          else              append first(right) to result              right = rest(right)      end while      if length(left) > 0           append left to result      else            append right to result      return result  


Here is a function to make the array unique:

Array.prototype.unique = function () {      var r = new Array();      o:for(var i = 0, n = this.length; i < n; i++)      {          for(var x = 0, y = r.length; x < y; x++)          {              if(r[x]==this[i])              {                  continue o;              }          }          r[r.length] = this[i];      }      return r;  }  

To merge Arrays you would do:

var MainArray= arr1.concat(arr2);  

Then to remove duplicates:

var MainArray= MainArray.unique();  

Then to sort:

var MainArray= MainArray.sort(); //Or you own sort if you have one  

I think this sounds along the lines you were looking for, but it might depend on the amount and type of data.


This seems to do it for me using maps to do comparisons instead of a comparison function. It results in more loops though which is often more expensive than the comparison. This was used to right join arrays of objects that had a name attribute. It also had the unique problem of having to modify the existing array vs. creating a new array and assigning. Some reference thing with D3 and force nodes.

function merge(right,left) {      var map_right = {},          map_left = {};      right.forEach(function(n) {          map_right[n.name] = n;      });      left.forEach(function(n) {          map_left[n.name] = n;      });      for(var n in map_left) {          if (map_right[n] === undefined) {              left.splice(nodes.indexOf(map_b[n]),1);          }      }      right.forEach(function (n) {          if (map_left[n.name] === undefined) {              left.push(n);          }      });  }  

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Next Post »