Wie kann man den Unterschied zwischen zwei Arrays in JavaScript ermitteln?

752

Gibt es eine Möglichkeit, den Unterschied zwischen zwei Arrays in JavaScript zurückzugeben?

Zum Beispiel:

var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];

// need ["c", "d"]
John Adawan
quelle
9
Symmetrisch oder nicht symmetrisch?
Leichtigkeitsrennen im Orbit
Mit der neuen ES6-Funktion kann dies als einfacher Einzeiler erfolgen (die Verwendung in allen gängigen Browsern nimmt viel Zeit in Anspruch). Überprüfen Sie auf jeden Fall meine Antwort
Salvador Dali
1
Ein wichtiger Aspekt der Lösung ist die Leistung. Die asymptotische zeitliche Komplexität dieser Art von Operation - in anderen Sprachen - ist O(a1.length x log(a2.length))- ist diese Leistung in JavaScript möglich?
Raul

Antworten:

219

Ich gehe davon aus, dass Sie ein normales Array vergleichen. Wenn nicht, müssen Sie die for- Schleife in eine for .. in- Schleife ändern .

function arr_diff (a1, a2) {

    var a = [], diff = [];

    for (var i = 0; i < a1.length; i++) {
        a[a1[i]] = true;
    }

    for (var i = 0; i < a2.length; i++) {
        if (a[a2[i]]) {
            delete a[a2[i]];
        } else {
            a[a2[i]] = true;
        }
    }

    for (var k in a) {
        diff.push(k);
    }

    return diff;
}

console.log(arr_diff(['a', 'b'], ['a', 'b', 'c', 'd']));
console.log(arr_diff("abcd", "abcde"));
console.log(arr_diff("zxc", "zxc"));

Eine bessere Lösung ist die Verwendung von Filtern, wenn Sie sich nicht für die Abwärtskompatibilität interessieren. Trotzdem funktioniert diese Lösung.

Denker
quelle
46
Dies mag funktionieren, führt jedoch drei Schleifen durch, um mithilfe der Filtermethode von Array zu erreichen, was in einer Codezeile möglich ist.
Joshaven Potter
9
Um klar zu sein, implementiert dies die symmetrische Differenz von a1 und a2 im Gegensatz zu den anderen hier veröffentlichten Antworten.
200_erfolg
25
Dies ist nicht die beste Antwort, aber ich gebe ihr eine positive Gegenstimme, um die unfairen Abstimmungen auszugleichen. Nur falsche Antworten sollten herabgestuft werden, und wenn ich an einem Projekt mit Cruft-Browsern im Umfang arbeite (schwierige Zeiten passieren), könnte diese Antwort sogar hilfreich sein.
Michael Scheper
3
Darf ich weiß , was passieren wird , wenn var a1 = ['a', 'b'];und var a2 = ['a', 'b', 'c', 'd', 'b'];, wird es falsche Antwort zurückgeben , dh ['c', 'd', 'b']statt ['c', 'd'].
skbly7
4
Der schnellste Weg ist die offensichtlich naivste Lösung. Ich habe alle vorgeschlagenen Lösungen für symmetrische Unterschiede in diesem Thread getestet und der Gewinner ist:function diff2(a, b) { var i, la = a.length, lb = b.length, res = []; if (!la) return b; else if (!lb) return a; for (i = 0; i < la; i++) { if (b.indexOf(a[i]) === -1) res.push(a[i]); } for (i = 0; i < lb; i++) { if (a.indexOf(b[i]) === -1) res.push(b[i]); } return res; }
Nomaed
1231

Es gibt einen besseren Weg mit ES7:


Überschneidung

 let intersection = arr1.filter(x => arr2.includes(x));

Schnittpunktdifferenz Venn-Diagramm

Denn [1,2,3] [2,3]es wird nachgeben [2,3]. Auf der anderen Seite wird for [1,2,3] [2,3,5]das Gleiche zurückgeben.


Unterschied

let difference = arr1.filter(x => !arr2.includes(x));

Richtiger Unterschied Venn-Diagramm

Denn [1,2,3] [2,3]es wird nachgeben [1]. Auf der anderen Seite wird for [1,2,3] [2,3,5]das Gleiche zurückgeben.


Für einen symmetrischen Unterschied können Sie Folgendes tun:

let difference = arr1
                 .filter(x => !arr2.includes(x))
                 .concat(arr2.filter(x => !arr1.includes(x)));

Symmetrischer Unterschied Venn-Diagramm

Auf diese Weise erhalten Sie ein Array, das alle Elemente von arr1 enthält, die nicht in arr2 enthalten sind, und umgekehrt

Wie @Joshaven Potter in seiner Antwort betonte, können Sie dies zu Array.prototype hinzufügen, damit es wie folgt verwendet werden kann:

