Was ist der schnellste Weg, um zwei Sätze in Java zu vergleichen?

Ich versuche, einen Code zu optimieren, der Elemente der Liste vergleicht.

Z.B.

public void compare(Set<Record> firstSet, Set<Record> secondSet){
    for(Record firstRecord : firstSet){
        for(Record secondRecord : secondSet){
            // comparing logic
        }
    }
}

Bitte beachten Sie, dass die Anzahl der Datensätze in Sätzen hoch ist.

Vielen Dank

Shekhar

firstSet.equals(secondSet)

Es hängt wirklich davon ab, was Sie in der Vergleichslogik tun möchten ... dh was passiert, wenn Sie ein Element in einer Menge finden, nicht in der anderen? Ihre Methode hat einen voidRückgabetyp, daher gehe ich davon aus, dass Sie die erforderliche Arbeit in dieser Methode ausführen werden.

Feinkörnigere Steuerung, wenn Sie sie benötigen:

if (!firstSet.containsAll(secondSet)) {
  // do something if needs be
}
if (!secondSet.containsAll(firstSet)) {
  // do something if needs be
}

Wenn Sie die Elemente benötigen, die sich in einem Satz befinden und nicht im anderen.
BEARBEITEN: set.removeAll(otherSet)Gibt einen Booleschen Wert zurück, keinen Satz. Um removeAll () zu verwenden, müssen Sie das Set kopieren und dann verwenden.

Set one = new HashSet<>(firstSet);
Set two = new HashSet<>(secondSet);
one.removeAll(secondSet);
two.removeAll(firstSet);

Wenn der Inhalt von oneund twobeide leer sind, wissen Sie, dass die beiden Sätze gleich waren. Wenn nicht, dann haben Sie die Elemente, die die Mengen ungleich gemacht haben.

Sie haben erwähnt, dass die Anzahl der Datensätze möglicherweise hoch ist. Wenn es sich bei der zugrunde liegenden Implementierung um eine HashSethandelt, erfolgt das Abrufen jedes Datensatzes O(1)rechtzeitig, sodass Sie nicht viel besser werden können. TreeSetist O(log n).

Wenn Sie einfach nur wissen möchten, ob die Mengen gleich sind, wird die equalsMethode on AbstractSetungefähr wie folgt implementiert:

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        return containsAll(c);
    }

Beachten Sie, wie die häufigsten Fälle optimiert werden, in denen:

• Die beiden Objekte sind gleich
• das andere Objekt ist überhaupt keine Menge, und
• Die Größen der beiden Sets sind unterschiedlich.

Danach containsAll(...)wird zurückgegeben false, sobald ein Element in der anderen Gruppe gefunden wird, das sich nicht ebenfalls in dieser Gruppe befindet. Wenn jedoch alle Elemente in beiden Sätzen vorhanden sind, müssen alle getestet werden.

Die Worst-Case-Leistung tritt daher auf, wenn die beiden Sätze gleich, aber nicht dieselben Objekte sind. Diese Kosten sind in der Regel O(N)oder O(NlogN)abhängig von der Implementierung von this.containsAll(c).

Und Sie erhalten eine nahezu Worst-Case-Leistung, wenn die Sets groß sind und sich nur in einem winzigen Prozentsatz der Elemente unterscheiden.

AKTUALISIEREN

Wenn Sie bereit sind, Zeit in eine benutzerdefinierte Set-Implementierung zu investieren, gibt es einen Ansatz, der den "fast gleichen" Fall verbessern kann.

Die Idee ist, dass Sie einen Hash für den gesamten Satz vorberechnen und zwischenspeichern müssen, damit Sie den aktuellen Hashcode-Wert des Satzes erhalten O(1). Dann können Sie den Hashcode für die beiden Sätze als Beschleunigung vergleichen.

Wie könnten Sie einen solchen Hashcode implementieren? Nun, wenn der eingestellte Hashcode war:

• Null für eine leere Menge und
• das XOR aller Element-Hashcodes für eine nicht leere Menge,

Dann können Sie den zwischengespeicherten Hashcode des Sets jedes Mal, wenn Sie ein Element hinzufügen oder entfernen, kostengünstig aktualisieren. In beiden Fällen XOR Sie einfach den Hashcode des Elements mit dem aktuell eingestellten Hashcode.

Dies setzt natürlich voraus, dass Element-Hashcodes stabil sind, während die Elemente Mitglieder von Mengen sind. Es wird auch davon ausgegangen, dass die Hashcode-Funktion der Elementklassen eine gute Streuung ergibt. Dies liegt daran, dass Sie bei gleichen zwei gesetzten Hashcodes immer noch auf den O(N)Vergleich aller Elemente zurückgreifen müssen .

Sie könnten diese Idee etwas weiter führen ... zumindest theoretisch.

WARNUNG - Dies ist sehr spekulativ. Ein "Gedankenexperiment", wenn Sie möchten.

Angenommen, Ihre Set-Element-Klasse verfügt über eine Methode zum Zurückgeben von Krypto-Prüfsummen für das Element. Implementieren Sie nun die Prüfsummen der Menge, indem Sie die für die Elemente zurückgegebenen Prüfsummen XOR-verknüpfen.

Was kauft uns das?

