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

Question 1

Lassen A und B zwei Sätze sein. Ich suche Ja wirklich schnelle oder elegante Möglichkeiten, die Mengendifferenz zu berechnen (A - B oder A \B, je nach Wunsch) zwischen ihnen. Die beiden Sätze werden, wie der Titel sagt, als Javascript-Arrays gespeichert und bearbeitet.

Anmerkungen:

Gecko-spezifische Tricks sind in Ordnung
Ich würde es vorziehen, mich an native Funktionen zu halten (aber ich bin offen für eine leichte Bibliothek, wenn sie viel schneller ist)
Ich habe gesehen, aber nicht getestet, JS.Set (siehe vorherigen Punkt)

Bearbeiten: Mir ist ein Kommentar zu Mengen aufgefallen, die doppelte Elemente enthalten. Wenn ich “Set” sage, beziehe ich mich auf die mathematische Definition, was (unter anderem) bedeutet, dass sie keine doppelten Elemente enthalten.

Question 2

wenn ich nicht weiß, ob dies 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);

Aktualisiert auf ES6:

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

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

console.log(diff);

Question 3

Nun, 7 Jahre später, mit ES6-Set Objekt ist es ganz einfach (aber immer noch nicht so kompakt wie Pythons A - B) und angeblich schneller als indexOf für große 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}

Question 4

Sie können ein Objekt als Karte verwenden, um ein lineares Scannen zu vermeiden B für jedes Element von A wie in der Antwort von user187291:

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 Nicht-Standard toSource() Methode wird verwendet, um eindeutige Eigenschaftsnamen zu erhalten; Wenn alle Elemente bereits eindeutige Zeichenfolgendarstellungen haben (wie es bei Zahlen der Fall ist), können Sie den Code beschleunigen, indem Sie das löschen toSource() Anrufungen.

Question 5

Wenn Sie sich viele dieser Lösungen ansehen, eignen sie sich gut für kleine Fälle. Aber wenn Sie sie auf eine Million Elemente aufblähen, wird die Zeitkomplexität albern.

 A.filter(v => B.includes(v))

Das sieht aus wie eine O(N^2)-Lösung. Da es eine O(N)-Lösung gibt, lassen Sie uns sie verwenden, können Sie leicht ändern, dass sie kein Generator ist, wenn Sie mit Ihrer JS-Laufzeit nicht auf dem neuesten Stand sind.

    function *setMinus(A, B) {
      const setA = new Set(A);
      const setB = new Set(B);

      for (const v of setB.values()) {
        if (!setA.delete(v)) {
            yield v;
        }
      }

      for (const v of setA.values()) {
        yield v;
      }
    }

    a = [1,2,3];
    b = [2,3,4];

    console.log(Array.from(setMinus(a, b)));

Dies ist zwar etwas komplexer als viele der anderen Lösungen, aber wenn Sie große Listen haben, wird dies viel schneller sein.

Werfen wir einen kurzen Blick auf den Leistungsunterschied, indem wir ihn mit einem Satz von 1.000.000 zufälligen ganzen Zahlen zwischen 0 und 10.000 ausführen, sehen wir die folgenden Leistungsergebnisse.

setMinus time =  181 ms
    diff time =  19099 ms

function buildList(count, range) {
  result = [];
  for (i = 0; i < count; i++) {
    result.push(Math.floor(Math.random() * range))
  }
  return result;
}

function *setMinus(A, B) {
  const setA = new Set(A);
  const setB = new Set(B);

  for (const v of setB.values()) {
    if (!setA.delete(v)) {
        yield v;
    }
  }

  for (const v of setA.values()) {
    yield v;
  }
}

function doDiff(A, B) {
  return A.filter(function(x) { return B.indexOf(x) < 0 })
}

const listA = buildList(100_000, 100_000_000); 
const listB = buildList(100_000, 100_000_000); 

let t0 = process.hrtime.bigint()

const _x = Array.from(setMinus(listA, listB))

let t1 = process.hrtime.bigint()

const _y = doDiff(listA, listB)

let t2 = process.hrtime.bigint()

console.log("setMinus time = ", (t1 - t0) / 1_000_000n, "ms");
console.log("diff time = ", (t2 - t1) / 1_000_000n, "ms");

Question 6

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

Question 7

Wenn Sie verwenden Sets, es kann ganz einfach und performant sein:

function setDifference(a, b) {
  return new Set(Array.from(a).filter(item => !b.has(item)));
}

Seit Sets verwenden Hash-Funktionen* unter der Haube, die has Funktion ist viel schneller als indexOf (Dies ist wichtig, wenn Sie beispielsweise mehr als 100 Artikel haben).

Question 8

Ich würde das Array B hashen und dann Werte aus dem Array A behalten, die nicht in B 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;
}