Was ist der schnellste oder eleganteste Weg, um einen Satz Unterschied mit Javascript-Arrays zu berechnen?

Question

Let A und B zwei Sätze sein. Ich suche nach wirklich schnelle und elegante Art und Weise die eingestellte Differenz (A - B oder A \B, je nach Vorliebe) zwischen ihnen zu berechnen. Die beiden Sätze werden gespeichert und manipuliert wie Javascript-Arrays, wie der Titel schon sagt.

Weitere Informationen:

• Gecko-spezifische Tricks sind in Ordnung
• Ich würde es vorziehen, auf native Funktionen kleben (aber ich bin offen für eine leichte Bibliothek, wenn es die Art und Weise schneller)
• Ich habe gesehen, aber nicht getestet, JS.Set (siehe vorherigen Punkt)

Edit: , bemerkte ich einen Kommentar über Sets mit doppelten Elemente. Als ich „set“ sagen, ich bin der mathematischen Definition bezieht, die Mittel (unter anderem), dass sie doppelte Elemente nicht enthalten.

Answer 1

Wenn Sie wissen nicht, ob dies ist am effektivsten, aber vielleicht die kürzeste

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

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

console.log(diff);

Aktualisiert ES6:

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

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

console.log(diff);

Answer 2

Nun, 7 Jahre später, mit ES6 der Set Objekt, um es ganz einfach ist, (aber immer noch nicht so wie Pythons A kompakt - B), und angeblich schneller als indexOf für großen Arrays:

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

Sie können ein Objekt als eine Karte verwenden linear B für jedes Element von A wie in user187291 Antwort :

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

Die Nicht-Standard- toSource() Methode wird verwendet, um erhalten einzigartige Eigenschaftsnamen; wenn alle Elemente bereits eindeutige Zeichenfolge Darstellungen haben (wie es der Fall mit Zahlen ist), können Sie den Code durch Fallenlassen der toSource() Anrufungen beschleunigen.

Answer 4

Die kürzeste, mit jQuery, ist:

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

I würde das Array B Hash-Werte dann halten aus dem Array A nicht 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

Die Einbeziehung der Idee von Christoph und unter der Annahme, ein paar Nicht-Standard-Iterationsverfahren auf Arrays und Objekte / Hashes (each und Freunde), können wir Einstelldifferenzdruck, Vereinigung und Schnitt in linearer Zeit in erhalten etwa 20 Zeilen gesamt:

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

Dies setzt voraus, dass each und filter für Arrays definiert, und dass wir zwei Hilfsmethoden:

• myUtils.keys(hash): Gibt ein Array mit den Tasten des Hash

• myUtils.select(hash, fnSelector, fnEvaluator): gibt einen Array mit die Ergebnisse des Aufrufs fnEvaluator auf dem Schlüssel / Wert-Paare, für die fnSelector gibt true zurück.

Die select() wird von Common Lisp lose inspiriert und ist nur filter() und map() in einem. (Es wäre besser, um sie auf Object.prototype definiert zu haben, aber tun so Wracks Verwüstung mit jQuery, so dass ich für statische Hilfsmethoden angesiedelt.)

Performance: Testen mit

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

gibt zwei Sätze mit 50.000 und 66.666 Elementen. Mit diesen Werten A-B dauert etwa 75 ms, während Vereinigung und Durchschnitt etwa 150ms ist jeweils. (Mac Safari 4.0 unter Verwendung von Javascript Datum für Timing.)

Ich denke, das ist anständig Auszahlung für 20 Zeilen Code.

Answer 7

Mit Underscore.js (Bibliothek für funktionelle JS)

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

Answer 8

Einige einfache Funktionen, Kreditaufnahme von @ milan Antwort:

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

Verbrauch:

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

Wie für die gefastet Art und Weise, ist dies nicht so elegant, aber ich habe einige Tests laufen sicher zu sein. Laden ein Array als ein Objekt ist weit schneller Prozess in großen Mengen:

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

Ergebnisse:

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

Dies funktioniert jedoch mit Saiten nur . Wenn Sie zu vergleichen, nummerierte Sätze planen möchten Sie mit den Ergebnissen zur Karte parseFloat .

Answer 10

Das funktioniert, aber ich denke, ein anderes viel kürzer ist, und elegant zu

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;