我有一个函数可以搜索两个数组中最长的公共(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>
最佳答案
如果您关心性能,您会希望使用可提供良好查找时间的数据结构。 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' ]
关于JavaScript:在两个数组中查找公共(public)元素的性能改进,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55304473/