Wie kann man mit JavaScript prüfen, ob zwei Arrays gleich sind?

Question

var a = [1, 2, 3];
var b = [3, 2, 1];
var c = new Array(1, 2, 3);

alert(a == b + "|" + b == c);

Demo

Wie kann ich diese Arrays auf Gleichheit prüfen und eine Methode erhalten, die Folgendes zurückgibt true wenn sie gleich sind?

Bietet jQuery eine Methode dafür?

Answer 1

Das sollten Sie tun. Bitte verwenden Sie nicht stringify noch < > .

function arraysEqual(a, b) {
  if (a === b) return true;
  if (a == null || b == null) return false;
  if (a.length !== b.length) return false;

  // If you don't care about the order of the elements inside
  // the array, you should sort both arrays here.
  // Please note that calling sort on an array will modify that array.
  // you might want to clone your array first.

  for (var i = 0; i < a.length; ++i) {
    if (a[i] !== b[i]) return false;
  }
  return true;
}

Answer 2

[2021 Changelog: Bugfix für Option4: keine Gesamtbestellung auf js-Objekte (auch ohne NaN!=NaN y '5'==5 ( '5'===5 , '2'<3 , etc.)), kann also nicht verwenden .sort(cmpFunc) auf Map.keys() (Sie können jedoch auf Object.keys(obj) da auch "numerische" Tasten Zeichenketten sind)].

Option 1

Die einfachste Option, die in fast allen Fällen funktioniert, außer in folgenden Fällen null !== undefined aber beide werden in die JSON-Darstellung konvertiert null und als gleichwertig betrachtet:

function arraysEqual(a1,a2) {
    /* WARNING: arrays must not contain {objects} or behavior may be undefined */
    return JSON.stringify(a1)==JSON.stringify(a2);
}

( Dies funktioniert möglicherweise nicht, wenn Ihr Array Objekte enthält. Ob dies auch bei Objekten funktioniert, hängt davon ab, ob die JSON-Implementierung die Schlüssel sortiert. Zum Beispiel, das JSON von {1:2,3:4} kann, muss aber nicht gleich sein mit {3:4,1:2} Dies hängt von der Implementierung ab, und die Spezifikation gibt keinerlei Garantie. [Update 2017: Tatsächlich garantiert die ES6-Spezifikation nun, dass Objektschlüssel in der Reihenfolge 1) ganzzahliger Eigenschaften, 2) Eigenschaften in der Reihenfolge, in der sie definiert wurden, dann 3) Symboleigenschaften in der Reihenfolge, in der sie definiert wurden, iteriert werden. WENN also die JSON.stringify-Implementierung dem folgt, werden gleiche Objekte (im ===-Sinn, aber NICHT NÖTIGERweise im ==-Sinn) zu gleichen Werten stringifiziert. Weitere Untersuchungen sind erforderlich. Man könnte also einen bösen Klon eines Objekts mit Eigenschaften in umgekehrter Reihenfolge erstellen, aber ich kann mir nicht vorstellen, dass das jemals aus Versehen passiert...] Zumindest in Chrome neigt die JSON.stringify-Funktion dazu, Schlüssel in der Reihenfolge zurückzugeben, in der sie definiert wurden (zumindest habe ich das festgestellt), aber dieses Verhalten kann sich jederzeit ändern und sollte nicht als verlässlich angesehen werden. Wenn Sie keine Objekte in Ihren Listen verwenden möchten, sollte dies problemlos funktionieren. Wenn Sie Objekte in Ihrer Liste haben, die alle eine eindeutige ID haben, können Sie Folgendes tun a1.map(function(x)}{return {id:x.uniqueId}}) . Wenn Sie beliebige Objekte in Ihrer Liste haben, können Sie für Option 2 weiterlesen).

Dies gilt auch für verschachtelte Arrays.

Es ist jedoch etwas ineffizient, da der Overhead für die Erstellung dieser Zeichenketten und das Sammeln von Datenmüll zu groß ist.

---

Option 2

