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

Lassen A und B werden zwei Sätze. Ich bin auf der Suche nach wirklich schnell oder elegante Möglichkeiten, um zu berechnen, den Unterschied zwischen (A - B oder A \B je nach Präferenz) zwischen Ihnen. Die beiden sets sind gespeichert und manipuliert werden als Javascript-arrays, wie der Titel sagt.

Hinweise:

Gecko-spezifischen tricks sind okay
Ich würde lieber kleben, um native Funktionen (aber ich bin offen für ein leichtes Bibliothek, wenn es so schneller)
Habe ich gesehen, aber nicht getestet, JS.Set (siehe vorherigen Punkt)

Edit: bemerkte ich einen Kommentar über sets mit doppelten Elemente. Wenn ich sage "der Satz" ich beziehe mich auf die mathematische definition, was bedeutet, dass (unter anderem), dass Sie enthalten keine doppelten Elemente.

InformationsquelleAutor der Frage Matt Ball | 2009-11-12

Nun, 7 Jahre später, mit ES6 - Set Objekt, es ist ganz 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}

InformationsquelleAutor der Antwort milan

16

Können Sie ein Objekt verwenden, als Karte zu vermeiden Linear scanning B für jedes element 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;
}
```
Den nicht-standard - toSource() Methode wird verwendet, um eindeutige Namen für die Eigenschaft; wenn alle Elemente, die bereits eindeutige string-Repräsentationen (wie bei zahlen), können Sie beschleunigen den code, indem Sie die toSource() Aufrufe.

InformationsquelleAutor der Antwort Christoph

Ich würde hash-array B, dann halten Sie Werte 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;
}

InformationsquelleAutor der Antwort Eric Bréchemier

4

Unter Einbeziehung der Idee von Christoph und davon ein paar nicht-standard-Methoden iteration über arrays und Objekte/hashes (each und Freunde), können wir festlegen, Differenz, Vereinigung und Schnittmenge in der linearen Zeit in über 20 Linien insgesamt:
```
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 definiert sind, die für arrays, und wir haben zwei utility-Methoden:
- myUtils.keys(hash): liefert eine
  array mit den Schlüsseln des hash -
- myUtils.select(hash, fnSelector, fnEvaluator): gibt ein array mit
  die Ergebnisse der Aufruf fnEvaluator
  auf das Schlüssel/Wert-Paare für die
  fnSelector true zurück.
Den select() ist lose inspiriert von Common Lisp, und ist nur filter() und map() in eine gerollt. (Es wäre besser, Sie zu haben, definiert Object.prototypeaber so tun, Wracks Verwüstung mit jQuery, also entschied ich mich für statische utility-Methoden.)

Performance: Tests 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 sets mit 50.000 und 66,666 Elemente. Mit diesen Werten A-B dauert etwa 75ms, während union und intersektion sind etwa 150mm jeden. (Mac Safari 4.0 mit Javascript-Datum für das timing.)

Ich denke, das ist anständige Belohnung für die 20 Zeilen code.

InformationsquelleAutor der Antwort j-g-faustus
3

Mit Underscore.js (Bibliothek für funktionales JS)
```
>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]
```
InformationsquelleAutor der Antwort chribsen

Dies funktioniert, aber ich denke, ein weiterer ist viel mehr kürzer und eleganter 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;

InformationsquelleAutor der Antwort Xavi Ivars

Als für die Schnellste Weise, das ist nicht so elegant, aber ich habe einige tests, um sicher zu sein. Laden ein array ein Objekt ist wesentlich schneller zu verarbeiten, in großen Mengen:

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

Ergebnisse:

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

Funktioniert dies jedoch mit strings nur. Wenn Sie planen, vergleichen nummerierte sets werden Sie wollen, um anzeigen Ergebnisse mit parseInt.

InformationsquelleAutor der Antwort SmujMaiku

Einige einfache Funktionen, die 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]);

Verwendung:

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 }

InformationsquelleAutor der Antwort Brian Burns

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.