Wenn wir davon ausgehen, dass nichts hinter uns liegt, beträgt die Wahrscheinlichkeit, dass zwei ungleiche Mengenelemente die gleichen N-Bit-Prüfsummen haben, 2 ^-N . Und die Wahrscheinlichkeit, dass 2 ungleiche Mengen die gleichen N-Bit-Prüfsummen haben, beträgt ebenfalls 2 ^-N . Meine Idee ist also, dass Sie Folgendes implementieren können equals:

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        return checksums.equals(c.checksums);
    }

Unter den oben genannten Annahmen erhalten Sie nur einmal in 2- ^N- Zeit die falsche Antwort . Wenn Sie N groß genug machen (z. B. 512 Bit), wird die Wahrscheinlichkeit einer falschen Antwort vernachlässigbar (z. B. ungefähr ^10-150 ).

Der Nachteil ist, dass die Berechnung der Krypto-Prüfsummen für Elemente sehr teuer ist, insbesondere wenn die Anzahl der Bits zunimmt. Sie brauchen also wirklich einen effektiven Mechanismus zum Speichern der Prüfsummen. Und das könnte problematisch sein.

Und der andere Nachteil ist, dass eine Fehlerwahrscheinlichkeit ungleich Null inakzeptabel sein kann, egal wie gering die Wahrscheinlichkeit ist. (Aber wenn das der Fall ist ... wie gehen Sie mit dem Fall um, in dem ein kosmischer Strahl ein kritisches Bit umdreht? Oder wenn er in zwei Fällen eines redundanten Systems gleichzeitig dasselbe Bit umdreht?)

In Guave gibt es eine Methode, Setsdie hier helfen kann:

public static <E>  boolean equals(Set<? extends E> set1, Set<? extends E> set2){
return Sets.symmetricDifference(set1,set2).isEmpty();
}

Sie haben die folgende Lösung von https://www.mkyong.com/java/java-how-to-compare-two-sets/

public static boolean equals(Set<?> set1, Set<?> set2){

    if(set1 == null || set2 ==null){
        return false;
    }

    if(set1.size() != set2.size()){
        return false;
    }

    return set1.containsAll(set2);
}

Oder wenn Sie eine einzelne return-Anweisung bevorzugen:

public static boolean equals(Set<?> set1, Set<?> set2){

  return set1 != null 
    && set2 != null 
    && set1.size() == set2.size() 
    && set1.containsAll(set2);
}

Es gibt eine O (N) -Lösung für ganz bestimmte Fälle, in denen:

• Die Sets sind beide sortiert
• beide in derselben Reihenfolge sortiert

Der folgende Code setzt voraus, dass beide Sätze auf den vergleichbaren Datensätzen basieren. Eine ähnliche Methode könnte auf einem Komparator basieren.

    public class SortedSetComparitor <Foo extends Comparable<Foo>> 
            implements Comparator<SortedSet<Foo>> {

        @Override
        public int compare( SortedSet<Foo> arg0, SortedSet<Foo> arg1 ) {
            Iterator<Foo> otherRecords = arg1.iterator();
            for (Foo thisRecord : arg0) {
                // Shorter sets sort first.
                if (!otherRecords.hasNext()) return 1;
                int comparison = thisRecord.compareTo(otherRecords.next());
                if (comparison != 0) return comparison;
            }
            // Shorter sets sort first
            if (otherRecords.hasNext()) return -1;
            else return 0;
        }
    }

Wenn Sie eine GuavaBibliothek verwenden, ist Folgendes möglich:

        SetView<Record> added = Sets.difference(secondSet, firstSet);
        SetView<Record> removed = Sets.difference(firstSet, secondSet);

Und dann daraus eine Schlussfolgerung ziehen.

Ich würde das secondSet vor dem Vergleich in eine HashMap einfügen. Auf diese Weise reduzieren Sie die Suchzeit der zweiten Liste auf n (1). So was:

HashMap<Integer,Record> hm = new HashMap<Integer,Record>(secondSet.size());
int i = 0;
for(Record secondRecord : secondSet){
    hm.put(i,secondRecord);
    i++;
}
for(Record firstRecord : firstSet){
    for(int i=0; i<secondSet.size(); i++){
    //use hm for comparison
    }
}

public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;

        Set<String> a = this;
        Set<String> b = o;
        Set<String> thedifference_a_b = new HashSet<String>(a);


        thedifference_a_b.removeAll(b);
        if(thedifference_a_b.isEmpty() == false) return false;

        Set<String> thedifference_b_a = new HashSet<String>(b);
        thedifference_b_a.removeAll(a);

        if(thedifference_b_a.isEmpty() == false) return false;

        return true;
    }

Ich denke, dass eine Methodenreferenz mit der Methode gleich verwendet werden kann. Wir gehen davon aus, dass der Objekttyp zweifelsfrei eine eigene Vergleichsmethode hat. Ein einfaches Beispiel ist hier,

Set<String> set = new HashSet<>();
set.addAll(Arrays.asList("leo","bale","hanks"));

Set<String> set2 = new HashSet<>();
set2.addAll(Arrays.asList("hanks","leo","bale"));

Predicate<Set> pred = set::equals;
boolean result = pred.test(set2);
System.out.println(result);   // true