Historische Lösung, Version 1:

// generally useful functions
function type(x) { // does not work in general, but works on JSONable objects we care about... modify as you see fit
    // e.g.  type(/asdf/g) --> "[object RegExp]"
    return Object.prototype.toString.call(x);
}
function zip(arrays) {
    // e.g. zip([[1,2,3],[4,5,6]]) --> [[1,4],[2,5],[3,6]]
    return arrays[0].map(function(_,i){
        return arrays.map(function(array){return array[i]})
    });
}

// helper functions
function allCompareEqual(array) {
    // e.g.  allCompareEqual([2,2,2,2]) --> true
    // does not work with nested arrays or objects
    return array.every(function(x){return x==array[0]});
}

function isArray(x){ return type(x)==type([]) }
function getLength(x){ return x.length }
function allTrue(array){ return array.reduce(function(a,b){return a&&b},true) }
    // e.g. allTrue([true,true,true,true]) --> true
    // or just array.every(function(x){return x});

function allDeepEqual(things) {
    // works with nested arrays
    if( things.every(isArray) )
        return allCompareEqual(things.map(getLength))     // all arrays of same length
               && allTrue(zip(things).map(allDeepEqual)); // elements recursively equal

    //else if( this.every(isObject) )
    //  return {all have exactly same keys, and for 
    //          each key k, allDeepEqual([o1[k],o2[k],...])}
    //  e.g. ... && allTrue(objectZip(objects).map(allDeepEqual)) 

    //else if( ... )
    //  extend some more

    else
        return allCompareEqual(things);
}

// Demo:

allDeepEqual([ [], [], [] ])
true
allDeepEqual([ [1], [1], [1] ])
true
allDeepEqual([ [1,2], [1,2] ])
true
allDeepEqual([ [[1,2],[3]], [[1,2],[3]] ])
true

allDeepEqual([ [1,2,3], [1,2,3,4] ])
false
allDeepEqual([ [[1,2],[3]], [[1,2],[],3] ])
false
allDeepEqual([ [[1,2],[3]], [[1],[2,3]] ])
false
allDeepEqual([ [[1,2],3], [1,[2,3]] ])
false

<!--

More "proper" option, which you can override to deal with special cases (like regular objects and null/undefined and custom objects, if you so desire):

To use this like a regular function, do:

    function allDeepEqual2() {
        return allDeepEqual([].slice.call(arguments));
    }

Demo:

    allDeepEqual2([[1,2],3], [[1,2],3])
    true

  -->

---

Option 3

function arraysEqual(a,b) {
    /*
        Array-aware equality checker:
        Returns whether arguments a and b are == to each other;
        however if they are equal-lengthed arrays, returns whether their 
        elements are pairwise == to each other recursively under this
        definition.
    */
    if (a instanceof Array && b instanceof Array) {
        if (a.length!=b.length)  // assert same length
            return false;
        for(var i=0; i<a.length; i++)  // assert each element equal
            if (!arraysEqual(a[i],b[i]))
                return false;
        return true;
    } else {
        return a==b;  // if not both arrays, should be the same
    }
}

//Examples:

arraysEqual([[1,2],3], [[1,2],3])
true
arraysEqual([1,2,3], [1,2,3,4])
false
arraysEqual([[1,2],[3]], [[1,2],[],3])
false
arraysEqual([[1,2],[3]], [[1],[2,3]])
false
arraysEqual([[1,2],3], undefined)
false
arraysEqual(undefined, undefined)
true
arraysEqual(1, 2)
false
arraysEqual(null, null)
true
arraysEqual(1, 1)
true
arraysEqual([], 1)
false
arraysEqual([], undefined)
false
arraysEqual([], [])
true

