CODEWITHSUNDEEP
javascriptnode.jsalgorithmperformance
ar099968
ar099968

Reputation: 7547

JavaScript: performance improvement to find the common elements in two array

I have a function for search the longest common elements in two array:

   /**
    * Return the common elements in two array
    */ 
    function searchArrayInArray(array1, array2) {
       var result = [];
       for (var j = 0, e = array1.length; j < e; j++){
           var element = array1[j];
           if( array2.indexOf(element) !== -1 ){
               result.push(element);
           }
       }
       return result;
    }

This method works, but I want improve performance because I call it many times.

There is any performance improvement appliable?

Side note: the elements into the arrays are unsorted string 

    /**
    * Return the common elements in two array
    */ 
    function searchArrayInArray(array1, array2) {
       var result = [];
       for (var j = 0, e = array1.length; j < e; j++){
           var element = array1[j];
           if( array2.indexOf(element) !== -1 ){
               result.push(element);
           }
       }
       return result;
    }
    
    var result = searchArrayInArray(['a', 'b'], ['b', 'c']);
    
    document.getElementById("result").innerHTML = JSON.stringify(result, null, 2);
<pre id="result"></pre>

Upvotes: 0

Views: 641

Answers (3)

md_salm
md_salm

Reputation: 459

The easiest way:

var a = [1,2,3,4,5,6,7,8,9,10];
var b = [2,4,5,7,11,15];


var c = a.filter(value => b.includes(value))
console.log(c)

Upvotes: 0

Mulan
Mulan

Reputation: 135277

If you're concerned about performance, you'll want to use a data structure which provides good look-up times. Array methods like Array.prototype.indexOf, Array.prototype.includes, and Array.prototype.find all have linear look-ups. Map has binary look-up and Set has constant look-up. I think Set will be ideal in this situation.

A straightforward implementation of intersection -

const intersection = (a1 = [], a2 = []) =>
{ const s =
    new Set(a1)
  
  const result =
    []

  for (const x of a2)
    if (s.has(x))
      result.push(x)

  return result
}

console.log(intersection(['a', 'b'], ['b', 'c']))
// [ 'b' ]

This can be simplified a bit using higher-order functions like Array.prototype.filter -

const intersection = (a1 = [], a2 = []) =>
{ const s =
    new Set(a1)
  
  return a2.filter(x => s.has(x))
}

console.log(intersection(['a', 'b'], ['b', 'c']))
// [ 'b' ]

This concept can be expanded upon to support intersecting an arbitrary number of arrays -

const intersection = (a1 = [], a2 = []) =>
{ const s =
    new Set(a1)
  
  return a2.filter(x => s.has(x))
}

const intersectAll = (a = [], ...more) =>
  more.reduce(intersection, a)

console.log(intersectAll(['a', 'b'], ['b', 'c'], ['b', 'd'], ['e', 'b']))
// [ 'b' ]

Upvotes: 3

Photon
Photon

Reputation: 2777

Well indexOf() is O(n) so by using Set() instead you can improve complexity from O(n^2) to O(n * log n)

function searchArrayInArray(array1, array2) {
       var result = [];
       let set = new Set();
       for(el of array2){
            set.add(el);
       }

       for (var j = 0, e = array1.length; j < e; j++){
           var element = array1[j];
           if( set.has(element) ){
               result.push(element);
           }
       }
       return result;
    }

Upvotes: 0

Related Questions