两个包含1000万项的数组的差异 - _.difference 太慢了。

Question

我有两个用户ID数组，想要检查它们中的不同项。

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

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

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

有没有更快的方法？

- user3175226

---

数组已经排序了吗？ - Cameron

如果你的元素作为对象的键，那么将一个数组的元素转化为键且值为1可能会更快，然后根据对象是否有或没有该元素作为键，过滤第二个数组。排序对于这么多项目来说会很慢，但是对象查找非常快，并且避免了underscore的contains()方法中循环查找的问题。 - dandavis

哦，看起来_.difference甚至没有使用集合..因此使用集合/探针将是*更好的边界。请参见https://dev59.com/NGcs5IYBdhLWcg3wGQDF - user2864740

如果你正在处理1000万个项目，那么或许你应该把数据存放在数据库中。 - mu is too short

Answer 1

使用本地js，而不是试图适应许多情况/输入的库。

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

简单优化：

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);
    }
}

- Metalstorm

Answer 2

将数组转换为对象以减少排序复杂度，如何看待这个想法？

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

你显然需要从最大的集合开始。

另外要考虑的一件事是对你的集合进行排序，并进行二分查找，将每个数组的复杂度从（O）N降低到（O）log2N（如果我想得没错的话）。 http://jsfiddle.net/sHUw5/

- Johan

---

除非你有理由相信属性迭代比数组遍历快得多（这可能不是真的），否则没有必要转换arr2。 - Aaron Dufour

现在你正在迭代两次，而for-in循环通常比常规for循环慢？ - adeneo

将函数调用 hasOwnProperty 更改为 if(!o1[prop])。如果数据集包含0，请使用 if(o1[prop] === undefined)，因为使用 undefined 可能更快，因为它不需要进行任何类型转换。 - Metalstorm

in操作符比hasOwnProperty()更快，甚至比比较或转换还要快... - dandavis

@AaronDufour 抱歉，那是我的误解。 - Johan

Answer 3

这意味着数组中没有数字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);
}

- juvian

---

请用数组推送替换 alert !! - Metalstorm

同时将arr2[i]分配给一个本地变量，这样你就可以进行两次查找。 - Metalstorm

你还在每次循环中重新计算数组长度。 - Metalstorm

@Metalstorm：数组长度是存储的，而不是计算的。 - cookie monster

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

通过在迭代中使用this，我们将一个纯函数交给JS以在最大可能的速度下执行。

请注意，这对于对象数组或像[1，"1"]这样的混合类型数组是不起作用的，但它应该适用于问题的描述和问题演示。

编辑：如果您想要双向比较（例如arr1有，arr2缺少或反之亦然），请反转并重复上面的代码。与使用indexOf()方法的方法相比，您仍然只需要进行4000万次计算，而不是100万亿次...

- dandavis

---

如果您手写循环，速度会快得多。 - Esailija

你将会排除掉arr1中不在arr2中的项目。 - cookie monster

在这种情况下，this 将成为全局变量，这使得它绝对不是一个纯函数，而且会污染全局命名空间。 - Aaron Dufour

哦，我从来没有见过forEach的第二个参数。有趣。 - Aaron Dufour

在函数中使用“this”是什么让它成为“可怕的滥用”？我一直认为这是[]方法中最好的部分，并且为reduce不允许相同选项而感到遗憾，尽管对于过滤而言，它并不像减少那样重要。 - dandavis