/*
If you wanted to apply this to JSON-like data structures with js Objects, you could do so. Fortunately we're guaranteed that all objects keys are unique, so iterate over the objects OwnProperties and sort them by key, then assert that both the sorted key-array is equal and the value-array are equal, and just recurse. We CANNOT extend the sort-then-compare method with Maps as well; even though Map keys are unique, there is no total ordering in ecmascript, so you can't sort them... but you CAN query them individually (see the next section Option 4). (Also if we extend this to Sets, we run into the tree isomorphism problem http://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf - fortunately it's not as hard as general graph isomorphism; there is in fact an O(#vertices) algorithm to solve it, but it can get very complicated to do it efficiently. The pathological case is if you have a set made up of lots of seemingly-indistinguishable objects, but upon further inspection some of those objects may differ as you delve deeper into them. You can also work around this by using hashing to reject almost all cases.)
*/

<!--
**edit**: It's 2016 and my previous overcomplicated answer was bugging me. This recursive, imperative "recursive programming 101" implementation keeps the code really simple, and furthermore fails at the earliest possible point (giving us efficiency). It also doesn't generate superfluous ephemeral datastructures (not that there's anything wrong with functional programming in general, but just keeping it clean here).

If we wanted to apply this to a non-empty arrays of arrays, we could do seriesOfArrays.reduce(arraysEqual).

This is its own function, as opposed to using Object.defineProperties to attach to Array.prototype, since that would fail with a key error if we passed in an undefined value (that is however a fine design decision if you want to do so).

This only answers OPs original question.
-->

---

Option 4: (Fortsetzung der Bearbeitung von 2016)

Dies sollte bei den meisten Objekten funktionieren:

const STRICT_EQUALITY_BROKEN = (a,b)=> a===b;
const STRICT_EQUALITY_NO_NAN = (a,b)=> {
    if (typeof a=='number' && typeof b=='number' && ''+a=='NaN' && ''+b=='NaN')
        // isNaN does not do what you think; see +/-Infinity
        return true;
    else
        return a===b;
};
function deepEquals(a,b, areEqual=STRICT_EQUALITY_NO_NAN, setElementsAreEqual=STRICT_EQUALITY_NO_NAN) {
    /* compares objects hierarchically using the provided 
       notion of equality (defaulting to ===);
       supports Arrays, Objects, Maps, ArrayBuffers */
    if (a instanceof Array && b instanceof Array)
        return arraysEqual(a,b, areEqual);
    if (Object.getPrototypeOf(a)===Object.prototype && Object.getPrototypeOf(b)===Object.prototype)
        return objectsEqual(a,b, areEqual);
    if (a instanceof Map && b instanceof Map)
        return mapsEqual(a,b, areEqual);        
    if (a instanceof Set && b instanceof Set) {
        if (setElementsAreEqual===STRICT_EQUALITY_NO_NAN)
            return setsEqual(a,b);
        else
            throw "Error: set equality by hashing not implemented because cannot guarantee custom notion of equality is transitive without programmer intervention."
    }
    if ((a instanceof ArrayBuffer || ArrayBuffer.isView(a)) && (b instanceof ArrayBuffer || ArrayBuffer.isView(b)))
        return typedArraysEqual(a,b);
    return areEqual(a,b);  // see note[1] -- IMPORTANT
}

function arraysEqual(a,b, areEqual) {
    if (a.length!=b.length)
        return false;
    for(var i=0; i<a.length; i++)
        if (!deepEquals(a[i],b[i], areEqual))
            return false;
    return true;
}
function objectsEqual(a,b, areEqual) {
    var aKeys = Object.getOwnPropertyNames(a);
    var bKeys = Object.getOwnPropertyNames(b);
    if (aKeys.length!=bKeys.length)
        return false;
    aKeys.sort();
    bKeys.sort();
    for(var i=0; i<aKeys.length; i++)
        if (!areEqual(aKeys[i],bKeys[i])) // keys must be strings
            return false;
    return deepEquals(aKeys.map(k=>a[k]), aKeys.map(k=>b[k]), areEqual);
}
function mapsEqual(a,b, areEqual) { // assumes Map's keys use the '===' notion of equality, which is also the assumption of .has and .get methods in the spec; however, Map's values use our notion of the areEqual parameter
    if (a.size!=b.size)
        return false;
    return [...a.keys()].every(k=> 
        b.has(k) && deepEquals(a.get(k), b.get(k), areEqual)
    );
}
function setsEqual(a,b) {
    // see discussion in below rest of StackOverflow answer
    return a.size==b.size && [...a.keys()].every(k=> 
        b.has(k)
    );
}
function typedArraysEqual(a,b) {
    // we use the obvious notion of equality for binary data
    a = new Uint8Array(a);
    b = new Uint8Array(b);
    if (a.length != b.length)
        return false;
    for(var i=0; i<a.length; i++)
        if (a[i]!=b[i])
            return false;
    return true;
}

Demo (not extensively tested):

var nineTen = new Float32Array(2);
nineTen[0]=9; nineTen[1]=10;

> deepEquals(
    [[1,[2,3]], 4, {a:5,'111':6}, new Map([['c',7],['d',8]]), nineTen],
    [[1,[2,3]], 4, {111:6,a:5}, new Map([['d',8],['c',7]]), nineTen]
)
true

> deepEquals(
    [[1,[2,3]], 4, {a:'5','111':6}, new Map([['c',7],['d',8]]), nineTen],
    [[1,[2,3]], 4, {111:6,a:5}, new Map([['d',8],['c',7]]), nineTen],
    (a,b)=>a==b
)
true

Beachten Sie, dass bei Verwendung der == Begriff der Gleichheit, dann wissen, dass falsche Werte und Zwang bedeutet, dass == Gleichheit ist NICHT TRANSITIV. Zum Beispiel ''==0 y 0=='0' sondern ''!='0' . Dies ist für Sets relevant: Ich glaube nicht, dass man den Begriff der Mengengleichheit auf sinnvolle Weise außer Kraft setzen kann. Wenn man den eingebauten Begriff der Mengengleichheit verwendet (d.h., === ), dann sollte das obige funktionieren. Wenn man jedoch einen nicht-transitiven Begriff der Gleichheit verwendet, wie == öffnen Sie ein Wespennest: Selbst wenn man den Benutzer zwingen würde, eine Hash-Funktion für den Bereich zu definieren (hash(a)!=hash(b) impliziert a!=b), bin ich nicht sicher, ob das helfen würde... Sicherlich könnte man die O(N^2)-Performance-Sache machen und Paare von == Elemente einzeln wie eine Bubble-Sortierung, und führen Sie dann einen zweiten O(N^2)-Durchlauf durch, um zu bestätigen, dass Dinge in Äquivalenzklassen tatsächlich == zueinander, und auch != auf alles, was nicht so gepaart, aber Sie müssten immer noch einen Laufzeitfehler auslösen, wenn Sie einige Zwang los haben ... Sie würden auch vielleicht seltsame (aber möglicherweise nicht so seltsam) Randfälle mit https://developer.mozilla.org/en-US/docs/Glossary/Falsy und Truthy-Werte (mit der Ausnahme, dass NaN==NaN... aber nur für Sets!). Bei den meisten Sets mit homogenem Datentyp ist dies normalerweise kein Problem.

Um die Komplexität der rekursiven Gleichheit auf Mengen zusammenzufassen:

• Mengengleichheit ist das Problem der Baumisomorphie http://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf aber ein bisschen einfacher
• Menge A =? Menge B ist gleichbedeutend mit B.has(k) for every k in A verwendet implizit === -Gleichheit ( [1,2,3]!==[1,2,3] ), nicht die rekursive Gleichheit ( deepEquals([1,2,3],[1,2,3]) == true ), also zwei new Set([[1,2,3]]) wäre nicht gleich, weil wir nicht rekursieren
• Der Versuch, rekursive Gleichheit zum Funktionieren zu bringen, ist ziemlich sinnlos, wenn der von Ihnen verwendete rekursive Begriff der Gleichheit nicht 1) reflexiv (a=b impliziert b=a) und 2) symmetrisch (a=a) und 3) transitiv (a=b und b=c impliziert a=c) ist; dies ist die Definition eines Äquivalenzklasse
• der Gleichheitsoperator == erfüllt offensichtlich viele dieser Eigenschaften nicht
• auch die strenge Gleichheit \=== Betreiber in ecmascript gehorcht diesen Eigenschaften nicht, da die strenger Gleichheitsvergleichsalgorithmus von ecmascript hat NaN!=NaN; dies ist der Grund, warum viele native Datentypen wie Set y Map NaNs "gleichsetzen", um sie als gleiche Werte zu betrachten, wenn sie als Schlüssel erscheinen
• Solange wir die rekursive Mengengleichheit erzwingen und sicherstellen, dass sie tatsächlich transitiv, reflexiv und symmetrisch ist, können wir sicherstellen, dass nichts Schreckliches passiert.
  • Dann können wir O(N^2)-Vergleiche durchführen, indem wir alles nach dem Zufallsprinzip rekursiv vergleichen, was unglaublich ineffizient ist. Es gibt keinen magischen Algorithmus, der es uns ermöglicht setKeys.sort((a,b)=> /*some comparison function*/) weil es in ecmascript keine totale Ordnung gibt (''==0 und 0=='0', aber ''!='0'... obwohl ich glaube, dass Sie in der Lage sein könnten, selbst eine zu definieren, was sicherlich ein hochgestecktes Ziel wäre).
  • Wir können jedoch .toString obige oder JSON.stringify alle Elemente, um uns zu unterstützen. Anschließend sortieren wir sie, wodurch wir Äquivalenzklassen (zwei gleiche Dinge haben nicht die gleiche String-JSON-Darstellung) und potenziell falsch-positive Klassen (zwei unterschiedliche Dinge können die gleiche String- oder JSON-Darstellung haben) erhalten.
    • Dies führt jedoch zu eigenen Leistungsproblemen, da die Serialisierung ein und desselben Objekts und dann die Serialisierung von Teilmengen dieses Objekts immer wieder unglaublich ineffizient ist. Stellen Sie sich einen Baum aus verschachtelten Set s; jeder Knoten würde zu O(Tiefe) verschiedenen Serialisierungen gehören!
    • Selbst wenn das kein Problem wäre, wäre die Leistung im schlimmsten Fall immer noch O(N!), wenn alle Serialisierungs-"Hinweise" die gleichen wären

