¿Cuál es la forma más rápida o elegante de calcular una diferencia de conjuntos utilizando matrices Javascript?

Sea Ay Bsea ​​dos conjuntos. Estoy buscando formas realmente rápidas o elegantes de calcular la diferencia establecida ( A - Bo A \B, según su preferencia) entre ellas. Los dos conjuntos se almacenan y manipulan como matrices Javascript, como dice el título.

Notas:

• Los trucos específicos de Gecko están bien
• Preferiría ceñirme a las funciones nativas (pero estoy abierto a una biblioteca ligera si es mucho más rápida)
• He visto, pero no probado, JS.Set (ver punto anterior)

Editar: noté un comentario sobre conjuntos que contienen elementos duplicados. Cuando digo "conjunto" me refiero a la definición matemática, lo que significa (entre otras cosas) que no contienen elementos duplicados.

si no sé si esto es más efectivo, pero quizás el más corto

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

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

console.log(diff);

Actualizado a ES6:

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

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

console.log(diff);

Bueno, 7 años después, con el objeto Set de ES6 es bastante fácil (pero aún no tan compacto como el de Python A - B ) y, según se informa, más rápido que indexOfpara arreglos grandes:

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}

Puede usar un objeto como mapa para evitar la exploración lineal Bde cada elemento de Acomo en la respuesta del usuario187291 :

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

El toSource()método no estándar se utiliza para obtener nombres de propiedad únicos; si todos los elementos ya tienen representaciones de cadenas únicas (como es el caso de los números), puede acelerar el código eliminando las toSource()invocaciones.

El más corto, usando jQuery, es:

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>

Haría hash en la matriz B, luego mantendría los valores de la matriz A que no están presentes en 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;
}

Incorporando la idea de Christoph y asumiendo un par de métodos de iteración no estándar en matrices y objetos / hashes ( eachy amigos), podemos obtener la diferencia de conjuntos, la unión y la intersección en tiempo lineal en aproximadamente 20 líneas en 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);
  }
};

Esto supone que eachy filterestán definidos para matrices, y que tenemos dos métodos de utilidad:

• myUtils.keys(hash): devuelve una matriz con las claves del hash

• myUtils.select(hash, fnSelector, fnEvaluator): devuelve una matriz con los resultados de llamar fnEvaluator a los pares clave / valor para los que fnSelectordevuelve verdadero.

El select()está vagamente inspirado en Common Lisp, y es simplemente filter()y map()en uno. (Sería mejor tenerlos definidos Object.prototype, pero hacerlo arruina el caos con jQuery, así que me conformé con métodos de utilidad estáticos).

Rendimiento: prueba con

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

da dos conjuntos con 50.000 y 66.666 elementos. Con estos valores AB tarda unos 75 ms, mientras que la unión y la intersección son de unos 150 ms cada una. (Mac Safari 4.0, usando Javascript Date para la sincronización).

Creo que es una recompensa decente por 20 líneas de código.

Usando Underscore.js (biblioteca para JS funcional)

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

Algunas funciones simples, tomadas de la respuesta 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]);

Uso:

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 cuanto a la forma de ayuno, no es tan elegante, pero he realizado algunas pruebas para estar seguro. La carga de una matriz como objeto es mucho más rápida de procesar en grandes cantidades:

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

Resultados:

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

Sin embargo, esto solo funciona con cadenas . Si planea comparar conjuntos numerados, querrá mapear los resultados con parseFloat .

Esto funciona, pero creo que otro es mucho más corto y elegante también.

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;