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

Question

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

笔记:

• 壁虎特有的技巧是可以的
• 我更喜欢坚持本机功能(但如果速度更快,我会对轻量级库开放)
• 我见过,但没有经过测试,JS.Set(见前一点)

编辑:我注意到有关包含重复元素的集合的注释.当我说"集合"时,我指的是数学定义,这意味着(除其他外)它们不包含重复元素.

Answer 1

如果不知道这是否最有效,但也许是最短的

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);

Answer 2

好吧,7年后,使用ES6的Set对象很容易(但仍然不像蟒蛇A-B那么紧凑),据报道比A - B大型阵列更快:

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}

Answer 3

看看这些解决方案中的许多，它们对于小情况来说效果很好。但是，当你将它们增加到一百万个项目时，时间复杂度开始变得愚蠢。

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

这看起来像是一个 O(N^2) 的解决方案。既然有一个 O(N) 解决方案，让我们使用它，如果您的 JS 运行时不是最新的，您可以轻松修改为不成为生成器。

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

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

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

setMinus time =  181 ms
    diff time =  19099 ms

    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)));

Answer 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()调用来加速代码.

Answer 5

使用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>

Answer 6

我会散列数组B,然后保持B中不存在的数组A中的值:

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;
}

Answer 7

结合 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 行代码来说是不错的回报。

Answer 8

使用Underscore.js（函数式 JS 库）

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

Answer 9

一些简单的功能，借用@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 }

Answer 10

如果您使用Set的是s，它可以非常简单且高效：

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

由于Sets 在底层使用哈希函数*，因此该has函数比indexOf（如果您有超过 100 个项目，这很重要）要快得多。