So erklärt die obige Implementierung, dass Mengen gleich sind, wenn die Elemente einfach === sind (nicht rekursiv ===). Dies bedeutet, dass sie false zurückgeben wird für new Set([1,2,3]) y new Set([1,2,3]) . Mit ein wenig Aufwand können Sie diesen Teil des Codes umschreiben, wenn Sie wissen, was Sie tun.

(Nebenbei bemerkt: Karten sind es6-Wörterbücher. Ich kann nicht sagen, ob sie O(1) oder O(log(N)) Suchleistung haben, aber auf jeden Fall sind sie "geordnet" in dem Sinne, dass sie die Reihenfolge verfolgen, in der Schlüssel-Wert-Paare in sie eingefügt wurden. Die Frage, ob zwei Maps gleichwertig sein sollten, wenn Elemente in unterschiedlicher Reihenfolge eingefügt wurden, ist jedoch nicht eindeutig zu beantworten. Im Folgenden gebe ich ein Beispiel für die Implementierung eines deepEquals, das zwei Maps auch dann als gleich betrachtet, wenn Elemente in unterschiedlicher Reihenfolge in sie eingefügt wurden).

(Anmerkung [1]: WICHTIG: BEGRIFF DER GLEICHHEIT: Es kann sein, dass Sie die angegebene Zeile mit einem eigenen Begriff der Gleichheit überschreiben wollen, den Sie dann auch in den anderen Funktionen ändern müssen, wo er auftaucht. Wollen Sie zum Beispiel NaN==NaN oder nicht? Standardmäßig ist dies nicht der Fall. Es gibt noch mehr seltsame Dinge wie 0=='0'. Betrachten Sie zwei Objekte als gleich, wenn und nur wenn sie im Speicher das gleiche Objekt sind? Siehe https://stackoverflow.com/a/5447170/711085 . Sie sollten den von Ihnen verwendeten Begriff der Gleichheit dokumentieren.) Beachten Sie auch, dass andere Antworten, die naiv den Begriff .toString y .sort Manchmal kann es vorkommen, dass man betet, dass 0!=-0 werden aber für fast alle Datentypen und JSON-Serialisierungen als gleichwertig und kanonisierbar zu 0 angesehen; ob -0==0 sollte auch in Ihrer Vorstellung von Gleichheit dokumentiert sein, ebenso wie die meisten anderen Dinge in dieser Tabelle wie NaN usw.

Sie sollten in der Lage sein, das oben Gesagte auf WeakMaps, WeakSets zu erweitern. Ich bin nicht sicher, ob es sinnvoll ist, auf DataViews zu erweitern. Sollte auch in der Lage sein, RegExps wahrscheinlich zu erweitern, etc.

Wenn Sie es erweitern, werden Sie feststellen, dass Sie viele unnötige Vergleiche anstellen. Dies ist der Punkt, an dem die type Funktion, die ich vorhin definiert habe (Lösung #2), kann sich als nützlich erweisen; dann kann man sofort loslegen. Ob das den Overhead der (möglicherweise? nicht sicher, wie es unter der Haube funktioniert) Zeichenfolge, die den Typ darstellt, wert ist, liegt an Ihnen. Sie können dann einfach den Dispatcher umschreiben, d.h. die Funktion deepEquals zu sein:

var dispatchTypeEquals = {
    number: function(a,b) {...a==b...},
    array: function(a,b) {...deepEquals(x,y)...},
    ...
}
function deepEquals(a,b) {
    var typeA = extractType(a);
    var typeB = extractType(a);
    return typeA==typeB && dispatchTypeEquals[typeA](a,b);
}

Answer 3

Für primitive Werte wie Zahlen und Zeichenketten ist dies eine einfache Lösung:

a = [1,2,3]

b = [3,2,1]

a.sort().toString() == b.sort().toString() 

Die Aufforderung an sort() wird sicherstellen, dass die Reihenfolge der Elemente keine Rolle spielt. Die toString() Aufruf wird eine Zeichenkette mit durch Komma getrennten Werten erstellt, so dass beide Zeichenketten auf Gleichheit geprüft werden können.

Answer 4

JQuery verfügt nicht über eine Methode zum Vergleichen von Arrays. Allerdings ist die Unterstreichungsbibliothek (oder die vergleichbare Lodash-Bibliothek) verfügt über eine solche Methode: isEqual und kann auch eine Vielzahl anderer Fälle (wie Objektliterale) behandeln. Um bei dem angegebenen Beispiel zu bleiben:

var a=[1,2,3];
var b=[3,2,1];
var c=new Array(1,2,3);

alert(_.isEqual(a, b) + "|" + _.isEqual(b, c));

Im Übrigen: Underscore hat noch viele andere Methoden, die jQuery fehlen, ist also eine gute Ergänzung zu jQuery.

EDIT: Wie in den Kommentaren hervorgehoben wurde, funktioniert die obige Funktion nur, wenn beide Arrays ihre Elemente in der gleichen Reihenfolge haben, d. h.:

_.isEqual([1,2,3], [1,2,3]); // true
_.isEqual([1,2,3], [3,2,1]); // false

Glücklicherweise hat Javascript eine eingebaute Methode, um genau dieses Problem zu lösen, sort :

_.isEqual([1,2,3].sort(), [3,2,1].sort()); // true

Answer 5

Mit JavaScript Version 1.6 ist es so einfach wie dieses:

Array.prototype.equals = function( array ) {
  return this.length == array.length && 
         this.every( function(this_i,i) { return this_i == array[i] } )  
  }

Zum Beispiel, [].equals([]) gibt true , während [1,2,3].equals( [1,3,2] ) ergibt false .