两个数组与1000万个项目的差异 – _.difference太慢了

我有两个数组与用户ID，我想检查其中的不同项目。

arr1 = [123, 456, 789]; arr2 = [123, 456, 789, 098]; 

问题是：这些数组可能有10或2000万个项目。

我正在尝试与underscore.difference()但它需要10分钟才能完成。

有没有更快的方法来做到这一点？

Answer 1

这认为你在数组中没有数字0或1：

 var arr1 = [123, 456, 789,3], arr2 = [123, 456, 789, 098], has = {}, different=[], length1=arr1.length, length2=arr2.length; for(var i=0;i<length1;i++){ has[arr1[i]]=true; } for(var i=0;i<length2;i++){ var val=arr2[i]; if(has[val] === undefined){ has[val]=val; } else{ if(has[val]!=val){ has[val]=false; } } } for(var i in has){ if (has[i]) different.push(i); } 

如果你想检查0和1：

 for(var i=0;i<length1;i++){ has[arr1[i]]=NaN; } for(var i=0;i<length2;i++){ var val=arr2[i]; if(has[val] === undefined){ has[val]=null; } else{ if(has[val]!=null){ has[val]=true; } } } for(var i in has){ if (!has[i]) different.push(i); } 

Answer 2

如何将数组转换为对象以减lesssorting复杂性：

 var arr1 = [123, 456, 789], arr2 = [123, 456, 789, 098]; function toObject(arr){ return arr.reduce(function(o, v, i) { o[v] = i; return o; }, {}); } var o1 = toObject(arr1), o2 = toObject(arr2), diff = []; for(var prop in o2){ if(o1[prop] === undefined) diff.push(prop); } console.log(diff); 

你显然需要从最大的一组开始。

http://jsfiddle.net/sHUw5/

另一个要考虑的事情是sorting你的集合，并进行二进制search，以减less从(O)N到(O)log2N每个arrays（如果我正在思考）的复杂性。

Answer 3

使用本地js，而不是试图容纳大量场景/input的库。

• 跳过所有函数调用和范围更改。
• 最小化属性查找/命名空间走
• 不要在每个循环中获取数组长度

简单的优化：

 var array1 = []; var array2 = []; var difference = []; for(var i = 0; len = array1.length; i < len; i++) { var value = array1[i]; if(value == array2[i]) { continue; } if(array2.indexOf(value) == -1) { difference.push(value); } } 

Answer 4

这是一个欺骗_.difference将会调用的嵌套迭代的快速方法：

 var arr1 = [123, 456, 789], arr2 = [123, 456, 789, 098], has = {}; arr1.forEach(function(a){ this[a]=1;}, has); alert( arr2.filter(function(a){return !this[a]; }, has) ); 

通过在迭代中使用它 ，我们可以将纯函数传递给可以以最大速度执行的JS。

请注意，这不适用于对象数组或像[1，“1”]这样的混合types数组，但它应该适用于问题描述和演示的问题。

编辑：它需要双向比较（如arr1有，arr2缺失或反之亦然），反转并重复上面的代码。 你仍然只有4000万的计算量，相比之下，indexOf（）使用的方法将花费100万亿美元。