Array.prototype.diff = function(arr2) { return this.filter(x => !arr2.includes(x)); }
[1, 2, 3].diff([2, 3])
Luis Sieira
quelle
3
Ich bevorzuge es zu überprüfen < 0anstatt== -1
Vic
1
Die Berechnung der ArrayDifferenz wird als so genannte bezeichnet set operation, da die Suche nach Eigenschaften die eigene Aufgabe von Sets ist, die um Größenordnungen schneller sind als indexOf/ includes. Einfach ausgedrückt ist Ihre Lösung sehr ineffizient und ziemlich langsam.
@ftor aber mit Set, Werte müssen eindeutig sein, nein?
CervEd
1
@LuisSieira Ich verstehe, dass es funktionieren würde, vorausgesetzt [1,2,3] [2,3,5], die Zahlen sind eindeutig, aber wenn Sie gesagt [1,1,2,3] [1,2,3,5]und erwartet hätten [1], könnten Sie nicht verwenden Set. Ihre Lösung würde aber auch nicht funktionieren: - / Am Ende habe ich diese Funktion erstellt, weil ich keinen zufriedenstellenden Weg gefunden habe, dies prägnanter zu machen. Wenn Sie Ideen dazu haben, würde ich gerne wissen!
CervEd
3
Ist Array.includes()ES7 nicht Funktion statt ES6? (1) (2) - und um fortzufahren, könnten Sie mit ES6 Array.some()zB let intersection = aArray.filter(a => bArray.some(b => a === b))nein verwenden?
Jari Keinänen
910
Array.prototype.diff = function(a) {
    return this.filter(function(i) {return a.indexOf(i) < 0;});
};

////////////////////  
// Examples  
////////////////////

[1,2,3,4,5,6].diff( [3,4,5] );  
// => [1, 2, 6]

["test1", "test2","test3","test4","test5","test6"].diff(["test1","test2","test3","test4"]);  
// => ["test5", "test6"]

Hinweis indexOf und Filter sind in dh vor ie9 nicht verfügbar.

Joshaven Potter
quelle
50
Der einzige wichtige Browser, der Filter und indexOf nicht unterstützt, ist IE8. IE9 unterstützt beide. Es ist also nicht falsch.
Bryan Larsen
14
ie7 und ie8 sind (leider) immer noch sehr relevant, jedoch finden Sie Polyfill-Code für beide Funktionen auf der MDN-Site: developer.mozilla.org/en/JavaScript/Reference/Global_Objects/… developer.mozilla.org/en/JavaScript/ Referenz / Global_Objects /… Laden Sie den unter "Kompatibilität" aufgeführten Code über eine IE-Bedingung & BOOM. Ie7 / 8 werden unterstützt.
1nfiniti
44
Diese Lösung hat eine Laufzeit von O (n ^ 2), eine lineare Lösung wäre weitaus effizienter.
Jholloman
75
Wenn Sie die Funktion wie [1,2,3].diff([3,4,5])folgt verwenden : Sie wird zurückgegeben, [1,2]anstatt [1,2,4,5]das Problem in der ursprünglichen Frage nicht zu lösen. Beachten Sie dies.
Bugster
12
@AlinPurcaru Wird von archaischen Browsern nicht unterstützt! = Falsch. In Anbetracht von Netscape 2.0 ist der größte Teil des JS-Codes hier nach dieser Definition "falsch". Es ist eine dumme Sache zu sagen.
NullUserException
304

Dies ist bei weitem der einfachste Weg, mit jQuery genau das gewünschte Ergebnis zu erzielen:

var diff = $(old_array).not(new_array).get();

diffjetzt enthält was drin war was old_arraynicht drin istnew_array

superphonisch
quelle
4
@ Batman Ja, aber nur, wenn sie auf dasselbe Objekt verweisen ( {a: 1} != {a: 1}) ( Beweis )
Matmarbon
Ist es möglich, es mit Arrays zu verwenden, die Daten eines benutzerdefinierten Objekts enthalten? Ich habe es tatsächlich genauso versucht, aber es hat nicht funktioniert. Alle Ideen werden sehr dankbar sein.
LetMeCodeYou
8
Ist das ein Trick? Das Dokument betrachtet diese Methode als Teil der DOM-Elementmethoden und nicht als allgemeinen Array-Helfer. So könnte es jetzt funktionieren, aber vielleicht nicht in zukünftigen Versionen, da es nicht beabsichtigt war, es auf diese Weise zu verwenden. Obwohl ich mich freuen würde, wenn es offiziell ein allgemeiner Array-Helfer wäre.
Robsch
1
@robsch Bei Verwendung .notmit einem Array verwendet jQuery das integrierte Dienstprogramm, .grep()das speziell zum Filtern von Arrays vorgesehen ist. Ich kann nicht sehen, dass sich das ändert.
Superphonic
1
@vsync Klingt wie Sie nach einem symmetrischen Unterschied sind
superphonic
158

Die Differenzmethode in Unterstrich (oder deren Drop-In-Ersatz, Lo-Dash ) kann dies auch:

(R)eturns the values from array that are not present in the other arrays

_.difference([1, 2, 3, 4, 5], [5, 2, 10]);
=> [1, 3, 4]

Wie bei jeder Unterstreichungsfunktion können Sie sie auch in einem objektorientierteren Stil verwenden:

