Javascript：有效地比较两个整数数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4193749/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Javascript: efficiently compare two integer arrays
提问by LDJ
I have two integer arrays which contain numeric values. I want to look through both lists and check for commonality (or lack of) between the lists. I.e. I want to iterate through the array(s) and find those items which appear in both lists, while in a separate function I want to go through the arrays and find items which are in the first and not in the second.
我有两个包含数值的整数数组。我想查看两个列表并检查列表之间的共性（或缺乏）。即我想遍历数组并找到出现在两个列表中的那些项目，而在一个单独的函数中我想遍历数组并找到第一个而不是第二个的项目。
The obvious way of doing this is nested for loops:
这样做的明显方法是嵌套 for 循环：
var containedInFirst = false;
for (var primaryID = 0; primaryID < PrimaryArray.length; primaryID++) {
containedInFirst = false;
for (var secondaryID = 0; secondaryID < SecondaryArray.length; secondaryID++) {
if (PrimaryArray [primaryID] === SecondaryArray[secondaryID]) {
containedInFirst = true;
break;
}
}
//Do some more stuff based on the value of containedInFirst here
}
But given the lists could contain hundreds or thousands of records this is quite a bit of itteration and processor intensive. I was therefore wondering if there is a more efficient way of executing the above code? Not just the actual searching, but something more efficient than an Integer array as the container for the values, or just not using nested for loops to traverse and compare the content.
但考虑到列表可能包含数百或数千条记录，这是相当多的迭代和处理器密集型。因此，我想知道是否有更有效的方式来执行上述代码？不仅仅是实际的搜索，而是比作为值的容器的 Integer 数组更有效的东西，或者只是不使用嵌套的 for 循环来遍历和比较内容。
Any thoughts on more efficient or elegant solutions?
关于更有效或更优雅的解决方案的任何想法？
采纳答案by Marcelo Cantos
Sort them first and duck-waddle through them in parallel.
首先对它们进行排序，然后并行地穿过它们。
a.sort();
b.sort();
left = []; both = []; right = [];
i = 0; j = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) {
left.push(a[i]);
++i;
} else if (b[j] < a[i]) {
right.push(b[j]);
++j;
} else {
both.push(a[i]);
++i; ++j;
}
}
while (i < a.length) {
left.push(a[i]);
++i;
}
while (j < b.length) {
right.push(b[j]);
++j;
}
回答by Timothy Perez
Everyone is overly complicating this. Here's a one liner:
每个人都把这件事复杂化了。这是一个单班轮：
var isEqual = (JSON.stringify(arr1.sort()) === JSON.stringify(arr2.sort()));
回答by Thariama
When using two nested loops the complexity will be O(n*n). Sorting both array can be done in complexity O(n log n).
当使用两个嵌套循环时，复杂度将为 O(n*n)。可以以复杂度 O(n log n) 对两个数组进行排序。
AS Marcelo Cantos stated duck-waddle :) through both in paralell has complexity O(n) leading to an overall complexity of O(n log n) + O(n) which is O (n log n).
AS Marcelo Cantos 说duck-waddle :) 通过两者并行具有复杂性 O(n) 导致 O(n log n) + O(n) 的整体复杂性，即 O (n log n)。
回答by Shadow Wizard is Ear For You
I think I have solution with efficiency of O(N) (no sort needed), here it is:
我想我有效率为 O(N) 的解决方案（不需要排序），这里是：
var firstNotSecond;
function CompareIntArrays(arr1, arr2)
{
firstNotSecond = new Array();
var arr3 = new Array(); //appear in both
var arrTemp = new Array(); //used for firstNotSecond
var usedNumbers = new Array();
for (var i = 0; i < arr1.length; i++)
{
var key = arr1[i];
usedNumbers[key] = true;
arrTemp[key + ""] = true;
}
for (var i = 0; i < arr2.length; i++)
{
var key = arr2[i];
if (usedNumbers[key])
{
arr3[arr3.length] = key;
arrTemp[key] = false;
}
}
for (var key in arrTemp)
if (arrTemp[key])
firstNotSecond[firstNotSecond.length] = parseInt(key);
return arr3;
}
The function will return new array with the items that exist in both arrays, and will assign global array with all items existing in first array that do not exist in second array.
该函数将返回包含两个数组中都存在的项目的新数组，并将第一个数组中存在但第二个数组中不存在的所有项目分配给全局数组。
This code is relying on the fact both arrays hold only integer numbers.
这段代码依赖于两个数组都只包含整数的事实。
Usage example:
用法示例：
alert(CompareIntArrays([15, 551, 25, 910, 11], [25, 11, 785, 880, 15]));
alert(firstNotSecond);
Tested with arrays having 100,000 items: less than one second. Tested with arrays having 200,000 items each: less than 2 seconds.
使用具有 100,000 个项目的数组进行测试：不到一秒。使用每个包含 200,000 个项目的数组进行测试：不到 2 秒。
回答by Pau
Another possibility could be order those arrays while you create them. I am not sure if you can do that. But if you can, it will increase a bit the complextity of adding an element to the array (O(log n) instead of O(1)) but it will decrease the complexity of your comparison algorithm to O(n)
另一种可能性是在创建它们时对这些数组进行排序。我不确定你是否能做到这一点。但是如果可以的话，它会稍微增加向数组添加元素的复杂性（O(log n) 而不是 O(1)），但它会将比较算法的复杂性降低到 O(n)
回答by the_drow
Sort both arrays, than loop just once and compare:
对两个数组进行排序，而不是循环一次并进行比较：
function diff(arrayToCompareTo, comparedArray)
{
Sort(arrayToCompareTo);
Sort(comparedArray);
var difference = [], same = [];
for(var i = 0; i < arrayToCompareTo.length; ++i)
{
if (arrayToCompareTo[i] != comparedArray[i])
difference.push(comparedArray[i]);
else
same.push(comparedArray[i]);
}
if (comparedArray.length > arrayToCompareTo.length)
for(var i = arrayToCompareTo.length; i < comparedArray.length; ++i)
difference.push(comparedArray[i]);
}
This is not tested so if something is wrong please let me know.
Anyway this should set you to the right direction since it's O(N) at best and O(M) at worst if comparedArray.length > arrayToCompareTo.length, it's much more efficient than O(N^2). Note that the sorting takes O(N log N).
这没有经过测试，所以如果有什么问题，请告诉我。
无论如何，这应该使您朝着正确的方向前进，因为它充其量是 O(N)，最坏的是 O(M)，如果comparedArray.length > arrayToCompareTo.length，它比 O(N^2) 高效得多。请注意，排序需要 O(N log N)。
