Pregunta ¿Cuál es la forma más rápida o más elegante de calcular una diferencia establecida mediante matrices de JavaScript?


Dejar A y B ser dos conjuntos. Estoy buscando De Verdad formas rápidas o elegantes de calcular la diferencia establecida (A - B o A \B, dependiendo de su preferencia) entre ellos. Los dos conjuntos se almacenan y manipulan como matrices de JavaScript, como dice el título.

Notas:

  • Los trucos específicos de Gecko están bien
  • Prefiero seguir con las funciones nativas (pero estoy abierto a una biblioteca liviana si es mucho más rápido)
  • He visto, pero no probado, JS.Set (ver punto anterior)

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


75
2017-11-12 15:42


origen


Respuestas:


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.indexOf(x) < 0 );

console.log(diff);


137
2017-11-12 15:50



Bueno, 7 años después, con Conjunto de ES6 objeto es bastante fácil (pero aún no tan compacto como las pitones A - B), y según los informes más rápido que indexOf para grandes arreglos:

let a = new Set([1,2,3,4]);
let b = new Set([5,4,3,2]);

console.log(new Set([...a].filter(x => !b.has(x)))); //a\b => {1}
console.log(new Set([...b].filter(x => !a.has(x)))); //b\a => {5}
console.log(new Set([...a].filter(x => b.has(x))));  //a∩b => {2,3,4}

44
2018-04-08 16:27



Puede usar un objeto como un mapa para evitar el escaneo lineal B para cada elemento de A como en La respuesta 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;
}

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


16
2017-11-12 16:37



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>


9
2017-10-16 07:13



Haría hash a la matriz B, luego mantendré los valores de la matriz A que 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;
}

5
2017-11-12 17:04



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

  • myUtils.keys(hash): devuelve un array con las teclas del hash

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

los select() está libremente inspirado por Common Lisp, y es meramente filter() y map() todo en uno. (Sería mejor tenerlos definidos en Object.prototype, pero hacerlo causó estragos en jQuery, así que me conformé con los 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, A-B tarda unos 75 ms, mientras que la unión y la intersección son de aproximadamente 150 ms cada uno. (Mac Safari 4.0, usando la fecha de Javascript para el tiempo).

Creo que es un pago decente por 20 líneas de código.


4
2017-11-12 16:44



Utilizando Underscore.js (Biblioteca para JS funcional)

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

3
2018-01-02 12:32



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;

1
2017-11-12 16:07