Qual è il modo più veloce o più elegante per calcolare la differenza insieme utilizzando gli array JavaScript?

Question

Lasciate A e B essere due set. Sto cercando davvero modi veloci o eleganti per calcolare la differenza set (A - B o A \B, a seconda delle preferenze) tra di loro. I due set sono memorizzati e manipolati come array Javascript, come dice il titolo.

Note:

• trucchi Gecko-specifici sono a posto
• preferirei attaccare alle funzioni native (ma sono aperto a una libreria leggera se è il modo più veloce)
• che ho visto, ma non testato, JS.Set (vedi punto precedente)

Modifica Ho notato un commento sui set che contengono elementi duplicati. Quando dico "set" mi riferisco alla definizione matematica, il che significa (tra l'altro) che non contengono elementi duplicati.

Answer 1

se non so se questo è più efficace, ma forse la più breve

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

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

console.log(diff);

Aggiornamento a ES6:

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

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

console.log(diff);

Answer 2

Bene, 7 anni dopo, con Set di ES6 oggetto è abbastanza facile (ma ancora non compatta come pitoni a - B), e secondo come riferito più veloce di indexOf per grandi array:

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

È possibile utilizzare un oggetto come una mappa per evitare linearmente scansione B per ogni elemento di A come in di user187291 risposta :

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

Il metodo toSource() viene utilizzato per ottenere i nomi di proprietà unica; se tutti gli elementi hanno già rappresentazioni di stringa unici (come è il caso con i numeri), è possibile accelerare il codice facendo cadere le invocazioni toSource().

Answer 4

Il più breve, utilizzando jQuery, è:

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

Vorrei hash la matrice B, quindi mantenere i valori dalla matrice A non presenti in 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

Incorporando l'idea da Christoph e assumendo un paio di metodi di iterazione non standard su array e oggetti / hash (each e amici), possiamo ottenere fissati differenza, unione e intersezione in tempo lineare in circa 20 righe in totale:

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

Questo presuppone che each e filter sono definiti per matrici, e che abbiamo due metodi di utilità:

• myUtils.keys(hash): restituisce un array con le chiavi del hash

• myUtils.select(hash, fnSelector, fnEvaluator): restituisce un array con i risultati di fnEvaluator chiamando il tasto / coppie di valori per i quali fnSelector restituisce true.

Il select() è liberamente ispirato da Common Lisp, ed è semplicemente filter() e map() in uno. (Sarebbe meglio averli definiti in Object.prototype, ma in questo modo relitti caos con jQuery, quindi ho optato per metodi di utilità statici.)

Performance: Test con

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

dà due set con 50.000 e 66.666 elementi. Con questi valori A-B richiede circa 75ms, mentre unione e intersezione sono circa 150 ms ciascuno. (Mac Safari 4.0, utilizzando Javascript Data per la temporizzazione.)

Credo che sia profitto decente per 20 righe di codice.

Answer 7

Underscore.js (Biblioteca per JS funzionale)

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

Answer 8

Alcune funzioni semplici, prendendo in prestito da @ risposta di Milano:

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

Utilizzo:

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

Per quanto riguarda il modo in cui digiuno, questo non è così elegante, ma ho eseguito alcuni test per essere sicuri. Caricare una matrice come un oggetto è ben più veloce di trasformare in grandi quantità:

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

Risultati:

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

Tuttavia, questo funziona con stringhe solo . Se avete intenzione di confrontare gli insiemi numerati si desidera mappare i risultati con parseFloat .

Answer 10

Questo funziona, ma penso che un altro è molto più breve, ed elegante anche

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;