使用 Javascript 数组计算集合差异的最快或最优雅的方法是什么？

设 A和 B为两组。我正在寻找 真的快速或优雅的方法来计算它们之间的集合差异(A - B或 A \B，取决于您的偏好)。正如标题所说，这两个集合作为 Javascript 数组存储和操作。

备注:

  • 壁虎特有的技巧没问题
  • 我更喜欢坚持使用本机函数(但是如果轻量级库更快的话，我也可以使用它)
  • 我已经看到，但没有测试，JS.Set(见前一点)

编辑: 我注意到一条关于包含重复元素的集合的注释。当我说“ set”时，我指的是数学定义，这意味着(在其他事情中)它们不包含重复的元素。

112526 次浏览
小开
最佳答案

我不知道这是否最有效，但也许是最短的:

var A = [1, 2, 3, 4];
var B = [1, 3, 4, 7];


var diff = A.filter(function(x) {
return B.indexOf(x) < 0;
});


console.log(diff); // [2]

更新至 ES6:

const A = [1, 2, 3, 4];
const B = [1, 3, 4, 7];


const diff = A.filter(x => !B.includes(x));


console.log(diff); // [2]

小开

这个可以，但我觉得另一个更短，也更优雅

A = [1, 'a', 'b', 12];
B = ['a', 3, 4, 'b'];


diff_set = {
ar : {},
diff : Array(),
remove_set : function(a) { ar = a; return this; },
remove: function (el) {
if(ar.indexOf(el)<0) this.diff.push(el);
}
}


A.forEach(diff_set.remove_set(B).remove,diff_set);
C = diff_set.diff;
小开

您可以使用一个对象作为映射，以避免像在 User187291的回答中那样对 A的每个元素进行线性扫描 B:

function setMinus(A, B) {
var map = {}, C = [];


for(var i = B.length; i--; )
map[B[i].toSource()] = null; // any other value would do


for(var i = A.length; i--; ) {
if(!map.hasOwnProperty(A[i].toSource()))
C.push(A[i]);
}


return C;
}

非标准的 toSource()法用于获取唯一的属性名; 如果所有元素都已经具有唯一的字符串表示形式(与数字一样) ，则可以通过删除 toSource()调用来加快代码的速度。

小开

结合 Christoph 的想法，并假设在数组和对象/哈希(each和朋友)上采用一些非标准的迭代方法，我们可以得到线性时间的集合差异、并集和交集，总共大约20行:

var setOPs = {
minusAB : function (a, b) {
var h = {};
b.each(function (v) { h[v] = true; });
return a.filter(function (v) { return !h.hasOwnProperty(v); });
},
unionAB : function (a, b) {
var h = {}, f = function (v) { h[v] = true; };
a.each(f);
b.each(f);
return myUtils.keys(h);
},
intersectAB : function (a, b) {
var h = {};
a.each(function (v) { h[v] = 1; });
b.each(function (v) { h[v] = (h[v] || 0) + 1; });
var fnSel = function (v, count) { return count > 1; };
var fnVal = function (v, c) { return v; };
return myUtils.select(h, fnSel, fnVal);
}
};

这里假设为数组定义了 each和 filter，并且我们有两个实用方法:

  • 返回一个 数组，其键为 hash

  • Select (hash，fnSelector, 返回一个数组，其中包含 调用 fnEvaluator的结果 的键/值对上 fnSelector返回 true

select()的灵感来源于 Common Lisp，它只是将 filter()和 map()合二为一。(最好在 Object.prototype上定义它们，但这样做会破坏 jQuery，所以我选择了静态实用程序方法。)

性能: 使用

var a = [], b = [];
for (var i = 100000; i--; ) {
if (i % 2 !== 0) a.push(i);
if (i % 3 !== 0) b.push(i);
}

给出两组分别含有50,000和66,666个元素。有了这些值，A-B 大约需要75毫秒，而联合和交集大约每个150毫秒。(Mac Safari 4.0，使用 Javascript Date 计时。)

我觉得20行代码的回报还不错。

小开

我将对数组 B 进行散列，然后保留数组 A 中 B 中不存在的值:

function getHash(array){
// Hash an array into a set of properties
//
// params:
//   array - (array) (!nil) the array to hash
//
// return: (object)
//   hash object with one property set to true for each value in the array


var hash = {};
for (var i=0; i<array.length; i++){
hash[ array[i] ] = true;
}
return hash;
}


function getDifference(a, b){
// compute the difference a\b
//
// params:
//   a - (array) (!nil) first array as a set of values (no duplicates)
//   b - (array) (!nil) second array as a set of values (no duplicates)
//
// return: (array)
//   the set of values (no duplicates) in array a and not in b,
//   listed in the same order as in array a.


var hash = getHash(b);
var diff = [];
for (var i=0; i<a.length; i++){
var value = a[i];
if ( !hash[value]){
diff.push(value);
}
}
return diff;
}
小开

使用 jQuery，最短的是:

var A = [1, 2, 3, 4];
var B = [1, 3, 4, 7];


var diff = $(A).not(B);


console.log(diff.toArray());
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

小开

好吧，7年后，使用 ES6就位对象相当容易(但仍然不如 巨蟒的 A - B紧凑) ，据报道对于大型数组比 indexOf快:

console.clear();


let a = new Set([1, 2, 3, 4]);
let b = new Set([5, 4, 3, 2]);


let a_minus_b = new Set([...a].filter(x => !b.has(x)));
let b_minus_a = new Set([...b].filter(x => !a.has(x)));
let a_intersect_b = new Set([...a].filter(x => b.has(x)));
let a_union_b = new Set([...a, ...b]);


console.log(...a_minus_b);     // {1}
console.log(...b_minus_a);     // {5}
console.log(...a_intersect_b); // {2,3,4}
console.log(...a_union_b);     // {1,2,3,4,5}

小开

使用 下划线.js(函数式 JS 库)

>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]
小开

