3
\$\begingroup\$

This is my challenge using JavaScript -> Compare two arrays and return a new array with any items only found in one of the two given arrays, but not both. In other words, return the symmetric difference of the two arrays.

My code works, but I think that it can be better.

function diffArray(arr1, arr2) {
 var newArr = [];

  arr1.map(function(val){
   arr2.indexOf(val) < 0 ? newArr.push(val) : '';
  });

  arr2.map(function(val){
   arr1.indexOf(val) < 0 ? newArr.push(val) : '';
  });

  return newArr;
}

diffArray([1, 2, 3, 5, 6, 7], [1, 2, 3, 4, 5]);

What do you think?

\$\endgroup\$
4
\$\begingroup\$

As for performance: Array.indexOf in the worse case(element is not there), will have to check all values of the array to check if the value is in it. And doing this for all values of the second array, means O(n * m) where n is the arr1 size and m is the arr2 size. If n = m, we can consider that it takes O(n*n), which is quite expensive. You could improve this by sorting both arrays and doing a smarter check, but even that will have the cost of the sorting, which is O(n * log n) with a good implementation

Having said all that, what you really want is a structure to check if you have seen or not an element that can check it really quick. In javascript, we can use objets to do this. As its native code we don´t really know the complexity of access, but with testing a bit it is clear that it´s much better (in theory access should be O(1) or O(log n))

The pseudo code is like this:

var seen = {}
iterate all map1 values and mark is as seen
iterate all map2 values and unmark if already seen, mark if not
add all seen values to new array
return array

And here is a full fiddle:

function diffArray(arr1, arr2) {
  var newArr = [];

  arr1.map(function(val) {
    arr2.indexOf(val) < 0 ? newArr.push(val) : '';
  });

  arr2.map(function(val) {
    arr1.indexOf(val) < 0 ? newArr.push(val) : '';
  });

  return newArr;
}


function diffArray2(arr1, arr2) {
  seen = {}
  var newArr = []
  arr1.forEach(function(val) {
    seen[val] = 1 // we saw it on first array	
  })
  arr2.forEach(function(val) {
    if (seen[val] == 1) { // we already saw it on the first one, unmark
      seen[val] = false
    } else if (seen.hasOwnProperty(seen[val]) == false) { // if we hadnt seen it earlier
      seen[val] = 2 // mark with a 2
    }
  })

  for (var val in seen) {
    if (seen[val]) { // if its a 1 or a 2, it was unique
      newArr.push(val)
    }
  }
  return newArr
}

var arr1 = []
var arr2 = []
var mx = 10000;
for (var i = 0; i < mx; i++) {
  arr1.push(i)
  arr2.push(i + Math.round(mx / 2))
}

console.time("diffArray with arrays and .index")
diffArray(arr1, arr2);
console.timeEnd("diffArray with arrays and .index")


console.time("diffArray with object")
diffArray2(arr1, arr2);
console.timeEnd("diffArray with object")

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

map is specifically designed to map a value to another. You're merely looping through the array, not actually mapping. This is best expressed by using forEach instead.

function diffArray(arr1, arr2) {
 var newArr = [];

  arr1.forEach(function(val){
   if(arr2.indexOf(val) < 0) newArr.push(val);
  });

  arr2.forEach(function(val){
   if(arr1.indexOf(val) < 0) newArr.push(val);
  });

  return newArr;
}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

This may not be more efficient than juvian's answer, but I think it's a lot cleaner to use Array.prototype.filter; it's usage, as the name suggests, it to filter elements out of an array, which is exactly what you are trying to do.

function diffArray(a, b) {
    return   a.filter(function(val) { // reveal the unique values in a
        return b.indexOf(val) < 0;
    }.concat(b.filter(function(val) { // concat those with the unique values in b
        return a.indexOf(val) < 0;
    }
}

And, if you want, you could make it even cleaner by extracting the filter parts to their own functions:

function getUniqueValues(src, other) {
    return src.filter(function(val) {
        return other.indexOf(val) < 0;
    }
}

Then, your main function becomes:

function diffArr(a, b) {
    return getUniqueValues(a, b).concat(getUniqueValues(b, a));
}

Again, this may not be more efficient, but it is more idiomatic in that is uses the right built-in JavaScript methods for the job.

Note: it may be more efficient to sort both arrays for faster computing overall:

function diffArr(a, b) {
    a.sort();
    b.sort();
    ...
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Your best fit for this issue is to use the (relatively) new guy in town : the Set, that will do the job for you of ignoring duplicate.
Most browsers support it now, and i looked a few jsperf and it is already fast. The Set is especially interesting if you have many duplicates.

Edit : i changed my code for the more efficient code of @juvian, thks to him for his update.

function diffArray(arr1, arr2) {
   var set1 = new Set(arr1);
   var set2 = new Set(arr2);

   var arr = []   

   set1.forEach(function(val) {  
     if (!set2.has(val)) arr.push(val); 
   });
   set2.forEach(function(val) {  
     if (!set1.has(val)) arr.push(val); 
   });

   return arr;
}

( Notice that if performance matters you'll want to create only once those 4 Set and only clear() them before use ).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Always nice to see people taking advantage of new structures! Would recommend some few changes to make it a bit more performant though: jsfiddle.net/hL9hgynq \$\endgroup\$ – juvian Apr 7 '16 at 15:04
1
\$\begingroup\$

I think it's more suitable to use filter than map in this example, because we are basically filtering two arrays. Finally, we just merge them:

filtered1 = arr1.filter(el => !arr2.includes(el))
filtered2 = arr2.filter(el => !arr1.includes(el))
merged = [...filtered1, filtered2]

The function could be a one-liner, although maybe not so readable:

function diffArray(arr1, arr2) {
  return [...arr1.filter(el => !arr2.includes(el)), ...arr2.filter(el => !arr1.includes(el))]
}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

You can use this array-diff open source component.

Example:

diff([1,2,3], [1,2,3,4,5]) // => [4,5]

It works by concating the two arrays passed and filtering included vals, returning an array representing the difference between the two arrays:

function diff(firstArray: any[], secondArray: any[]): any[] {
  return firstArray.concat(secondArray).filter((val) => {
    return !(firstArray.includes(val) && secondArray.includes(val));
  });
};
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – Toby Speight May 23 '17 at 12:17
  • \$\begingroup\$ K. Edited. Does it make more sense now? \$\endgroup\$ – Yoni May 23 '17 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.