Question:
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)); };
Solution:1
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
Solution:2
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.
Solution:3
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
EmoticonEmoticon