_([1, 2, 3, 4, 5]).difference([5, 2, 10]);
Mahemoff
quelle
4
Ich denke, es ist eine gute Lösung in Bezug auf die Leistung, zumal Lodash und Unterstrich immer wieder um die beste Implementierung kämpfen. Es ist auch IE6-kompatibel.
Mahemoff
4
Beachten Sie, dass diese Implementierung für Arrays von Objekten nicht funktioniert. Weitere Informationen finden Sie unter stackoverflow.com/q/8672383/14731 .
Gili
1
Wie in einer der Antworten dort erwähnt, funktioniert es, wenn es sich um dasselbe Objekt handelt, nicht jedoch, wenn zwei Objekte dieselben Eigenschaften haben. Ich denke, das ist in Ordnung, da die Vorstellungen von Gleichheit variieren (z. B. könnte es in einigen Apps auch ein "id" -Attribut sein). Es wäre jedoch gut, wenn Sie einen Vergleichstest für intersect () bestehen könnten.
Mahemoff
Für die Nachwelt: Lodash hat jetzt _.differenceBy (), das einen Rückruf benötigt, um den Vergleich durchzuführen. Wenn Sie Objekte vergleichen, können Sie eine Funktion hinzufügen, die sie nach Bedarf vergleicht.
SomeCallMeTim
2
Seien Sie vorsichtig, wenn die Reihenfolge der Argumente umgekehrt wird, es wird nicht funktionieren. z.B. Unterschied ([5, 2, 10], [1, 2, 3, 4, 5]); kann das diff nicht bekommen
Russj
79

Einfaches JavaScript

Es gibt zwei mögliche Interpretationen für "Unterschied". Ich lasse Sie wählen, welche Sie wollen. Angenommen, Sie haben:

var a1 = ['a', 'b'     ];
var a2 = [     'b', 'c'];
  1. Wenn Sie erhalten möchten ['a'], verwenden Sie diese Funktion:

    function difference(a1, a2) {
      var result = [];
      for (var i = 0; i < a1.length; i++) {
        if (a2.indexOf(a1[i]) === -1) {
          result.push(a1[i]);
        }
      }
      return result;
    }
  2. Wenn Sie erhalten möchten ['a', 'c'](alle Elemente, die in einem a1 oder a2, aber nicht in beiden enthalten sind - die sogenannte symmetrische Differenz ), verwenden Sie diese Funktion:

    function symmetricDifference(a1, a2) {
      var result = [];
      for (var i = 0; i < a1.length; i++) {
        if (a2.indexOf(a1[i]) === -1) {
          result.push(a1[i]);
        }
      }
      for (i = 0; i < a2.length; i++) {
        if (a1.indexOf(a2[i]) === -1) {
          result.push(a2[i]);
        }
      }
      return result;
    }

Lodash / Unterstrich

Wenn Sie lodash verwenden, können Sie _.difference(a1, a2)(Fall 1 oben) oder _.xor(a1, a2)(Fall 2) verwenden.

Wenn Sie Underscore.js verwenden, können Sie die _.difference(a1, a2)Funktion für Fall 1 verwenden.

ES6-Set für sehr große Arrays

Der obige Code funktioniert in allen Browsern. Bei großen Arrays mit mehr als 10.000 Elementen wird es jedoch ziemlich langsam, da es eine O (n²) -Komplexität aufweist. In vielen modernen Browsern können wir das ES6- SetObjekt nutzen, um die Dinge zu beschleunigen. Lodash wird automatisch verwendet, Setwenn es verfügbar ist. Wenn Sie lodash nicht verwenden, verwenden Sie die folgende Implementierung, die vom Blog-Beitrag von Axel Rauschmayer inspiriert wurde :

function difference(a1, a2) {
  var a2Set = new Set(a2);
  return a1.filter(function(x) { return !a2Set.has(x); });
}

function symmetricDifference(a1, a2) {
  return difference(a1, a2).concat(difference(a2, a1));
}

Anmerkungen

Das Verhalten für alle Beispiele kann überraschend oder nicht offensichtlich sein, wenn Sie sich für -0, +0, NaN oder spärliche Arrays interessieren . (Für die meisten Anwendungen spielt dies keine Rolle.)

Jo Liss
quelle
Danken. du hast meinen Tag gerettet. Ich musste 300K-Arrays vergleichen, und Ihre "Set" -Lösung funktionierte perfekt. Dies sollte die akzeptierte Antwort sein.
Justadev
52

Um den symmetrischen Unterschied zu erhalten , müssen Sie die Arrays auf beide Arten vergleichen (oder auf alle Arten bei mehreren Arrays).

Geben Sie hier die Bildbeschreibung ein


ES7 (ECMAScript 2016)

// diff between just two arrays:
function arrayDiff(a, b) {
    return [
        ...a.filter(x => !b.includes(x)),
        ...b.filter(x => !a.includes(x))
    ];
}

// diff between multiple arrays:
function arrayDiff(...arrays) {
    return [].concat(...arrays.map( (arr, i) => {
        const others = arrays.slice(0);
        others.splice(i, 1);
        const unique = [...new Set([].concat(...others))];
        return arr.filter(x => !unique.includes(x));
    }));
}

