JavaScript: улучшение производительности для поиска общих элементов в двух массивах

Question

У меня есть функция для поиска самых длинных общих элементов в двух массивах:

   /**
    * 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;
    }

Этот метод работает, но я хочу улучшить производительность, потому что я вызываю его много раз.

Можно ли улучшить производительность?

Примечание: элементы в массивах имеют несортированную строку

    /**
    * 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);

Answer 1

Если вы беспокоитесь о производительности, вам нужно использовать структуру данных, которая обеспечивает хорошее время поиска.Методы массива, такие как Array.prototype.indexOf, Array.prototype.includes и Array.prototype.find, имеют линейный поиск.Map имеет двоичный поиск и Set имеет постоянный поиск.Я думаю, что Set будет идеальным в этой ситуации.

Простая реализация 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' ]

Это можно немного упростить, используя функции высшего порядка, такие как 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' ]

Эта концепция может быть расширена для поддержки пересечения произвольного числа массивов -

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' ]

Answer 2

Хорошо, indexOf () - это O (n), поэтому, используя Set (), вы можете повысить сложность с O (n ^ 2) до 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;
    }