让A
和B
成为两组。我正在寻找真正快速或优雅的方法来计算它们之间的集合差异(A - B
或A \B
,取决于您的偏好)。正如标题所说,这两个集合作为 Javascript 数组存储和操作。
笔记:
- 壁虎专用技巧还可以
- 我更喜欢坚持使用本机功能(但如果它更快,我愿意使用轻量级库)
- 我见过,但没有测试过,JS.Set(见上一点)
编辑:我注意到关于包含重复元素的集合的评论。当我说“集合”时,我指的是数学定义,这意味着(除其他外)它们不包含重复的元素。
让A
和B
成为两组。我正在寻找真正快速或优雅的方法来计算它们之间的集合差异(A - B
或A \B
,取决于您的偏好)。正如标题所说,这两个集合作为 Javascript 数组存储和操作。
笔记:
编辑:我注意到关于包含重复元素的集合的评论。当我说“集合”时,我指的是数学定义,这意味着(除其他外)它们不包含重复的元素。
如果不知道这是否最有效,但也许是最短的
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}
您可以将对象用作地图,以避免线性扫描user187291 的答案中B
的每个元素:A
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()
如果所有元素都已经具有唯一的字符串表示形式(就像数字的情况一样),您可以通过删除调用来加速代码。
纵观这些解决方案中的许多,它们适用于小案例。但是,当您将它们增加到一百万个项目时,时间复杂度开始变得愚蠢。
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");
最短的,使用 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>
如果您使用Set
s,它可以非常简单且高效:
function setDifference(a, b) {
return new Set(Array.from(a).filter(item => !b.has(item)));
}
由于Set
s 在后台使用哈希函数*,因此该has
函数比indexOf
(例如,如果您拥有 100 多个项目,这很重要)要快得多。
我将对数组 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;
}
结合 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)
:返回一个数组,其中包含调用返回 truefnEvaluator
的键/值对的
结果。fnSelector
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 个元素的两组. 使用这些值 AB 大约需要 75 毫秒,而联合和交集每个大约需要 150 毫秒。(Mac Safari 4.0,使用 Javascript Date 进行计时。)
我认为这对 20 行代码来说是不错的回报。
使用Underscore.js(函数式 JS 库)
>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]
一些简单的功能,借用@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 }
至于禁食的方式,这不是那么优雅,但我已经运行了一些测试来确定。将一个数组作为对象加载会更快地进行大量处理:
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映射结果。
这行得通,但我认为另一个更短,也更优雅
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;