ES6 (ECMAScript 2015)

// diff between just two arrays:
function arrayDiff(a, b) {
    return [
        ...a.filter(x => b.indexOf(x) === -1),
        ...b.filter(x => a.indexOf(x) === -1)
    ];
}

// diff between multiple arrays:
function arrayDiff(...arrays) {
    return [].concat(...arrays.map( (arr, i) => {
        const others = arrays.slice(0);
        others.splice(i, 1);
        const unique = [...new Set([].concat(...others))];
        return arr.filter(x => unique.indexOf(x) === -1);
    }));
}

ES5 (ECMAScript 5.1)

// diff between just two arrays:
function arrayDiff(a, b) {
    var arrays = Array.prototype.slice.call(arguments);
    var diff = [];

    arrays.forEach(function(arr, i) {
        var other = i === 1 ? a : b;
        arr.forEach(function(x) {
            if (other.indexOf(x) === -1) {
                diff.push(x);
            }
        });
    })

    return diff;
}

// diff between multiple arrays:
function arrayDiff() {
    var arrays = Array.prototype.slice.call(arguments);
    var diff = [];

    arrays.forEach(function(arr, i) {
        var others = arrays.slice(0);
        others.splice(i, 1);
        var otherValues = Array.prototype.concat.apply([], others);
        var unique = otherValues.filter(function (x, j) { 
            return otherValues.indexOf(x) === j; 
        });
        diff = diff.concat(arr.filter(x => unique.indexOf(x) === -1));
    });
    return diff;
}

Beispiel:

// diff between two arrays:
const a = ['a', 'd', 'e'];
const b = ['a', 'b', 'c', 'd'];
arrayDiff(a, b); // (3) ["e", "b", "c"]

// diff between multiple arrays
const a = ['b', 'c', 'd', 'e', 'g'];
const b = ['a', 'b'];
const c = ['a', 'e', 'f'];
arrayDiff(a, b, c); // (4) ["c", "d", "g", "f"]

Unterschied zwischen Arrays von Objekten

function arrayDiffByKey(key, ...arrays) {
    return [].concat(...arrays.map( (arr, i) => {
        const others = arrays.slice(0);
        others.splice(i, 1);
        const unique = [...new Set([].concat(...others))];
        return arr.filter( x =>
            !unique.some(y => x[key] === y[key])
        );
    }));
}

Beispiel:

const a = [{k:1}, {k:2}, {k:3}];
const b = [{k:1}, {k:4}, {k:5}, {k:6}];
const c = [{k:3}, {k:5}, {k:7}];
arrayDiffByKey('k', a, b, c); // (4) [{k:2}, {k:4}, {k:6}, {k:7}]
Luca Borrione
quelle
50

Ein sauberer Ansatz in ES6 ist die folgende Lösung.

var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];

Unterschied

a2.filter(d => !a1.includes(d)) // gives ["c", "d"]

Überschneidung

a2.filter(d => a1.includes(d)) // gives ["a", "b"]

Disjunktive Union (symmetrischer Unterschied)

[ ...a2.filter(d => !a1.includes(d)),
  ...a1.filter(d => !a2.includes(d)) ]
ifelse.codes
quelle
Es funktioniert nur in eine Richtung. Stellen Sie sich nun vor a1 = ['a', 'b', 'e']: e wird nicht extrahiert.
Imrok
Ja, so funktioniert der Unterschied in der Mengenlehre. (a2 -a1) Was Sie suchen, ist (a2-a1) + (a1-a2)
ifelse.codes
1
@imrok Ich glaube, das ist es, wonach Sie suchen [... a2.filter (d =>! a1.includes (d)), ... (a1.filter (d =>! a2.includes (d)) )]
ifelse.codes
2
Schöne Lösung, danke!
Thiago Alves
40

In diesem Fall können Sie ein Set verwenden . Es ist für diese Art von Operation (Vereinigung, Schnittmenge, Differenz) optimiert.

Stellen Sie sicher, dass dies für Ihren Fall gilt, sobald keine Duplikate mehr zulässig sind.

var a = new JS.Set([1,2,3,4,5,6,7,8,9]);
var b = new JS.Set([2,4,6,8]);

a.difference(b)
// -> Set{1,3,5,7,9}
Samuel Carrijo
quelle
4
Das sieht aus wie eine schöne Bibliothek! Was für eine Schande, dass Sie nicht nur die SetFunktion herunterladen können, ohne alles andere bekommen zu müssen ...
Blixt
@Blixt Ich glaube, Sie können alles herunterladen und nur die Datei set.js einschließen
Samuel Carrijo
Set ist auch in Google Closure implementiert. Closure-library.googlecode.com/svn/docs/…
Ben Flynn
32
function diff(a1, a2) {
  return a1.concat(a2).filter(function(val, index, arr){
    return arr.indexOf(val) === arr.lastIndexOf(val);
  });
}

