让A和B成为两组。我正在寻找非常快速或优雅的方法来计算它们之间的集差（A - B或A \B，取决于您的偏好）。正如标题所说，这两个集合作为 Javascript 数组进行存储和操作。
笔记：
- 壁虎特有的技巧没问题
- 我更喜欢坚持使用本机函数（但如果速度更快，我对轻量级库持开放态度）
- 我见过，但没有测试过，JS.Set（见上一点）
编辑：我注意到关于包含重复元素的集合的评论。当我说“设置”时，我指的是数学定义，这意味着（除其他外）它们不包含重复元素。
使用 Javascript 数组计算集差的最快或最优雅的方法是什么？
IT技术
javascript
arrays
set-difference
2021-01-17 03:44:44
6个回答
如果不知道这是否最有效，但也许是最短的
A = [1, 2, 3, 4];
B = [1, 3, 4, 7];
diff = A.filter(function(x) { return B.indexOf(x) < 0 })
console.log(diff);
更新到 ES6：
A = [1, 2, 3, 4];
B = [1, 3, 4, 7];
diff = A.filter(x => !B.includes(x) );
console.log(diff);
好吧，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)));
console.log([...a_minus_b]) // {1}
console.log([...b_minus_a]) // {5}
console.log([...a_intersect_b]) // {2,3,4}您可以使用一个对象作为地图，以避免线性扫描B每个元素的A作为user187291的回答：
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()调用来加速代码。
最短的，使用 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>看看这些解决方案中的很多，它们在小案例中做得很好。但是，当你把它们炸到一百万个项目时，时间复杂度就开始变得愚蠢了。
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");其它你可能感兴趣的问题