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

103

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.

Matt Ball
fuente
¿Cuál es esta terminología de "establecer diferencias" que está utilizando? ¿Eso es de C ++ o algo así?
Josh Stodola
¿Qué hay en tus sets? Dependiendo del tipo al que esté apuntando (por ejemplo, Números), calcular una diferencia establecida se puede hacer de manera muy rápida y elegante. Si sus conjuntos contienen (digamos) elementos DOM, se quedará atascado con una indexOfimplementación lenta .
Crescent Fresh
@Crescent: mis conjuntos contienen números, lo siento por no especificar. @Josh: es la operación estándar establecida en matemáticas ( en.wikipedia.org/wiki/Set_%28mathematics%29#Complements )
Matt Ball
1
@MattBall No, lo vi. Pero la pregunta de Josh era válida y sin respuesta, así que la respondí :)
Pat

Respuestas:

173

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);
usuario187291
fuente
8
+1: no es la solución más eficiente, pero definitivamente es breve y legible
Christoph
10
Nota: array.filter no es compatible con varios navegadores (por ejemplo, no en IE). Parece que a @Matt no le importa, ya que dijo que "los trucos específicos de Gecko están bien", pero creo que vale la pena mencionarlo.
Eric Bréchemier
44
Esto es muy lento. O (| A | * | B |)
glebm
1
@ EricBréchemier Esto ahora es compatible (desde IE 9). Array.prototype.filter es una función estándar de ECMAScript.
Quentin Roy
5
En ES6, podría usar en !B.includes(x)lugar de B.indexOf(x) < 0:)
c24w
86

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}

Milán
fuente
1
También considerablemente más rápido que indexOf para matrices grandes.
Estus Flask
100
Por qué los conjuntos de JavaScript no tienen unión / intersección / diferencia integrada está más allá de mí ...
SwiftsNamesake
6
Estoy completamente de acuerdo; estas deberían ser primitivas de nivel inferior implementadas en el motor js. También me supera ...
Rafael
4
@SwiftsNamesake Hay una propuesta para establecer métodos integrados de los que, con suerte, se hablará en enero de 2018 en github.com/tc39/agendas/blob/master/2018/01.md .
John
15

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.

Christoph
fuente
9

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>

perhelio
fuente
Esto devuelve un objeto de la diferencia.
Drew Baker
2
jQuery notya no funciona con objetos genéricos a partir de 3.0.0-rc1. Ver github.com/jquery/jquery/issues/3147
Marc-André Lafortune
2
No es una gran idea agregar una dependencia en una biblioteca de terceros de ~ 70k solo para hacer esto, ya que se puede lograr lo mismo en solo unas pocas líneas de código como se muestra en las otras respuestas aquí. Sin embargo, si ya está utilizando jQuery en su proyecto, esto funcionará bien.
CBarr
Aunque este enfoque tiene menos código, no proporciona ninguna explicación de la complejidad del espacio y el tiempo de los diferentes algoritmos y la estructura de datos que utiliza para realizar el método. Está en una caja negra para que los desarrolladores diseñen el software sin evaluación cuando se permite la ampliación de datos o con memoria limitada. Si utiliza este enfoque con un gran conjunto de datos, el rendimiento podría permanecer desconocido hasta que se realicen más investigaciones sobre el código fuente.
Downhillski
Esto solo devuelve la cantidad (2 en este caso) de elementos de A que no están en B. Convertir 2 en una matriz no tiene sentido ...
Alex
6

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;
}
Eric Bréchemier
fuente
ese es exactamente el mismo algoritmo que publiqué hace media hora
Christoph
@Christoph: tienes razón ... No me di cuenta de eso. Sin embargo, encuentro que mi implementación es más simple de entender :)
Eric Bréchemier
Creo que es mejor calcular la diferencia fuera de getDifference para que pueda reutilizarse varias veces. Tal vez opcional así:, getDifference(a, b, hashOfB)si no se pasa, se calculará, de lo contrario, se reutilizará como está.
Christophe Roussy
4

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.

jg-faustus
fuente
1
aún debe verificar hasOwnProperty()incluso si los elementos son numéricos: de lo contrario, algo como los Object.prototype[42] = true;medios 42nunca puede ocurrir en el conjunto de resultados
Christoph
Concedido que sería posible establecer 42 de esa manera, pero ¿hay un caso de uso semi-realista en el que alguien realmente lo haría? Pero para las cadenas generales, tomo el punto: podría entrar en conflicto fácilmente con alguna variable o función Object.prototype.
jg-faustus
3

Usando Underscore.js (biblioteca para JS funcional)

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

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 }
Brian Burns
fuente
2

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 .

SmujMaiku
fuente
1
¿No debería ser c = b.filter(function(v) { return !A[v]; });en la segunda función?
fabianmoronzirfas
Estás en lo correcto. De alguna manera parece ser aún más rápido para mí
SmujMaiku
1

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;
Xavi Ivars
fuente