Wenn Sie beide Arrays zusammenführen, werden eindeutige Werte nur einmal angezeigt, sodass indexOf () mit lastIndexOf () identisch ist.

pdbrito
quelle
3
Ich bin damit einverstanden, dass dies der sauberste und einfachste Weg ist und dass es nicht erforderlich ist, den Prototyp zu berühren. "Wenn du es einem Sechsjährigen nicht erklären kannst, verstehst du es selbst nicht." - Albert Einstein
Lacostenycoder
18

Um ein Array von einem anderen zu subtrahieren, verwenden Sie einfach das folgende Snippet:

var a1 = ['1','2','3','4','6'];
var a2 = ['3','4','5'];

var items = new Array();

items = jQuery.grep(a1,function (item) {
    return jQuery.inArray(item, a2) < 0;
});

Es werden ['1,' 2 ',' 6 '] zurückgegeben, die Elemente des ersten Arrays sind, die im zweiten nicht vorhanden sind.

Entsprechend Ihrem Problembeispiel ist daher der folgende Code die genaue Lösung:

var array1 = ["test1", "test2","test3", "test4"];
var array2 = ["test1", "test2","test3","test4", "test5", "test6"];

var _array = new Array();

_array = jQuery.grep(array2, function (item) {
     return jQuery.inArray(item, array1) < 0;
});
Al___
quelle
14

Mit der Ankunft von ES6 mit Sets und Splat-Operator (zum Zeitpunkt der Arbeit nur in Firefox, überprüfen Sie die Kompatibilitätstabelle ) können Sie den folgenden Liner schreiben:

var a = ['a', 'b', 'c', 'd'];
var b = ['a', 'b'];
var b1 = new Set(b);
var difference = [...new Set([...a].filter(x => !b1.has(x)))];

was dazu führen wird [ "c", "d" ].

Salvador Dali
quelle
Nur neugierig, wie ist das anders als zu tunb.filter(x => !a.indexOf(x)))
chovy
1
@chovy es ist anders in der zeitlichen Komplexität. Meine Lösung ist O(n + m)Ihre Lösung, O(n * m)bei der n und m die Länge von Arrays sind. Nehmen Sie lange Listen und meine Lösung wird in Sekunden ausgeführt, während Ihre Stunden dauern wird.
Salvador Dali
Was ist mit dem Vergleichen eines Attributs einer Liste von Objekten? Ist das mit dieser Lösung möglich?
Chovy
2
a.filter(x => !b1.has(x))ist einfacher. Und beachten Sie die Spezifikation nur die Komplexität erfordert zu sein n * f(m) + mmit f(m)sublinear im Durchschnitt. Es ist besser als n * m, aber nicht unbedingt n + m.
Oriol
2
@SalvadorDali var difference = [...new Set([...a].filter(x => !b1.has(x)))];Warum erstellen Sie ein doppeltes ' a' -Array? Warum verwandeln Sie das Ergebnis des Filters in eine Menge und dann wieder in ein Array? Ist das nicht gleichbedeutend mitvar difference = a.filter(x => !b1.has(x));
Deepak Mittal
13

Funktionsansatz mit ES2015

Das Berechnen der differencezwischen zwei Arrays ist eine der SetOperationen. Der Begriff gibt bereits an, dass der native SetTyp verwendet werden sollte, um die Suchgeschwindigkeit zu erhöhen. Auf jeden Fall gibt es drei Permutationen, wenn Sie die Differenz zwischen zwei Mengen berechnen:

[+left difference] [-intersection] [-right difference]
[-left difference] [-intersection] [+right difference]
[+left difference] [-intersection] [+right difference]

Hier ist eine funktionale Lösung, die diese Permutationen widerspiegelt.

Links difference:

// small, reusable auxiliary functions

const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));


// left difference

const differencel = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? false
     : true
  ) (xs);
};


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// run the computation

console.log( differencel(xs) (ys) );

Richtig difference:

differencerist trivial. Es ist nur differencelmit umgedrehten Argumenten. Sie können der Einfachheit halber eine Funktion schreiben : const differencer = flip(differencel). Das ist alles!

Symmetrisch difference:

Jetzt, da wir die linke und die rechte haben, wird die Implementierung der Symmetrie ebenfalls differencetrivial:

// small, reusable auxiliary functions

const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const concat = y => xs => xs.concat(y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));


// left difference

const differencel = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? false
     : true
  ) (xs);
};


// symmetric difference

const difference = ys => xs =>
 concat(differencel(xs) (ys)) (flip(differencel) (xs) (ys));

// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// run the computation

console.log( difference(xs) (ys) );

Ich denke, dieses Beispiel ist ein guter Ausgangspunkt, um einen Eindruck davon zu bekommen, was funktionale Programmierung bedeutet:

Programmieren mit Bausteinen, die auf viele verschiedene Arten miteinander verbunden werden können.


quelle
12

