Wie kann man die Gleichheit von Arrays mit modernem Java vergleichen?

70

Ich habe zwei Listen von Arrays.

Wie kann ich die Gleichheit dieser mit Java 8 und seinen Funktionen vergleichen , ohne externe Bibliotheken zu verwenden? Ich suche nach einer "besseren" (übergeordneten, kürzeren, effizienteren) Lösung als Brute-Force-Code wie diesem (ungetesteter Code, kann Tippfehler usw. enthalten, nicht der Punkt der Frage):

boolean compare(List<String[]> list1, List<String[]> list2) 
{
    // tests for nulls etc omitted
    if(list1.size() != list2.size()) {
       return false;
    }
    for(i=0; i<list1.size(); ++i) {
        if(!Arrays.equals(list1.get(i), list2.get(i))) {
            return false;
        }
    }
    return true;
}

Oder wenn es keinen schöneren Weg gibt, ist das auch eine gültige Antwort.

Bonus: Wenn Java 9 eine noch bessere Möglichkeit bietet, was auch immer Java 8 bieten kann, können Sie es auch erwähnen.

Bearbeiten: Nachdem ich mir die Kommentare angesehen und gesehen habe, wie diese Frage mäßig heiß geworden ist, denke ich, dass das " Bessere " das erste Überprüfen der Länge aller Arrays vor dem Überprüfen des Array-Inhalts beinhalten sollte , da dies das Potenzial hat, Ungleichheit viel schneller zu finden, wenn sie innerlich ist Arrays sind lang.

Hyde
quelle
2
Wenn Sie nur List <List <String >> anstelle von List <String []> verwenden würden, könnten Sie list1.equals (list2) ausführen. Der tatsächliche Vergleich (unter dem Deckmantel) wird jedoch immer noch rohe Gewalt sein.
Marshallursson
3
Der Code funktioniert, ist schnell und einfach zu lesen / verstehen und zu warten ... warum zum Teufel ändern Sie ihn? Warum ist kürzer besser?
Falco
1
Beachten Sie, dass kürzere Lösungen möglicherweise auch langsamer sind.
Pharap
3
Was ist besser"? Schneller? Einfacher zu warten? Verbraucht weniger Speicher?
Martin Schröder
@ MartinSchröder Ich habe die Frage dazu etwas geklärt.
Hyde

Antworten:

31

1) Lösung basierend auf Java 8-Streams:

List<List<String>> first = list1.stream().map(Arrays::asList).collect(toList());
List<List<String>> second = list2.stream().map(Arrays::asList).collect(toList());
return first.equals(second);

2) Viel einfachere Lösung (funktioniert in Java 5+):

return Arrays.deepEquals(list1.toArray(), list2.toArray());

3) In Bezug auf Ihre neue Anforderung (um zuerst die Länge der enthaltenen String-Arrays zu überprüfen) können Sie eine generische Hilfsmethode schreiben, die die Gleichheitsprüfung für transformierte Listen durchführt:

<T, U> boolean equal(List<T> list1, List<T> list2, Function<T, U> mapper) {
    List<U> first = list1.stream().map(mapper).collect(toList());
    List<U> second = list2.stream().map(mapper).collect(toList());
    return first.equals(second);
}

Dann könnte die Lösung sein:

return equal(list1, list2, s -> s.length)
    && equal(list1, list2, Arrays::asList);
Dragan Bozanovic
quelle
5
# 2 ist einfacher, aber auch eine Kopie jeder Liste
Holger
2
@Holger Richtig, eigentlich besteht die erste Lösung darin, auch die Listen zu kopieren. Die enthaltenen String-Arrays werden jedoch in keiner der beiden Lösungen kopiert, sondern nur Verweise auf sie werden kopiert.
Dragan Bozanovic
Ich habe die Frage ein wenig bearbeitet, wenn Sie das überprüfen möchten ... Ich denke, deepEquals macht das nicht, oder?
Hyde
2
@hyde deepEqualsprüft auf Länge. Aus dem Javadoc: Zwei Array-Referenzen werden als zutiefst gleich angesehen, wenn beide null sind oder wenn sie sich auf Arrays beziehen, die die gleiche Anzahl von Elementen enthalten und alle entsprechenden Elementpaare in den beiden Arrays zutiefst gleich sind.
SpaceTrucker
@SpaceTrucker Ja, aber ich meine, es überprüft wahrscheinlich nicht zuerst die Länge aller Arrays usw. und erst danach beginnt der Inhalt zu überprüfen. Es wird davon ausgegangen, dass der Inhalt des ersten angetroffenen Arrays überprüft wird, bevor die Länge des zweiten Arrays überprüft wird.
Hyde
50

Die forSchleife kann zumindest gestreamt werden, was zu Folgendem führt:

