javascript - sirve - script html ejemplos

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

Question

Deje que A y B sean dos conjuntos. Estoy buscando maneras realmente rápidas o elegantes de calcular la diferencia establecida ( A - B o A /B , según su preferencia) entre ellas. 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.

Answer 1

Al incorporar la idea de Christoph y suponer un par de métodos de iteración no estándar en matrices y objetos / hashes ( each y amigos), podemos establecer la diferencia, unión e 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 están definidos para matrices, y que tenemos dos métodos de utilidad:

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

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

El select() está ligeramente inspirado por Common Lisp, y es meramente filter() y map() enrollado en uno. (Sería mejor tenerlos definidos en Object.prototype , pero hacerlo arruina el 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, AB 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.

Answer 2

Algunas funciones simples, tomando prestado 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 }

Answer 3

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

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}

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

En cuanto a la forma de ayunar, esto no es tan elegante, pero he realizado algunas pruebas para estar seguro. Cargar una matriz como un objeto es mucho más rápido de procesar en grandes cantidades:

var t, a, b, c, A;

    // 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();
A = {};
a.forEach(function(v) { A[v] = true; });
c = b.filter(function(v) { return !a[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 solo con cadenas . Si planea comparar conjuntos numerados, querrá mapear resultados con parseInt .

Answer 6

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;

Answer 7

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

Answer 8

Puede usar este ligero componente de código abierto array-diff .

Ejemplo:

diff([1,2,3], [1,2,3,4,5]) // => [4,5]

Funciona mediante la concatenación de las dos matrices aprobadas y el filtrado incluido vals, devolviendo una matriz que representa la diferencia entre las dos matrices:

function diff(firstArray: any[], secondArray: any[]): any[] {
  return firstArray.concat(secondArray).filter((val) => {
    return !(firstArray.includes(val) && secondArray.includes(val));
  });
};

Answer 9

Puede usar un objeto como un mapa para evitar escanear linealmente B para cada elemento de A como 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 método toSource() no estándar 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 toSource() invocaciones de toSource() .

Answer 10

Usando Underscore.js (Biblioteca para JS funcional)

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

Answer 11

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