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


Lassen A und B zwei Sätze sein. Ich suche Ja wirklich schnelle oder elegante Methoden zur Berechnung der Set-Differenz (A - B oder A \B, je nach Ihrer Präferenz) zwischen ihnen. Die beiden Sätze werden als Javascript-Arrays gespeichert und bearbeitet, wie der Titel sagt.

Anmerkungen:

  • Gecko-spezifische Tricks sind in Ordnung
  • Ich würde lieber native Funktionen beibehalten (aber ich bin offen für eine leichte Bibliothek, wenn es viel schneller ist)
  • Ich habe gesehen, aber nicht getestet, JS.Set (siehe vorheriger Punkt)

Bearbeiten: Ich habe einen Kommentar zu Sets mit doppelten Elementen bemerkt. Wenn ich "set" sage, beziehe ich mich auf die mathematische Definition, was (unter anderem) bedeutet, dass sie keine doppelten Elemente enthalten.


75
2017-11-12 15:42


Ursprung


Antworten:


wenn nicht wissen, ob das am effektivsten ist, aber vielleicht am kürzesten

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

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

console.log(diff);

Auf ES6 aktualisiert:

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



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

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



Sie können ein Objekt als Map verwenden, um ein lineares Scannen zu vermeiden B für jedes Element von A wie in Benutzer187291's 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;
}

Der Nichtstandard toSource() Methode wird verwendet, um eindeutige Eigenschaftennamen zu erhalten; Wenn alle Elemente bereits eindeutige Zeichenfolgendarstellungen haben (wie dies bei Zahlen der Fall ist), können Sie den Code beschleunigen, indem Sie die Taste toSource() Aufrufe.


16
2017-11-12 16:37



Der 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>


9
2017-10-16 07:13



Ich würde das Array B hashen und dann Werte aus dem Array A behalten, die in B nicht vorhanden sind:

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



Einbezug der Idee von Christoph und Übernahme einiger nicht standardisierter Iterationsmethoden für Arrays und Objekte / Hashes (each und Freunde), können wir die Differenz, Vereinigung und Schnittmenge in linearer Zeit in etwa 20 Zeilen insgesamt erhalten:

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 sind für Arrays definiert, und wir haben zwei Hilfsmethoden:

  • myUtils.keys(hash): gibt ein Array mit den Schlüsseln des Hash

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

Das select() ist locker von Common Lisp inspiriert und ist lediglich filter() und map() in einem zusammengerollt. (Es wäre besser, sie zu definieren Object.prototype, aber das macht Wracks mit jQuery verheerend, also entschied ich mich für statische Hilfsmethoden.)

Leistung: 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 dauert A-B etwa 75 ms, während Vereinigung und Schnittpunkt jeweils etwa 150 ms betragen. (Mac Safari 4.0, Verwendung von Javascript-Datum für das Timing.)

Ich denke, das ist eine ordentliche Auszahlung für 20 Zeilen Code.


4
2017-11-12 16:44



Verwenden Underscore.js (Bibliothek für funktionale JS)

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

3
2018-01-02 12:32