return (list1.size()==list2.size() &&
        IntStream.range(0, list1.size())
                 .allMatch(i -> Arrays.equals(list1.get(i), list2.get(i)));
khelwood
quelle
12
Ganz schöne Lösung. Erwähnenswert ist, dass es für Nicht- RandomAccessListen ineffizient ist .
Jaroslaw Pawlak
10
@cat, im allgemeinen Fall gibt es keine Möglichkeit, zwei Sammlungen von n Elementen schneller als O (n) zu vergleichen.
ymbirtt
17
@ymbirtt: Eigentlich gibt es einen Weg, aber es würde erfordern, dass Sie Ihre eigene Sammlung schreiben oder eine vorhandene erweitern und sie ändern. Behalten Sie einfach einen Hash-Code in der Sammlung. Passen Sie den Hash jedes Mal, wenn ein Element hinzugefügt wird, entsprechend an (z. B. mit einer Primzahl multiplizieren und den Hash-Code des Elements hinzufügen). Dann müssen Sie nur noch die Hashes von 2 Sammlungen vergleichen, also O (1). Da die Möglichkeit einer Kollision besteht, können Sie optional nur dann einen vollständigen Vergleich durchführen, wenn die Hashes übereinstimmen. Es wäre also O (n), aber der Rest der Zeit viel schneller. Das Löschen oder Bearbeiten von Elementen in der Sammlung kann auch kompliziert sein.
Darrel Hoffman
1
zipist für solche Probleme viel natürlicher und eine bekannte Redewendung in vielen verschiedenen Sprachen - wie in hahns Antwort dargestellt . In einigen Fällen ganz zu schweigen von der Leistungsüberlegenheit (wie von @JaroslawPawlak im oberen Kommentar erwähnt).
BartoszKP
8
@DarrelHoffman Für einen genauen Vergleich, Sie müssen jedes Element vergleichen , wenn die Hashes übereinstimmen.
user253751
31

Mit der Funktion zip(die von Lambda B93 stammt) von https://stackoverflow.com/a/23529010/755183 könnte der Code wie folgt aussehen:

boolean match = a.size() == b.size() && 
                zip(a.stream(), b.stream(), Arrays::deepEquals).
                allMatch(equal -> equal)

aktualisieren

Um zuerst die Größe der Arrays und dann den Inhalt zu überprüfen, könnte dies eine zu berücksichtigende Lösung sein

final boolean match = a.size() == b.size() 
                   && zip(a.stream(), b.stream(), (as, bs) -> as.length == bs.length).
                      allMatch(equal -> equal)
                   && zip(a.stream(), b.stream(), Arrays::deepEquals).
                      allMatch(equal -> equal);
hahn
quelle
15

Sie können einen Stream verwenden, wenn es sich bei den Listen um Listen mit wahlfreiem Zugriff handelt (so dass ein Aufruf von getschnell ist - im Allgemeinen eine konstante Zeit). Dies führt zu:

//checks for null and size before
boolean same = IntStream.range(0, list1.size()).allMatch(i -> Arrays.equals(list1.get(i), list2.get(i)));

Sie können jedoch einige Implementierungen als Parameter angeben, die dies nicht sind (z. B. LinkedLists). In diesem Fall ist es am besten, den Iterator explizit zu verwenden. Etwas wie:

boolean compare(List<String[]> list1, List<String[]> list2) {

    //checks for null and size

    Iterator<String[]> iteList1 = list1.iterator();
    Iterator<String[]> iteList2 = list2.iterator();

    while(iteList1.hasNext()) {
        if(!Arrays.equals(iteList1.next(), iteList2.next())) {
            return false;
        }
    }
    return true;
}
Alexis C.
quelle
Die erste Lösung gibt true zurück, wenn die zweite Liste mehr Elemente enthält. Die zweite Lösung ist für große Listen unterschiedlicher Größe ineffizient, da sie erst nach dem Durchlaufen von false falsch zurückgibt.
Jaroslaw Pawlak
@JaroslawPawlak Die erste Lösung geht davon aus, dass die Überprüfung auf Nullreferenzen und die Größe bereits durchgeführt wurde (nur das Ersetzen der for-Schleife). Ich habe für die zweite Lösung bearbeitet.
Alexis C.
1
Fair genug. In diesem Fall können wir die endgültige Rückgabeerklärung in der zweiten Lösung für return true;:)
Jaroslaw Pawlak
@ JaroslawPawlak Ja, und wir können sogar die && iteList2.hasNext()in der Bedingung weglassen
Alexis C.
6

Sie können über eine Liste streamen und mit jedem Element des anderen vergleichen, indem Sie einen Iterator verwenden:

Iterator<String[]> it = list1.iterator();
boolean match = list1.size() == list2.size() &&
                list2.stream().allMatch(a -> Arrays.equals(a, it.next()));

Die Verwendung eines Iterators anstelle der get(index)Methode in der ersten Liste ist besser, da es keine Rolle spielt, ob die Liste vorhanden ist RandomAccessoder nicht.

Hinweis: Dies funktioniert nur mit einem sequentiellen Stream. Die Verwendung eines parallelen Streams führt zu falschen Ergebnissen.


BEARBEITEN: Gemäß der Frage der letzten Bearbeitung, die angibt, dass es besser ist, die Länge jedes Array-Paares im Voraus zu überprüfen , denke ich, dass dies mit einer geringfügigen Änderung meines vorherigen Codes erreicht werden könnte:

Iterator<String[]> itLength = list1.iterator();
Iterator<String[]> itContents = list1.iterator();

boolean match = 
        list1.size() == list2.size()
    && 
        list2.stream()
            .allMatch(a -> {
                String[] s = itLength.next();
                return s == null ? a == null :
                       a == null ? s == null :
                       a.length == s.length;
            })
    && 
        list2.stream()
            .allMatch(a -> Arrays.equals(a, itContents.next()));

Hier verwende ich zwei Iteratoren und streame list2zweimal, aber ich sehe keine andere Möglichkeit, alle Längen zu überprüfen, bevor der Inhalt des ersten Array-Paares überprüft wird. Die Prüfung auf Längen ist nullsicher, während die Prüfung auf Inhalt an die Arrays.equals(array1, array2)Methode delegiert wird.

fps
quelle
Ich würde warnen, dass dies zu unerwarteten Ergebnissen führen wird, wenn jemand anruft .parallelStream().
Alexis C.
Ja, ich weiß. Aber ich stelle mir schon vor, dass jemand dies kopiert und einfügt und sagt "Hey, ich werde versuchen, dies mit einem parallelen Stream zu beschleunigen".
Alexis C.
1
Sie können es weiter vereinfachen, um : list2.stream() .allMatch(a -> Arrays.equals(a, it.next())).
Dragan Bozanovic