What is the fastest or most elegant way to compute a set difference using Javascript arrays?

user_139010 0
Viewed 108518

Let A and B be two sets. I'm looking for really fast or elegant ways to compute the set difference (A - B or A \B, depending on your preference) between them. The two sets are stored and manipulated as Javascript arrays, as the title says.

Notes:

  • Gecko-specific tricks are okay
  • I'd prefer sticking to native functions (but I am open to a lightweight library if it's way faster)
  • I've seen, but not tested, JS.Set (see previous point)

Edit: I noticed a comment about sets containing duplicate elements. When I say "set" I'm referring to the mathematical definition, which means (among other things) that they do not contain duplicate elements.

set-difference arrays javascript
14 Answers

Looking at a lof of these solutions, they do fine for small cases. But, when you blow them up to a million items, the time complexity starts getting silly.

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

That starts looking like an O(N^2) solution. Since there is an O(N) solution, let's use it, you can easily modify to not be a generator if you're not up to date on your JS runtime.

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

While this is a bit more complex than many of the other solutions, when you have large lists this will be far faster.

Let's take a quick look at the performance difference, running it on a set of 1,000,000 random integers between 0...10,000 we see the following performance results.

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

user_1914500

If you're using Sets, it can be quite simple and performant:

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

Since Sets use Hash functions* under the hood, the has function is much faster than indexOf (this matters if you have, say, more than 100 items).

user_21025910

The function below are ports of the methods found in Python's set() class and follows the TC39 Set methods proposal.

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

user_17622240

Using core-js to polyfill the New Set methods proposal:

import "core-js"

new Set(A).difference(B)

In theory, the time complexity should be Θ(n), where n is the number of elements in B.

user_4062490
Related