假设有两个集合 A 和 B。我正在寻求一种非常快速或优雅的方式来计算它们之间的差集(A - B 或 A \B，具体取决于您的喜好)。如标题所述，这两个集合被存储和操作为 Javascript 数组。
注意:
- Gecko 特定技巧可行
- 我更喜欢使用本地功能(但如果它更快，我也可以考虑轻量级库)
- 我看过但未测试过JS.Set(见上一点)
编辑: 我发现有评论提到集合包含重复元素。当我说“集合”时，我是指数学定义，这意味着它们不包含重复元素。
使用Javascript数组计算集合差的最快或最优雅的方法是什么？
182
- Matt Ball
9
15个回答
229
我不知道这是否最有效，但也许是最短的方法：
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]- user187291
13
11+1：虽然不是最高效的解决方案，但绝对简洁易读。 - Christoph
10注意：array.filter在跨浏览器方面不受支持（例如，在IE中不支持）。这似乎对@Matt没有影响，因为他表示“Gecko-specifc tricks are okay”，但我认为值得一提。 - Eric Bréchemier
64这很慢。O（|A| * |B|）。 - glebm
2@WongJiaHau，可以使用哈希集在摊销的O（|A|+|B|）时间复杂度内完成此操作。 - glebm
显示剩余8条评论
181
7年后，使用ES6的Set对象变得非常容易（但仍不像Python的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}- milan
6
2对于大型数组来说，比indexOf快得多。 - Estus Flask
274我不知道为什么JavaScript的集合没有内置的并集/交集/差集函数... - SwiftsNamesake
8@SwiftsNamesake，有一个提案关于创建内置方法的集合，希望在2018年1月讨论 https://github.com/tc39/agendas/blob/master/2018/01.md。 - John
9四年后，规范提案已经放置在 https://github.com/tc39/proposal-set-methods 上。 - Carl Walsh
4提案目前处于第二阶段。 - Quinten C
2截至2022年11月30日，处于第三阶段。 - htmlboss
22
看到很多这样的解决方案，对于小规模情况表现不错。但是，当它们扩展到一百万项时，时间复杂度开始变得荒谬。
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)));虽然这个方法比其他解决方案更加复杂，但是当你有大型列表时，这种方法会更快。
让我们快速查看性能差异，运行在包含1,000,000个0到10,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");- koblas
5
@RonKlein 公正的观点，已将代码更新为两个集合。 - koblas
请注意，如果您有一个非常大的Set，您将被限制在2^24个项目（16,777,216）并且它会崩溃。否则，这是一个很好的解决方案！ - Jordan
@koblas，你的第二段代码片段有问题，会抛出一个ReferenceError错误，但是你却撤销了我所做的修复。 - David Tejuosho
process.hrtime.bigint() 是一个 Node.js 函数，不是浏览器函数，无法在“运行代码片段”引擎中工作。区别在于纳秒和毫秒计时。 - koblas那个setMinus()函数看起来不正确，不能作为A-B的差集。B中不在A中的元素不应该被返回。按照现在的实现，它更像是一个集合异或而不是一个差集。 - Timothée Groleau
16
如果您正在使用Set，那么它可以非常简单和高效：
function setDifference(a, b) {
return new Set(Array.from(a).filter(item => !b.has(item)));
}
由于Set在底层使用哈希函数*，因此has函数比indexOf函数快得多（如果您有超过100个项，则这很重要）。
- Andrew Schwartz
1
这是迄今为止最好的答案，之前的回答都没有正确使用集合。 - Martijn Scheffer
14
你可以使用一个对象作为映射，避免像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
8
最短的方法是使用jQuery：
最短的方法是使用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>- perhelion
5
这将返回一个差异对象。 - Drew Baker
2jQuery
not 在3.0.0-rc1版本中不再支持通用对象。请参考https://github.com/jquery/jquery/issues/3147。 - Marc-André Lafortune3为了完成这个任务而仅仅为此添加一个约70k的第三方库并不是一个好主意，因为正如其他回答中所示，同样的事情只需几行代码即可完成。然而，如果您已经在项目中使用jQuery，则可以完全使用它。 - FiniteLooper
虽然这种方法的代码量较少，但它并没有提供任何关于所使用的不同算法和数据结构的空间和时间复杂度的解释。对于开发人员来说，它是一个黑盒子，无法在数据规模扩大或内存受限时进行评估，从而使软件工程师难以进行工程化。如果您在大型数据集上使用这种方法，性能可能会一直未知，直到进一步研究源代码。 - Downhillski
这只是返回A中不包含在B中的元素数量（在本例中为2）。将2转换为数组是毫无意义的... - Alex
7
一些简单的函数，借鉴 @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 }
- Brian Burns
6
我会对数组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;
}
- Eric Bréchemier
3
这正是我半小时前发布的算法。 - Christoph
@Christoph：你说得对...我没注意到。不过我觉得我的实现更简单易懂 :) - Eric Bréchemier
我认为最好在getDifference之外计算差异，这样可以多次重复使用。也许可以像这样选择性地传递参数：
getDifference(a, b, hashOfB)，如果没有传递，则会计算，否则将直接重用。 - Christophe Roussy6
- chribsen
5
借鉴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，并且我们有两个实用方法：
myUtils.keys(hash)：返回具有哈希键的数组。myUtils.select(hash, fnSelector, fnEvaluator)：返回一个数组，其中包含调用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);
}
提供两个分别包含50000和66666个元素的集合。在这些值下，A-B操作大约需要75ms，而并集和交集操作各需要约150ms。（在Mac Safari 4.0上使用Javascript Date计时。）
我认为这对于20行代码来说是不错的回报。
- j-g-faustus
2
1即使元素是数字，您仍应检查
hasOwnProperty()：否则，类似于Object.prototype[42] = true;的情况意味着42永远不会出现在结果集中。 - Christoph虽然可以通过这种方式设置42，但是否存在半现实的使用情况呢？有人真的会这样做吗？
但对于一般的字符串来说，我理解你的观点 - 它很容易与某些Object.prototype变量或函数发生冲突。 - j-g-faustus
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
indexOf实现中。 - Crescent Fresh