至于禁食的方式，这并不是那么优雅，但我已经运行了一些测试来确定。将一个数组作为对象加载要快得多，以便大量处理:

var t, a, b, c, objA;


// Fill some arrays to compare
a = Array(30000).fill(0).map(function(v,i) {
return i.toFixed();
});
b = Array(20000).fill(0).map(function(v,i) {
return (i*2).toFixed();
});


// Simple indexOf inside filter
t = Date.now();
c = b.filter(function(v) { return a.indexOf(v) < 0; });
console.log('completed indexOf in %j ms with result %j length', Date.now() - t, c.length);


// Load `a` as Object `A` first to avoid indexOf in filter
t = Date.now();
objA = {};
a.forEach(function(v) { objA[v] = true; });
c = b.filter(function(v) { return !objA[v]; });
console.log('completed Object in %j ms with result %j length', Date.now() - t, c.length);

结果:

completed indexOf in 1219 ms with result 5000 length
completed Object in 8 ms with result 5000 length

但是，这适用于 只有字符串。如果您计划比较编号的集合，您将希望将结果与 ParseFloat映射。

小开

一些简单的函数，借用了@milan 的回答:

const setDifference = (a, b) => new Set([...a].filter(x => !b.has(x)));
const setIntersection = (a, b) => new Set([...a].filter(x => b.has(x)));
const setUnion = (a, b) => new Set([...a, ...b]);

用法:

const a = new Set([1, 2]);
const b = new Set([2, 3]);


setDifference(a, b); // Set { 1 }
setIntersection(a, b); // Set { 2 }
setUnion(a, b); // Set { 1, 2, 3 }
小开

看看这些解决方案中的大部分，它们在小案例中表现良好。但是，当你把它们放大到一百万个项目时，时间的复杂性就开始变得愚蠢了。

 A.filter(v => B.includes(v))

看起来像 O (N ^ 2)解。因为有一个 O (N)解决方案，所以让我们使用它，如果没有更新 JS 运行时，您可以很容易地修改为不是生成器。

    function *setMinus(A, B) {
const setA = new Set(A);
const setB = new Set(B);


for (const v of setB.values()) {
if (!setA.delete(v)) {
yield v;
}
}


for (const v of setA.values()) {
yield v;
}
}


a = [1,2,3];
b = [2,3,4];


console.log(Array.from(setMinus(a, b)));

虽然这比其他许多解决方案要复杂一些，但是当您有大型列表时，这将快得多。

让我们快速看一下性能差异，在0... 10,000之间的1,000,000个随机整数集上运行它，我们会看到以下性能结果。

setMinus time =  181 ms
diff time =  19099 ms


function buildList(count, range) {
result = [];
for (i = 0; i < count; i++) {
result.push(Math.floor(Math.random() * range))
}
return result;
}


function *setMinus(A, B) {
const setA = new Set(A);
const setB = new Set(B);


for (const v of setB.values()) {
if (!setA.delete(v)) {
yield v;
}
}


for (const v of setA.values()) {
yield v;
}
}


function doDiff(A, B) {
return A.filter(function(x) { return B.indexOf(x) < 0 })
}


const listA = buildList(100_000, 100_000_000);
const listB = buildList(100_000, 100_000_000);


let t0 = process.hrtime.bigint()


const _x = Array.from(setMinus(listA, listB))


let t1 = process.hrtime.bigint()


const _y = doDiff(listA, listB)


let t2 = process.hrtime.bigint()


console.log("setMinus time = ", (t1 - t0) / 1_000_000n, "ms");
console.log("diff time = ", (t2 - t1) / 1_000_000n, "ms");

小开

如果你使用的是 Set，它可以非常简单和高性能:

function setDifference(a, b) {
return new Set(Array.from(a).filter(item => !b.has(item)));
}

由于 Set在底层使用 Hash 函数 * ，因此 has函数比 indexOf快得多(如果有超过100个项目，这就很重要了)。

小开

使用 core-js填充 新的 Set方法建议:

import "core-js"


new Set(A).difference(B)

从理论上讲，时间复杂度应该是 Θ(n)，其中 n是 B中元素的个数。

小开

下面的函数是在 Python 的 set()类中找到的方法的端口，位于 TC39集方法建议之后。

const
union = (a, b) => new Set([...a, ...b]),
intersection = (a, b) => new Set([...a].filter(x => b.has(x))),
difference = (a, b) => new Set([...a].filter(x => !b.has(x))),
symetricDifference = (a, b) => union(difference(a, b), difference(b, a)),
isSubsetOf = (a, b) => [...b].every(x => a.has(x)),
isSupersetOf = (a, b) => [...a].every(x => b.has(x)),
isDisjointFrom = (a, b) => !intersection(a, b).size;


const
a = new Set([1, 2, 3, 4]),
b = new Set([5, 4, 3, 2]);


console.log(...union(a, b));              // [1, 2, 3, 4, 5]
console.log(...intersection(a, b));       // [2, 3, 4]
console.log(...difference(a, b));         // [1]
console.log(...difference(b, a));         // [5]
console.log(...symetricDifference(a, b)); // [1, 5]


const
c = new Set(['A', 'B', 'C', 'D', 'E']),
d = new Set(['B', 'D']);
  

console.log(isSubsetOf(c, d));            // true
console.log(isSupersetOf(d, c));          // true


const
e = new Set(['A', 'B', 'C']),
f = new Set(['X', 'Y', 'Z']);
  

console.log(isDisjointFrom(e, f));        // true
.as-console-wrapper { top: 0; max-height: 100% !important; }


提交答案