javascript - 具有 1000 万个项目的两个数组的差异 - _.difference 太慢了

Question

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

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

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

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

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

Answer 1

如何将数组转换为对象以降低排序的复杂性:

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/

另一件需要考虑的事情是对你的集合进行排序并进行二进制搜索，以将每个数组的复杂度从 (O)N 降低到 (O)log2N(如果我正在思考)。