Jaki jest najszybszy sposób porównania dwóch zestawów w Javie?

Próbuję zoptymalizować fragment kodu, który porównuje elementy listy.

Na przykład.

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

Proszę wziąć pod uwagę, że ilość rekordów w zestawach będzie duża.

Dzięki

Shekhar

firstSet.equals(secondSet)

To naprawdę zależy od tego, co chcesz zrobić w logice porównania… czyli co się stanie, jeśli znajdziesz element w jednym zestawie, a nie w drugim? Twoja metoda ma voidtyp zwrotu, więc zakładam, że wykonasz niezbędną pracę w tej metodzie.

Bardziej precyzyjna kontrola, jeśli jej potrzebujesz:

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

Jeśli potrzebujesz zdobyć elementy, które są w jednym zestawie, a nie w drugim.
EDYCJA: set.removeAll(otherSet)zwraca wartość logiczną, a nie zestaw. Aby użyć removeAll (), musisz skopiować zestaw, a następnie go użyć.

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

Jeśli zawartość onei twooba są puste, to wiesz, że oba zestawy były równe. Jeśli nie, to masz elementy, które sprawiły, że zestawy były nierówne.

Wspomniałeś, że liczba rekordów może być wysoka. Jeśli podstawową implementacją jest HashSeta, pobieranie każdego rekordu odbywa się na O(1)czas, więc naprawdę nie można uzyskać nic lepszego. TreeSetjest O(log n).

Jeśli chcesz po prostu wiedzieć, czy zestawy są równe, equalsmetoda on AbstractSetjest zaimplementowana mniej więcej tak, jak poniżej:

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

Zwróć uwagę, jak optymalizuje typowe przypadki, w których:

• te dwa obiekty są takie same
• drugi obiekt nie jest w ogóle zbiorem i
• rozmiary obu zestawów są różne.

Po tym containsAll(...)zwróci, falsegdy tylko znajdzie element w innym zestawie, którego również nie ma w tym zestawie. Ale jeśli wszystkie elementy są obecne w obu zestawach, będzie musiał przetestować je wszystkie.

Dlatego wydajność w najgorszym przypadku występuje, gdy dwa zestawy są równe, ale nie są tymi samymi obiektami. Koszt ten jest zazwyczaj O(N)lub w O(NlogN)zależności od implementacji this.containsAll(c).

I uzyskuje się wydajność bliską najgorszemu przypadkowi, jeśli zestawy są duże i różnią się tylko niewielkim procentem elementów.

AKTUALIZACJA

Jeśli chcesz zainwestować czas w implementację zestawu niestandardowego, istnieje podejście, które może poprawić „prawie ten sam” przypadek.

Chodzi o to, że musisz wstępnie obliczyć i buforować hash dla całego zestawu, abyś mógł pobrać bieżącą wartość hashcode zestawu O(1). Następnie możesz porównać hashcode dla dwóch zestawów jako przyspieszenie.

Jak możesz zaimplementować taki hashcode? Cóż, jeśli ustawiony hashcode to:

• zero dla pustego zestawu i
• XOR wszystkich hashcodes elementu dla niepustego zestawu,

wtedy możesz tanio zaktualizować buforowany hashcode zestawu za każdym razem, gdy dodasz lub usuniesz element. W obu przypadkach po prostu XORujesz kod mieszający elementu z bieżącym ustawionym hashcode.

Oczywiście zakłada się, że hashcodes elementów są stabilne, podczas gdy elementy są członkami zestawów. Zakłada również, że funkcja hashcode klas elementów daje dobry rozkład. Dzieje się tak, ponieważ gdy dwa ustawione hashcodes są takie same, nadal musisz wrócić do O(N)porównania wszystkich elementów.

Możesz pójść dalej z tym pomysłem ... przynajmniej w teorii.

OSTRZEŻENIE - jest to wysoce spekulacyjne. „Eksperyment myślowy”, jeśli chcesz.

Załóżmy, że twoja klasa elementu set ma metodę zwracania kryptograficznych sum kontrolnych dla elementu. Teraz zaimplementuj sumy kontrolne zestawu, XORując sumy kontrolne zwrócone dla elementów.

Co nam to daje?

Cóż, jeśli założymy, że nic się nie dzieje podstępnie, prawdopodobieństwo, że dowolne dwa nierówne elementy zbioru mają takie same N-bitowe sumy kontrolne, wynosi 2 ^-N . Prawdopodobieństwo, że 2 nierówne zbiory mają te same N-bitowe sumy kontrolne, również wynosi 2 ^-N . Więc mój pomysł jest taki, że możesz wdrożyć equalsjako:

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

Zgodnie z powyższymi założeniami, daje to złą odpowiedź tylko raz na 2- ^N raz. Jeśli zrobisz N wystarczająco duże (np. 512 bitów), prawdopodobieństwo złej odpowiedzi stanie się pomijalne (np. Około 10 ^-150 ).

Wadą jest to, że obliczanie kryptograficznych sum kontrolnych elementów jest bardzo kosztowne, zwłaszcza gdy rośnie liczba bitów. Więc naprawdę potrzebujesz skutecznego mechanizmu zapamiętywania sum kontrolnych. A to może być problematyczne.

Drugą wadą jest to, że niezerowe prawdopodobieństwo błędu może być niedopuszczalne bez względu na to, jak małe jest to prawdopodobieństwo. (Ale jeśli tak jest ... jak radzić sobie z przypadkiem, w którym promień kosmiczny odwraca krytyczny bit? Lub jeśli jednocześnie odwraca ten sam bit w dwóch przypadkach systemu nadmiarowego?)

W guawie istnieje metoda, Setsktóra może tutaj pomóc:

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

Masz następujące rozwiązanie z 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);
}

Lub jeśli wolisz użyć pojedynczej instrukcji powrotu:

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

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

Istnieje rozwiązanie O (N) dla bardzo specyficznych przypadków, w których:

• zestawy są sortowane
• oba posortowane w tej samej kolejności

Poniższy kod zakłada, że ​​oba zestawy są oparte na porównywalnych rekordach. Podobna metoda mogłaby opierać się na komparatorze.

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

Jeśli korzystasz z Guavabiblioteki, możesz:

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

A następnie wyciągnij wnioski na tej podstawie.

Przed porównaniem umieściłbym secondSet w HashMap. W ten sposób zredukujesz czas przeszukiwania drugiej listy do n (1). Lubię to:

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

Myślę, że można użyć odwołania do metody z metodą równości. Zakładamy, że typ obiektu bez cienia wątpliwości ma własną metodę porównania. Oto jasny i prosty przykład,

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