JavaScript:在两个数组中查找公共(public)元素的性能改进

Question

我有一个函数可以搜索两个数组中最长的公共(public)元素:

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

<pre id="result"></pre>

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