Quelle est la manière la plus rapide ou la plus élégante de calculer une différence d'ensemble en utilisant des tableaux Javascript ?

Question

Sea A y B sont deux ensembles. Je recherche vraiment des méthodes rapides ou élégantes pour calculer la différence d'ensemble ( A - B o A \B selon votre préférence) entre eux. Les deux ensembles sont stockés et manipulés comme des tableaux Javascript, comme l'indique le titre.

Notes :

• Les astuces spécifiques au gecko sont acceptables
• Je préfère m'en tenir aux fonctions natives (mais je suis ouvert à une bibliothèque légère si elle est beaucoup plus rapide).
• Je l'ai vu, mais je ne l'ai pas testé, JS.Set (voir point précédent)

Editer : J'ai remarqué un commentaire sur les ensembles contenant des éléments en double. Lorsque je dis "ensemble", je me réfère à la définition mathématique, ce qui signifie (entre autres) qu'ils ne contiennent pas d'éléments en double.

Answer 1

Je ne sais pas si c'est le plus efficace, mais c'est peut-être le plus court :

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]

Mise à jour vers 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]

Answer 2

Eh bien, 7 ans plus tard, avec Ensemble ES6 c'est assez facile (mais pas aussi compact que l'objet de python A - B ), et serait plus rapide que le indexOf pour les grands tableaux :

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}

Answer 3

En examinant un grand nombre de ces solutions, on constate qu'elles conviennent parfaitement pour les petits cas. Mais lorsque l'on passe à un million d'éléments, la complexité temporelle commence à devenir ridicule.

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

Cela commence à ressembler à une solution O(N^2). Puisqu'il existe une solution O(N), utilisons-la, vous pouvez facilement la modifier pour qu'elle ne soit pas un générateur si vous n'êtes pas à jour sur votre runtime 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)));

Bien que cette solution soit un peu plus complexe que beaucoup d'autres, elle est beaucoup plus rapide lorsque vous avez de grandes listes.

Jetons un coup d'œil rapide à la différence de performance, en l'exécutant sur un ensemble de 1 000 000 d'entiers aléatoires entre 0...10 000, nous obtenons les résultats de performance suivants.

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

Answer 4

Vous pouvez utiliser un objet comme carte pour éviter le balayage linéaire. B pour chaque élément de A comme dans Réponse de l'utilisateur187291 :

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

La norme non standard toSource() méthode est utilisé pour obtenir des noms de propriétés uniques ; si tous les éléments ont déjà une représentation unique sous forme de chaîne de caractères (comme c'est le cas pour les nombres), vous pouvez accélérer le code en supprimant l'élément toSource() invocations.

Answer 5

Si vous utilisez Set il peut être assez simple et performant :

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

Depuis Set utilisent des fonctions Hash* sous le capot, la fonction has est beaucoup plus rapide que la fonction indexOf (c'est important si vous avez, par exemple, plus de 100 articles).