Eine Lösung mit indexOf()ist für kleine Arrays in Ordnung, aber mit zunehmender Länge nähert sich die Leistung des Algorithmus an O(n^2). Hier ist eine Lösung, die bei sehr großen Arrays eine bessere Leistung erzielt, indem Objekte als assoziative Arrays zum Speichern der Array-Einträge als Schlüssel verwendet werden. Es werden auch doppelte Einträge automatisch entfernt, es funktioniert jedoch nur mit Zeichenfolgenwerten (oder Werten, die sicher als Zeichenfolgen gespeichert werden können):

function arrayDiff(a1, a2) {
  var o1={}, o2={}, diff=[], i, len, k;
  for (i=0, len=a1.length; i<len; i++) { o1[a1[i]] = true; }
  for (i=0, len=a2.length; i<len; i++) { o2[a2[i]] = true; }
  for (k in o1) { if (!(k in o2)) { diff.push(k); } }
  for (k in o2) { if (!(k in o1)) { diff.push(k); } }
  return diff;
}

var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];
arrayDiff(a1, a2); // => ['c', 'd']
arrayDiff(a2, a1); // => ['c', 'd']
Maerics
quelle
Sie möchten Object.hasOwnProperty () verwenden, wenn Sie ein "for in" für ein Objekt ausführen. Andernfalls besteht die Gefahr, dass Sie alle Felder durchlaufen, die dem Prototyp des Standardobjekts hinzugefügt wurden. (Oder nur das übergeordnete Objekt Ihres Objekts) Außerdem benötigen Sie nur zwei Schleifen, eine für die Erstellung einer Hash-Tabelle, und die andere sucht in dieser Hash-Tabelle nach.
Jholloman
1
@ jholloman Ich bin respektvoll anderer Meinung . Jetzt, da wir die Aufzählbarkeit für jede Eigenschaft steuern können, sollten Sie vermutlich jede Eigenschaft einbeziehen, die Sie während der Aufzählung erhalten.
Phrogz
1
@Phrogz Ein guter Punkt, wenn Sie sich nur um moderne Browser sorgen. Leider muss ich bei der Arbeit wieder auf IE7 zurückgreifen, so dass die Steinzeit mein Standardgedanke ist und wir keine Shims verwenden.
jholloman
10

Die obige Antwort von Joshaven Potter ist großartig. Es werden jedoch Elemente in Array B zurückgegeben, die sich nicht in Array C befinden, aber nicht umgekehrt. Wenn var a=[1,2,3,4,5,6].diff( [3,4,5,7]);dann zum Beispiel Folgendes ausgegeben wird: ==> [1,2,6], aber nicht [1,2,6,7] , was der tatsächliche Unterschied zwischen den beiden ist. Sie können weiterhin den obigen Potter-Code verwenden, aber den Vergleich auch einmal rückwärts wiederholen:

Array.prototype.diff = function(a) {
    return this.filter(function(i) {return !(a.indexOf(i) > -1);});
};

////////////////////  
// Examples  
////////////////////

var a=[1,2,3,4,5,6].diff( [3,4,5,7]);
var b=[3,4,5,7].diff([1,2,3,4,5,6]);
var c=a.concat(b);
console.log(c);

Dies sollte Folgendes ausgeben: [ 1, 2, 6, 7 ]

user1685068
quelle
9

Ein anderer Weg, um das Problem zu lösen

function diffArray(arr1, arr2) {
    return arr1.concat(arr2).filter(function (val) {
        if (!(arr1.includes(val) && arr2.includes(val)))
            return val;
    });
}

diffArray([1, 2, 3, 7], [3, 2, 1, 4, 5]);    // return [7, 4, 5]

Sie können auch die Pfeilfunktionssyntax verwenden:

const diffArray = (arr1, arr2) => arr1.concat(arr2)
    .filter(val => !(arr1.includes(val) && arr2.includes(val)));

diffArray([1, 2, 3, 7], [3, 2, 1, 4, 5]);    // return [7, 4, 5]
Iurii Golskyi
quelle
7
Array.prototype.difference = function(e) {
    return this.filter(function(i) {return e.indexOf(i) < 0;});
};

eg:- 

[1,2,3,4,5,6,7].difference( [3,4,5] );  
 => [1, 2, 6 , 7]
Riyas TK
quelle
Sie sollten ein natives Objekt niemals auf diese Weise erweitern. Wenn der Standard differencein einer zukünftigen Version als Funktion eingeführt wird und diese Funktion eine andere Funktionssignatur als Ihre hat, wird Ihr Code oder fremde Bibliotheken, die diese Funktion verwenden, beschädigt.
t.niese
7

Sehr einfache Lösung mit der Filterfunktion von JavaScript:

var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];

function diffArray(arr1, arr2) {
  var newArr = [];
  var myArr = arr1.concat(arr2);
  
    newArr = myArr.filter(function(item){
      return arr2.indexOf(item) < 0 || arr1.indexOf(item) < 0;
    });
   alert(newArr);
}

diffArray(a1, a2);

Yash Thakkar
quelle
6

Wie wäre es damit:

Array.prototype.contains = function(needle){
  for (var i=0; i<this.length; i++)
    if (this[i] == needle) return true;

  return false;
} 

