javascript - 匹配来自两个 JavaScript 数组的元素的最快方法

Question

我正在尝试使用 JavaScript 探索数组，我遇到了一种情况，我想匹配来自两个不同数组的元素。

第一个数组:

json1=[{
    name:"abc",
    add:"xyz"
},{
    name:"mno",
    add :"xxy"
}]

第二个数组

json2=[{
    name:"abc",
    add:"xyz",
    off:"lop"
},{
    name:"rag",
    add:"vrt",
    off:"wwq"
},{
    name:"abc",
    add:"xyz",
    off:"lop"
},{
    name:"wal",
    add:"rot",
    off:"nim"
},{
    name:"abc",
    add:"ola",
    off:"blo"
}]

两个数组都有共同的名称值('abc')。我正在循环并将 json1 的每个名称值与 json2 的每个名称值进行匹配。

为了让它更快，我按名称对第二个数组进行了排序:

json2.sort(function(x,y){
     return x.name>y.name? 1 : x.name<y.name? -1 :0;  
});

我仍然认为它可能没有那么有用，因为如果我们有更多的数据，每个数组中可能有 100 个左右的元素，这将需要一些计算时间。另外，为了避免阻塞页面，我已将所有这些任务委托(delegate)给网络 worker 。

有什么方法可以让它更快吗？

Answer 1

如果你不关心循环后json2的结果你可以使用。

var match = [];
for(var indx in json1){
    var mainItem = json1[i];
    for(var mIndx = 0; mIndx < json2.length; mIndex++){
        if(json2[mIndex].name === json1[indx].name){
            match.push(json2.splice(mIndex, 1));
            mIndex--;
        }
        //this else is only used when you know that your json2 array is sorted ascendingly
        //by name property. this helps the time complexity.
        else if(json2[mIndx].name > json1[indx].name){
            break; 
        }
    }
}

您的匹配结果将在匹配变量中。m = 第一个数组的长度，n = 第二个数组的长度。json2排序时的时间复杂度为(m + n)。最坏情况的复杂度是 m * n，即 json2 中的所有记录都是不同的并且 json2 未排序。