Wat is de snelste manier om twee sets in Java te vergelijken?

Ik probeer een stuk code te optimaliseren dat elementen van een lijst vergelijkt.

Bijvoorbeeld

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

Houd er rekening mee dat het aantal records in sets hoog zal zijn.

Bedankt

Shechar

Antwoord 1, autoriteit 100%

firstSet.equals(secondSet)

Het hangt er echt van af wat je wilt doen in de vergelijkingslogica… dwz wat gebeurt er als je een element in de ene set niet in de andere vindt? Uw methode heeft een voidretourtype, dus ik neem aan dat u het nodige werk met deze methode zult doen.

Meer fijnmazige controle als je het nodig hebt:

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

Als je de elementen nodig hebt die in de ene set zitten en niet in de andere.

EDIT: set.removeAll(otherSet)geeft een boolean terug, geen set. Om removeAll() te gebruiken, moet je de set kopiëren en vervolgens gebruiken.

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

Als de inhoud van oneen twobeide leeg zijn, dan weet je dat de twee sets gelijk waren. Zo niet, dan heb je de elementen die de sets ongelijk maakten.

U zei dat het aantal records mogelijk hoog is. Als de onderliggende implementatie een HashSetis, dan wordt het ophalen van elk record gedaan in O(1)tijd, dus veel beter dan dat kun je niet worden. TreeSetis O(log n).

Antwoord 2, autoriteit 37%

Als u gewoon wilt weten of de sets gelijk zijn, wordt de methode equalsop AbstractSetongeveer als volgt geïmplementeerd:

   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);
    }

Merk op hoe het de veelvoorkomende gevallen optimaliseert waarin:

• de twee objecten zijn hetzelfde
• het andere object is helemaal geen set, en
• de maten van de twee sets zijn verschillend.

Daarna zal containsAll(...)falseretourneren zodra het een element in de andere set vindt dat niet ook in deze set zit. Maar als alle elementen in beide sets aanwezig zijn, moet het ze allemaal testen.

De slechtste prestatie treedt daarom op wanneer de twee sets gelijk zijn, maar niet dezelfde objecten. Die kosten zijn doorgaans O(N)of O(NlogN), afhankelijk van de implementatie van this.containsAll(c).

En je krijgt bijna de slechtste prestaties als de sets groot zijn en slechts in een klein percentage van de elementen verschillen.

UPDATE

Als u bereid bent tijd te investeren in een implementatie van een aangepaste set, is er een aanpak die het “bijna hetzelfde” geval kan verbeteren.

Het idee is dat je een hash voor de hele set vooraf moet berekenen en in de cache moet opslaan, zodat je de huidige hashcode-waarde van de set in O(1)kunt krijgen. Dan kun je de hashcode voor de twee sets vergelijken als een versnelling.

Hoe zou je zo’n hashcode kunnen implementeren? Als de ingestelde hashcode was:

• nul voor een lege set, en
• de XOR van alle element-hashcodes voor een niet-lege set,

dan zou je de gecachte hashcode van de set goedkoop kunnen bijwerken elke keer dat je een element toevoegt of verwijdert. In beide gevallen XOR de hashcode van het element met de huidige ingestelde hashcode.

Natuurlijk veronderstelt dit dat element-hashcodes stabiel zijn terwijl de elementen lid zijn van sets. Het gaat er ook van uit dat de hashcode-functie van de elementklassen een goede spreiding geeft. Dat komt omdat wanneer de twee ingestelde hashcodes hetzelfde zijn, je nog steeds terug moet vallen op de O(N)vergelijking van alle elementen.

Je zou dit idee wat verder kunnen uitdiepen… in ieder geval in theorie.

WAARSCHUWING– Dit is zeer speculatief. Een “gedachten-experiment” zo je wilt.

Stel dat uw set-elementklasse een methode heeft om crypto-checksums voor het element te retourneren. Implementeer nu de checksums van de set door de checksums voor de elementen te XORen.

Wat levert dit ons op?

Nou, als we aannemen dat er niets achterbaks aan de hand is, is de kans dat twee ongelijke verzamelingselementen dezelfde N-bit checksums hebben 2^-N. En de kans dat 2 ongelijke sets dezelfde N-bit checksums hebben is ook 2^-N. Dus mijn idee is dat je equalskunt implementeren als:

   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);
    }

Onder de bovenstaande veronderstellingen geeft dit u slechts één keer in de 2^-Ntijd het verkeerde antwoord. Als je N groot genoeg maakt (bijvoorbeeld 512 bits), wordt de kans op een fout antwoord verwaarloosbaar (bijvoorbeeld ongeveer 10^-150).

Het nadeel is dat het berekenen van de crypto-checksums voor elementen erg duur is, vooral naarmate het aantal bits toeneemt. Je hebt dus echt een effectief mechanisme nodig om de checksums te onthouden. En dat kan problematisch zijn.

En het andere nadeel is dat een foutkans van meer dan nul mogelijkonaanvaardbaar is, hoe klein de kans ook is. (Maar als dat het geval is … hoe ga je om met het geval waarin een kosmische straal een kritisch bit omdraait? Of als het tegelijkertijd hetzelfde bit omkeert in twee gevallen van een redundant systeem?)

Antwoord 3, autoriteit 10%

Er is een methode in Guava Setsdie hier kan helpen:

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

Antwoord 4, autoriteit 3%

Er is een O(N)-oplossing voor zeer specifieke gevallen waarin:

• de sets zijn beide gesorteerd
• beiden in dezelfde volgorde gesorteerd

De volgende code gaat ervan uit dat beide sets zijn gebaseerd op vergelijkbare records. Een vergelijkbare methode zou gebaseerd kunnen zijn op een vergelijker.

   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;
        }
    }