Array.prototype.diff = function(compare) {
    return this.filter(function(elem) {return !compare.contains(elem);})
}

var a = new Array(1,4,7, 9);
var b = new Array(4, 8, 7);
alert(a.diff(b));

Auf diese Weise können Sie also array1.diff(array2)den Unterschied ermitteln (schreckliche Zeitkomplexität für den Algorithmus - O (array1.length x array2.length), glaube ich).

Katze
quelle
Die Verwendung der Filteroption ist eine gute Idee. Sie müssen jedoch keine Includes-Methode für Array erstellen. Ich habe Ihre Idee in einen Einzeiler umgewandelt ... Danke für die Inspiration!
Joshaven Potter
Sie müssen die Funktion includes () nicht definieren. JS include () macht dasselbe.
Da Man
4

Mit http://phrogz.net/JS/ArraySetMath.js können Sie:

var array1 = ["test1", "test2","test3", "test4"];
var array2 = ["test1", "test2","test3","test4", "test5", "test6"];

var array3 = array2.subtract( array1 );
// ["test5", "test6"]

var array4 = array1.exclusion( array2 );
// ["test5", "test6"]
Phrogz
quelle
4
function diffArray(arr1, arr2) {
  var newArr = arr1.concat(arr2);
  return newArr.filter(function(i){
    return newArr.indexOf(i) == newArr.lastIndexOf(i);
  });
}

Das funktioniert bei mir

Stan D.
quelle
3
  • Reine JavaScript-Lösung (keine Bibliotheken)
  • Kompatibel mit älteren Browsern (wird nicht verwendet filter)
  • O (n ^ 2)
  • Optionaler fnRückrufparameter, mit dem Sie angeben können, wie Array-Elemente verglichen werden sollen

function diff(a, b, fn){
    var max = Math.max(a.length, b.length);
        d = [];
    fn = typeof fn === 'function' ? fn : false
    for(var i=0; i < max; i++){
        var ac = i < a.length ? a[i] : undefined
            bc = i < b.length ? b[i] : undefined;
        for(var k=0; k < max; k++){
            ac = ac === undefined || (k < b.length && (fn ? fn(ac, b[k]) : ac == b[k])) ? undefined : ac;
            bc = bc === undefined || (k < a.length && (fn ? fn(bc, a[k]) : bc == a[k])) ? undefined : bc;
            if(ac == undefined && bc == undefined) break;
        }
        ac !== undefined && d.push(ac);
        bc !== undefined && d.push(bc);
    }
    return d;
}

alert(
    "Test 1: " + 
    diff(
        [1, 2, 3, 4],
        [1, 4, 5, 6, 7]
      ).join(', ') +
    "\nTest 2: " +
    diff(
        [{id:'a',toString:function(){return this.id}},{id:'b',toString:function(){return this.id}},{id:'c',toString:function(){return this.id}},{id:'d',toString:function(){return this.id}}],
        [{id:'a',toString:function(){return this.id}},{id:'e',toString:function(){return this.id}},{id:'f',toString:function(){return this.id}},{id:'d',toString:function(){return this.id}}],
        function(a, b){ return a.id == b.id; }
    ).join(', ')
);

Trevor
quelle
Sie können Längenwerte zwischenspeichern, um die Geschwindigkeit zu erhöhen. Ich wollte empfehlen, auf Array-Elemente zuzugreifen, ohne die Länge zu überprüfen, aber anscheinend führt diese einfache Überprüfung zu einer fast 100-fachen Beschleunigung.
Slotos
Kein Grund, lengthWerte zwischenzuspeichern. Es ist bereits einfaches Eigentum. jsperf.com/array-length-caching
vp_arth
3

Dies funktioniert: Führen Sie die beiden Arrays zusammen, suchen Sie nach den Duplikaten und verschieben Sie das, was nicht dupliziert wurde, in ein neues Array, das den Unterschied ausmacht.

function diff(arr1, arr2) {
  var newArr = [];
  var arr = arr1.concat(arr2);
  
  for (var i in arr){
    var f = arr[i];
    var t = 0;
    for (j=0; j<arr.length; j++){
      if(arr[j] === f){
        t++; 
        }
    }
    if (t === 1){
      newArr.push(f);
        }
  } 
  return newArr;
}

Giorgio Giuliani
quelle
3

// es6 Ansatz

function diff(a, b) {
  var u = a.slice(); //dup the array
  b.map(e => {
    if (u.indexOf(e) > -1) delete u[u.indexOf(e)]
    else u.push(e)   //add non existing item to temp array
  })
  return u.filter((x) => {return (x != null)}) //flatten result
}
Kopremesis
quelle
3

Symmetrische und lineare Komplexität . Benötigt ES6.

function arrDiff(arr1, arr2) {
    var arrays = [arr1, arr2].sort((a, b) => a.length - b.length);
    var smallSet = new Set(arrays[0]);

    return arrays[1].filter(x => !smallSet.has(x));
}
Dodgie
quelle
3

