Apa cara tercepat untuk membandingkan dua set di Java?

Saya mencoba untuk mengoptimalkan sepotong kode yang membandingkan elemen daftar.

Misalnya.

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

Harap diperhatikan bahwa jumlah record dalam set akan tinggi.

Terima kasih

Shekhar

firstSet.equals(secondSet)

Ini benar-benar tergantung pada apa yang ingin Anda lakukan dalam logika perbandingan ... yaitu apa yang terjadi jika Anda menemukan elemen dalam satu himpunan bukan di himpunan lainnya? Metode Anda memiliki voidtipe pengembalian jadi saya berasumsi Anda akan melakukan pekerjaan yang diperlukan dalam metode ini.

Kontrol yang lebih halus jika Anda membutuhkannya:

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

Jika Anda perlu mendapatkan elemen yang ada di satu set dan bukan yang lain.
EDIT: set.removeAll(otherSet)mengembalikan boolean, bukan satu set. Untuk menggunakan removeAll (), Anda harus menyalin set lalu menggunakannya.

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

Jika isi onedan twokeduanya kosong, maka Anda tahu bahwa kedua himpunan itu sama. Jika tidak, maka Anda memiliki elemen yang membuat himpunan tidak sama.

Anda menyebutkan bahwa jumlah record mungkin tinggi. Jika implementasi yang mendasarinya adalah, HashSetmaka pengambilan setiap record dilakukan O(1)tepat waktu, jadi Anda tidak bisa mendapatkan yang lebih baik dari itu. TreeSetadalah O(log n).

Jika Anda hanya ingin mengetahui apakah setnya sama, equalsmetode on AbstractSetdiimplementasikan secara kasar seperti di bawah ini:

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

Perhatikan bagaimana ini mengoptimalkan kasus umum di mana:

• kedua objek itu sama
• objek lainnya bukanlah satu set sama sekali, dan
• ukuran kedua set berbeda.

Setelah itu, containsAll(...)akan kembali falsesegera setelah menemukan elemen di himpunan lain yang juga tidak ada di himpunan ini. Tetapi jika semua elemen ada di kedua set, itu perlu menguji semuanya.

Oleh karena itu, kinerja kasus terburuk terjadi ketika dua set objek yang sama tetapi tidak sama. Biaya tersebut biasanya O(N)atau O(NlogN)tergantung pada penerapannya this.containsAll(c).

Dan Anda akan mendapatkan kinerja kasus yang mendekati terburuk jika setnya besar dan hanya berbeda dalam persentase kecil elemen.

MEMPERBARUI

Jika Anda ingin menginvestasikan waktu dalam implementasi kumpulan kustom, ada pendekatan yang dapat meningkatkan kasus "hampir sama".

Idenya adalah Anda perlu menghitung sebelumnya dan menyimpan hash ke cache untuk seluruh set sehingga Anda bisa mendapatkan nilai kode hash set saat ini O(1). Kemudian Anda dapat membandingkan kode hash untuk dua set sebagai percepatan.

Bagaimana Anda bisa menerapkan kode hash seperti itu? Nah jika set hashcode-nya adalah:

• nol untuk satu set kosong, dan
• XOR dari semua kode hash elemen untuk himpunan yang tidak kosong,

maka Anda dapat dengan murah memperbarui kode hash cache set setiap kali Anda menambahkan atau menghapus elemen. Dalam kedua kasus, Anda cukup melakukan XOR kode hash elemen dengan kode hash set saat ini.

Tentu saja, ini mengasumsikan bahwa kode hash elemen stabil sementara elemen adalah anggota set. Ini juga mengasumsikan bahwa fungsi kode hash kelas elemen memberikan penyebaran yang baik. Itu karena ketika dua set kode hash sama, Anda masih harus kembali ke O(N)perbandingan semua elemen.

Anda dapat mengambil ide ini lebih jauh ... setidaknya dalam teori.

PERINGATAN - Ini sangat spekulatif. Sebuah "eksperimen pikiran" jika Anda suka.

Misalkan kelas elemen set Anda memiliki metode untuk mengembalikan checksum crypto untuk elemen tersebut. Sekarang implementasikan checksum set dengan XOR checksum yang dikembalikan untuk elemen.

Apa yang dibeli ini untuk kita?

Nah, jika kita berasumsi bahwa tidak ada kesalahan yang terjadi, probabilitas bahwa dua elemen himpunan yang tidak sama memiliki checksum N-bit yang sama adalah 2 ^-N . Dan probabilitas 2 himpunan tidak sama memiliki checksum N-bit yang sama juga 2 ^-N . Jadi ide saya adalah Anda dapat menerapkan equalssebagai:

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

Berdasarkan asumsi di atas, ini hanya akan memberi Anda jawaban yang salah sekali dalam waktu 2 ^-N . Jika Anda membuat N cukup besar (misalnya 512 bit), kemungkinan jawaban yang salah dapat diabaikan (misalnya kira-kira 10 ^-150 ).

Kelemahannya adalah bahwa menghitung checksum kripto untuk elemen sangat mahal, terutama karena jumlah bit meningkat. Jadi, Anda benar-benar membutuhkan mekanisme yang efektif untuk membuat memo checksum. Dan itu bisa menjadi masalah.

Dan sisi negatif lainnya adalah bahwa probabilitas kesalahan yang bukan nol mungkin tidak dapat diterima tidak peduli seberapa kecil probabilitasnya. (Tetapi jika itu masalahnya ... bagaimana Anda menangani kasus di mana sinar kosmik membalik sedikit kritis? Atau jika secara bersamaan membalik bit yang sama dalam dua contoh sistem redundan?)

Ada metode dalam Jambu Setsyang dapat membantu di sini:

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

Anda memiliki solusi berikut dari 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);
}

Atau jika Anda lebih suka menggunakan pernyataan pengembalian tunggal:

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

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

Ada solusi O (N) untuk kasus yang sangat spesifik di mana:

• set keduanya diurutkan
• keduanya diurutkan dalam urutan yang sama

Kode berikut mengasumsikan bahwa kedua set didasarkan pada catatan yang sebanding. Metode serupa dapat didasarkan pada Comparator.

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

Jika Anda menggunakan Guavaperpustakaan, itu mungkin untuk dilakukan:

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

Dan kemudian buat kesimpulan berdasarkan ini.

Saya akan meletakkan secondSet di HashMap sebelum perbandingan. Dengan cara ini Anda akan mengurangi waktu pencarian daftar kedua menjadi n (1). Seperti ini:

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

Saya pikir referensi metode dengan metode yang sama dapat digunakan. Kami berasumsi bahwa tipe objek tanpa bayangan keraguan memiliki metode perbandingannya sendiri. Contoh yang jelas dan sederhana ada di sini,

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