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

Question

Que A y B haber dos conjuntos. Busco realmente maneras rápidas o elegantes para calcular la diferencia de conjuntos (A - B o A \B, dependiendo de su preferencia) entre ellos. Los dos conjuntos son almacenados y manipulados como matrices de JavaScript, como dice el título.

Notas:

• trucos Gecko-específicos están bien
• preferiría pegarse a las funciones nativas (pero estoy abierto a una biblioteca ligera si se trata de manera más rápida)
• que he visto, pero no probado, JS.Set (ver punto anterior)

Editar Noté un comentario acerca de los conjuntos que contienen elementos duplicados. Cuando digo "set" Me refiero a la definición matemática, lo que significa (entre otras cosas) que no contienen elementos duplicados.

Answer 1

Si no se sabe si esto es más eficaz, pero tal vez 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);

Se ha actualizado para ES6:

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

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

console.log(diff);

Answer 2

Bueno, 7 años después, con Conjunto de ES6 objeto es bastante fácil (pero todavía no es tan compacta como pitones a - B), y según se informa más rápido que indexOf para grandes conjuntos:

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

Puede utilizar un objeto como un mapa para evitar linealmente escanear B para cada elemento de A como en user187291 de respuesta :

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 se utiliza para obtener los nombres de propiedades únicas; si todos los elementos ya tienen representaciones de cadena única (como es el caso de los números), se puede acelerar el código dejando caer las invocaciones toSource().

Answer 4

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>

Answer 5

Me hash de la matriz B, a continuación, mantener los valores de la matriz A no está presente 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;
}

Answer 6

La incorporación de la idea de Christoph y asumiendo un par de métodos de iteración no estándar sobre matrices y objetos / hashes (each y amigos), podemos conseguir el sistema diferencia, unión e intersección en el 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 asume que each y filter se definen para las matrices, y que tenemos dos métodos de utilidad:

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

• myUtils.select(hash, fnSelector, fnEvaluator): devuelve una matriz con los resultados de fnEvaluator llamando en el pares clave / valor para el cual fnSelector devuelve verdadero.

El select() está vagamente inspirado por Common Lisp, y es meramente filter() y map() en uno. (Sería mejor tenerlos definidos en Object.prototype, pero hacerlo naufragios estragos con jQuery, por lo que se conformó con métodos de utilidad estáticos.)

Rendimiento: Las pruebas 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 A-B tarda aproximadamente 75 ms, mientras que la unión e intersección son alrededor de 150 ms cada uno. (Mac Safari 4.0, usando Javascript Fecha para medir el tiempo.)

Creo que es ganancia decente para 20 líneas de código.

Answer 7

Uso Underscore.js (Biblioteca para JS funcional)

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

Answer 8

Algunas funciones simples, préstamos de @ respuesta de Milán:

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 }

Answer 9

En cuanto a la forma en ayunas, esto no es tan elegante, pero me he encontrado algunas pruebas para estar seguro. Cargando una matriz como un objeto es mucho más rápido para procesar 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 funciona con cuerdas solamente . Si va a comparar conjuntos numerados usted desea asignar resultados con parseFloat .

Answer 10

Esto funciona, pero creo que el 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;