Noch eine Antwort, aber anscheinend hat niemand jsperf erwähnt, wo sie verschiedene Algorithmen und technologische Unterstützung vergleichen: https://jsperf.com/array-difference-javascript scheint die Verwendung von Filtern die besten Ergebnisse zu erzielen . Vielen Dank

Cancerbero
quelle
2

Ich denke nur ... für eine Herausforderung ;-) würde dies funktionieren ... (für grundlegende Arrays von Strings, Zahlen usw.) keine verschachtelten Arrays

function diffArrays(arr1, arr2, returnUnion){
  var ret = [];
  var test = {};
  var bigArray, smallArray, key;
  if(arr1.length >= arr2.length){
    bigArray = arr1;
    smallArray = arr2;
  } else {
    bigArray = arr2;
    smallArray = arr1;
  }
  for(var i=0;i<bigArray.length;i++){
    key = bigArray[i];
    test[key] = true;
  }
  if(!returnUnion){
    //diffing
    for(var i=0;i<smallArray.length;i++){
      key = smallArray[i];
      if(!test[key]){
        test[key] = null;
      }
    }
  } else {
    //union
    for(var i=0;i<smallArray.length;i++){
      key = smallArray[i];
      if(!test[key]){
        test[key] = true;
      }
    }
  }
  for(var i in test){
    ret.push(i);
  }
  return ret;
}

array1 = "test1", "test2","test3", "test4", "test7"
array2 = "test1", "test2","test3","test4", "test5", "test6"
diffArray = diffArrays(array1, array2);
//returns ["test5","test6","test7"]

diffArray = diffArrays(array1, array2, true);
//returns ["test1", "test2","test3","test4", "test5", "test6","test7"]

Beachten Sie, dass die Sortierung wahrscheinlich nicht wie oben angegeben sein wird. Rufen Sie jedoch bei Bedarf .sort () im Array auf, um sie zu sortieren.

scunliffe
quelle
2

Ich wollte eine ähnliche Funktion, die ein altes Array und ein neues Array aufnimmt und mir ein Array von hinzugefügten Elementen und ein Array von entfernten Elementen gibt, und ich wollte, dass es effizient ist (also keine .contains!).

Sie können mit meiner vorgeschlagenen Lösung hier spielen: http://jsbin.com/osewu3/12 .

Kann jemand irgendwelche Probleme / Verbesserungen an diesem Algorithmus sehen? Vielen Dank!

Codeauflistung:

function diff(o, n) {
  // deal with empty lists
  if (o == undefined) o = [];
  if (n == undefined) n = [];

  // sort both arrays (or this won't work)
  o.sort(); n.sort();

  // don't compare if either list is empty
  if (o.length == 0 || n.length == 0) return {added: n, removed: o};

  // declare temporary variables
  var op = 0; var np = 0;
  var a = []; var r = [];

  // compare arrays and add to add or remove lists
  while (op < o.length && np < n.length) {
      if (o[op] < n[np]) {
          // push to diff?
          r.push(o[op]);
          op++;
      }
      else if (o[op] > n[np]) {
          // push to diff?
          a.push(n[np]);
          np++;
      }
      else {
          op++;np++;
      }
  }

  // add remaining items
  if( np < n.length )
    a = a.concat(n.slice(np, n.length));
  if( op < o.length )
    r = r.concat(o.slice(op, o.length));

  return {added: a, removed: r}; 
}
Ian Grainger
quelle
2

Ich suchte nach einer einfachen Antwort, bei der keine unterschiedlichen Bibliotheken verwendet wurden, und fand eine eigene, die meiner Meinung nach hier nicht erwähnt wurde. Ich weiß nicht, wie effizient es ist oder so, aber es funktioniert;

    function find_diff(arr1, arr2) {
      diff = [];
      joined = arr1.concat(arr2);
      for( i = 0; i <= joined.length; i++ ) {
        current = joined[i];
        if( joined.indexOf(current) == joined.lastIndexOf(current) ) {
          diff.push(current);
        }
      }
      return diff;
    }

Für meinen Code müssen auch Duplikate herausgenommen werden, aber ich denke, das wird nicht immer bevorzugt.

Ich denke, der Hauptnachteil ist, dass möglicherweise viele Optionen verglichen werden, die bereits abgelehnt wurden.

Samuel
quelle
2

Littlebit Fix für die beste Antwort

function arr_diff(a1, a2)
{
  var a=[], diff=[];
  for(var i=0;i<a1.length;i++)
    a[a1[i]]=a1[i];
  for(var i=0;i<a2.length;i++)
    if(a[a2[i]]) delete a[a2[i]];
    else a[a2[i]]=a2[i];
  for(var k in a)
   diff.push(a[k]);
  return diff;
}

Dies berücksichtigt den aktuellen Elementtyp. b / c Wenn wir a [a1 [i]] machen, konvertiert es einen Wert von seinem ursprünglichen Wert in einen String, sodass wir den tatsächlichen Wert verloren haben.

Vedanta-krit das
quelle
Dies schlägt für ein Array von Objekten immer noch fehl. var a = [{a: 1}], b = [{b: 2}] arr_diff (a, b) == [].
EricP