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

Soit Aet Bsoit deux ensembles. Je recherche des moyens très rapides ou élégants de calculer la différence d'ensemble ( A - Bou A \B, selon vos préférences) entre eux. Les deux ensembles sont stockés et manipulés sous forme de tableaux Javascript, comme l'indique le titre.

Remarques:

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

Edit: J'ai remarqué un commentaire sur les ensembles contenant des éléments en double. Quand je dis «ensemble», je fais référence à la définition mathématique, ce qui signifie (entre autres) qu'ils ne contiennent pas d'éléments en double.

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

A = [1, 2, 3, 4];
B = [1, 3, 4, 7];

diff = A.filter(function(x) { return B.indexOf(x) < 0 })

console.log(diff);

Mis à jour vers ES6:

A = [1, 2, 3, 4];
B = [1, 3, 4, 7];

diff = A.filter(x => !B.includes(x) );

console.log(diff);

Eh bien, 7 ans plus tard, avec l' objet Set d' ES6, c'est assez facile (mais toujours pas aussi compact que celui de python A - B ), et apparemment plus rapide que indexOfpour 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))); 

console.log([...a_minus_b]) // {1}
console.log([...b_minus_a]) // {5}
console.log([...a_intersect_b]) // {2,3,4}

Vous pouvez utiliser un objet comme carte pour éviter de balayer linéairement Bchaque élément Acomme dans la réponse de 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;
}

La toSource()méthode non standard est utilisée pour obtenir des noms de propriétés uniques; si tous les éléments ont déjà des représentations de chaîne uniques (comme c'est le cas avec les nombres), vous pouvez accélérer le code en supprimant les toSource()appels.

Le plus court, en utilisant jQuery, est:

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>

Je hacherais le tableau B, puis conserverais les valeurs du tableau A non présentes dans 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;
}

En incorporant l'idée de Christoph et en supposant quelques méthodes d'itération non standard sur des tableaux et des objets / hachages ( eachet amis), nous pouvons obtenir la différence, l'union et l'intersection en temps linéaire sur environ 20 lignes au total:

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

Cela suppose que eachet filtersont définis pour les tableaux, et que nous avons deux méthodes utilitaires:

• myUtils.keys(hash): retourne un tableau avec les clés du hachage

• myUtils.select(hash, fnSelector, fnEvaluator): renvoie un tableau avec les résultats de l'appel fnEvaluator sur les paires clé / valeur pour lesquelles fnSelectorrenvoie true.

Le select()est vaguement inspiré par Common Lisp, et est simplement filter()et map()roulé en un seul. (Il serait préférable de les définir sur Object.prototype, mais cela fait des ravages avec jQuery, alors j'ai opté pour des méthodes utilitaires statiques.)

Performance: test avec

var a = [], b = [];
for (var i = 100000; i--; ) {
  if (i % 2 !== 0) a.push(i);
  if (i % 3 !== 0) b.push(i);
}

donne deux ensembles de 50 000 et 66 666 éléments. Avec ces valeurs, AB prend environ 75 ms, tandis que l'union et l'intersection sont d'environ 150 ms chacune. (Mac Safari 4.0, utilisant la date Javascript pour le timing.)

Je pense que c'est une récompense décente pour 20 lignes de code.

Utilisation de Underscore.js (bibliothèque pour JS fonctionnel)

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

Quelques fonctions simples, empruntées à la réponse de @ 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]);

Usage:

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 }

En ce qui concerne le jeûne, ce n'est pas si élégant, mais j'ai effectué des tests pour en être sûr. Le chargement d'un tableau en tant qu'objet est beaucoup plus rapide à traiter en grande quantité:

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

Résultats:

completed indexOf in 1219 ms with result 5000 length
completed Object in 8 ms with result 5000 length

Cependant, cela ne fonctionne qu'avec des chaînes . Si vous envisagez de comparer des ensembles numérotés, vous voudrez mapper les résultats avec parseFloat .

Cela fonctionne, mais je pense qu'un autre est beaucoup plus court et élégant aussi

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;