Cara sederhana untuk mengetahui apakah dua daftar berbeda mengandung elemen yang sama persis?

Apa cara paling sederhana untuk menemukan jika dua Daftar berisi elemen yang persis sama, di perpustakaan Java standar?

Seharusnya tidak masalah jika kedua Daftar adalah instance yang sama atau tidak, dan seharusnya tidak masalah jika parameter tipe Daftar berbeda.

misalnya

List list1
List<String> list2; 
// ... construct etc

list1.add("A");
list2.add("A"); 
// the function, given these two lists, should return true

Mungkin ada sesuatu yang menatapku di wajah, aku tahu :-)

EDIT: Untuk memperjelas, saya mencari EXACT elemen yang sama dan jumlah elemen, secara berurutan.

Jika Anda peduli tentang pesanan, maka gunakan metode sama dengan:

list1.equals(list2)

Dari javadoc:

Membandingkan objek yang ditentukan dengan daftar ini untuk persamaan. Mengembalikan nilai true jika dan hanya jika objek yang ditentukan juga daftar, kedua daftar memiliki ukuran yang sama, dan semua pasangan elemen yang sesuai dalam dua daftar adalah sama. (Dua elemen e1 dan e2 sama jika (e1 == null? E2 == null: e1.equals (e2)).) Dengan kata lain, dua daftar didefinisikan sama jika mengandung elemen yang sama dalam urutan yang sama . Definisi ini memastikan bahwa metode yang sama berfungsi dengan baik di seluruh implementasi berbeda dari antarmuka Daftar.

Jika Anda ingin memeriksa independen dari pesanan, Anda bisa menyalin semua elemen ke Set dan menggunakan sama dengan Set yang dihasilkan:

public static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

Keterbatasan pendekatan ini adalah tidak hanya mengabaikan ketertiban, tetapi juga frekuensi elemen duplikat. Misalnya, jika list1["A", "B", "A"] dan list2[[A], "B", "B"] Setpendekatan akan menganggap mereka sama.

Jika Anda harus tidak sensitif untuk memesan tetapi peka terhadap frekuensi duplikat Anda dapat:

• urutkan kedua daftar (atau salinan) sebelum membandingkannya, seperti yang dilakukan dalam jawaban ini untuk pertanyaan lain
• atau salin semua elemen ke Multiset

Saya memposting banyak hal dalam komentar saya pikir itu menjamin jawabannya sendiri.

Seperti yang dikatakan semua orang di sini, menggunakan equals () tergantung pada urutannya. Jika Anda tidak peduli tentang pesanan, Anda memiliki 3 opsi.

Pilihan 1

Gunakan containsAll(). Opsi ini tidak ideal, menurut saya, karena ia menawarkan kinerja kasus terburuk, O (n ^ 2).

pilihan 2

Ada dua variasi untuk ini:

2a) Jika Anda tidak peduli tentang menjaga urutan daftar Anda ... gunakan Collections.sort()di kedua daftar. Kemudian gunakan equals(). Ini adalah O (nlogn), karena Anda melakukan dua macam, dan kemudian perbandingan O (n).

2b) Jika Anda perlu mempertahankan urutan daftar, Anda dapat menyalin kedua daftar terlebih dahulu. MAKA Anda dapat menggunakan solusi 2a pada kedua daftar yang disalin. Namun ini mungkin tidak menarik jika menyalin sangat mahal.

Ini mengarah ke:

Opsi 3

Jika persyaratan Anda sama dengan bagian 2b , tetapi menyalin terlalu mahal. Anda dapat menggunakan TreeSet untuk melakukan penyortiran untuk Anda. Buang setiap daftar ke TreeSet sendiri. Ini akan disortir dalam set, dan daftar asli akan tetap utuh. Kemudian lakukan equals()perbandingan pada keduanya TreeSet. The TreeSetss dapat dibangun dalam O (nlogn) waktu, dan equals()adalah O (n).

Ambil pilihanmu :-).

EDIT: Saya hampir lupa peringatan yang sama yangditunjukkan Laurence Gonsalves . Implementasi TreeSet akan menghilangkan duplikat. Jika Anda peduli tentang duplikat, Anda akan membutuhkan semacam multiset yang diurutkan.

Jika Anda menggunakan (atau senang menggunakan) Koleksi Apache Commons, Anda dapat menggunakan CollectionUtils.isEqualCollection yang "mengembalikan true jika Koleksi yang diberikan mengandung elemen yang persis sama dengan kardinalitas yang persis sama."

Sangat terlambat ke pesta tetapi ingin menambahkan cek aman nol ini:

Objects.equals(list1, list2)

Saya tahu ini adalah utas lama, tetapi tidak ada jawaban lain yang sepenuhnya memecahkan kasus penggunaan saya (saya kira Guava Multiset mungkin melakukan hal yang sama, tetapi tidak ada contoh di sini). Maafkan pemformatan saya. Saya masih baru untuk memposting di stack stack. Selain itu beri tahu saya jika ada kesalahan

Katakanlah Anda memiliki List<T>a dan List<T>b dan Anda ingin memeriksa apakah mereka sama dengan kondisi berikut:

1) O (n) waktu berjalan yang diharapkan
2) Kesetaraan didefinisikan sebagai: Untuk semua elemen dalam a atau b, berapa kali elemen terjadi dalam a sama dengan berapa kali elemen tersebut terjadi dalam b. Elemen kesetaraan didefinisikan sebagai T.equals ()

private boolean listsAreEquivelent(List<? extends Object> a, List<? extends Object> b) {
    if(a==null) {
        if(b==null) {
            //Here 2 null lists are equivelent. You may want to change this.
            return true;
        } else {
            return false;
        }
    }
    if(b==null) {
        return false;
    }
    Map<Object, Integer> tempMap = new HashMap<>();
    for(Object element : a) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            tempMap.put(element, 1);
        } else {
            tempMap.put(element, currentCount+1);
        }
    }
    for(Object element : b) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            return false;
        } else {
            tempMap.put(element, currentCount-1);
        }
    }
    for(Integer count : tempMap.values()) {
        if(count != 0) {
            return false;
        }
    }
    return true;
}

Waktu berjalan adalah O (n) karena kita melakukan penyisipan O (2 * n) ke dalam hashmap dan O (3 * n) memilih hashmap. Saya belum sepenuhnya menguji kode ini, jadi waspadalah :)

//Returns true:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","A"));
listsAreEquivelent(null,null);
//Returns false:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),null);

Coba versi ini yang tidak membutuhkan urutan yang sama tetapi mendukung memiliki kelipatan dari nilai yang sama. Mereka cocok hanya jika masing-masing memiliki jumlah nilai yang sama.

public boolean arraysMatch(List<String> elements1, List<String> elements2) {
    // Optional quick test since size must match
    if (elements1.size() != elements2.size()) {
        return false;
    }
    List<String> work = newArrayList(elements2);
    for (String element : elements1) {
        if (!work.remove(element)) {
            return false;
        }
    }
    return work.isEmpty();
}

Metode equals pada Daftar akan melakukan ini, Daftar diperintahkan, sehingga untuk menjadi sama dua Daftar harus memiliki elemen yang sama dalam urutan yang sama.

return list1.equals(list2);

Solusi untuk kasus ketika dua daftar memiliki elemen yang sama, tetapi urutannya berbeda:

public boolean isDifferentLists(List<Integer> listOne, List<Integer> listTwo) {
    if(isNullLists(listOne, listTwo)) {
        return false;
    }

    if (hasDifferentSize(listOne, listTwo)) {
        return true;
    }

    List<Integer> listOneCopy = Lists.newArrayList(listOne);
    List<Integer> listTwoCopy = Lists.newArrayList(listTwo);
    listOneCopy.removeAll(listTwoCopy);

    return CollectionUtils.isNotEmpty(listOneCopy);
}

private boolean isNullLists(List<Integer> listOne, List<Integer> listTwo) {
    return listOne == null && listTwo == null;
}

private boolean hasDifferentSize(List<Integer> listOne, List<Integer> listTwo) {
    return (listOne == null && listTwo != null) || (listOne != null && listTwo == null) || (listOne.size() != listTwo.size());
}

Jawaban Tom sangat bagus. Saya setuju sepenuhnya dengan jawabannya!

Aspek yang menarik dari pertanyaan ini adalah, apakah Anda memerlukan Listjenis itu sendiri dan urutan bawaannya.

Jika tidak, Anda dapat menurunkan Iterableatau Collectionyang memberi Anda beberapa fleksibilitas dalam melewati struktur data yang diurutkan pada waktu penyisipan, daripada pada saat Anda ingin memeriksa.

Jika pesanan tidak pernah penting (dan Anda tidak memiliki duplikat elemen) mempertimbangkan menggunakan Set.

Jika pesanan penting tetapi ditentukan oleh waktu penyisipan (dan Anda tidak memiliki duplikat) pertimbangkan LinkedHashSetyang seperti TreeSet tetapi dipesan berdasarkan waktu penyisipan (duplikat tidak dihitung). Ini juga memberi Anda O(1)akses yang diamortisasi O(log n).

Kode sampel:

public static '<'T'>' boolean isListDifferent(List'<'T'>' previousList,
        List'<'T'>' newList) {

    int sizePrevoisList = -1;
    int sizeNewList = -1;

    if (previousList != null && !previousList.isEmpty()) {
        sizePrevoisList = previousList.size();
    }
    if (newList != null && !newList.isEmpty()) {
        sizeNewList = newList.size();
    }

    if ((sizePrevoisList == -1) && (sizeNewList == -1)) {
        return false;
    }

    if (sizeNewList != sizePrevoisList) {
        return true;
    }

    List n_prevois = new ArrayList(previousList);
    List n_new = new ArrayList(newList);

    try {
        Collections.sort(n_prevois);
        Collections.sort(n_new);
    } catch (ClassCastException exp) {
        return true;
    }

    for (int i = 0; i < sizeNewList; i++) {
        Object obj_prevois = n_prevois.get(i);
        Object obj_new = n_new.get(i);
        if (obj_new.equals(obj_prevois)) {
            // Object are same
        } else {
            return true;
        }
    }

    return false;
}

Selain jawaban Laurence, jika Anda juga ingin menjadikannya nol-aman:

private static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    if (list1 == null)
        return list2==null;
    if (list2 == null)
        return list1 == null;
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

list1.equals(list2);

Jika daftar Anda mengandung MyClass Kelas kustom, kelas ini harus menimpa equalsfungsi.

 class MyClass
  {
  int field=0;
  @0verride
  public boolean equals(Object other)
        {
        if(this==other) return true;
        if(other==null || !(other instanceof MyClass)) return false;
        return this.field== MyClass.class.cast(other).field;
        }
  }

Catatan: jika Anda ingin menguji sama dengan pada java.util.Set daripada a java.util.List, maka objek Anda harus menimpa hashCode fungsi.

List.equals ()

http://java.sun.com/j2se/1.5/docs/api/java/util/List.html#equals(java.lang.Object)

Anda dapat menggunakan perpustakaan Apache.apache.commons.collections: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html

public static boolean isEqualList(java.util.Collection list1,
                              java.util.Collection list2)

Periksa kedua daftar bukan nol. Jika ukurannya berbeda, maka daftar ini tidak sama. Buat peta yang terdiri dari elemen daftar sebagai kunci dan pengulangannya sebagai nilai dan bandingkan peta.

Asumsi, jika kedua daftar adalah nol, saya menganggapnya sama.

private boolean compareLists(List<?> l1, List<?> l2) {
    if (l1 == null && l2 == null) {
        return true;
    } else if (l1 == null || l2 == null) {
        return false;
    }

    if (l1.size() != l2.size()) {
        return false;
    }

    Map<?, Integer> m1 = toMap(l1);
    Map<?, Integer> m2 = toMap(l2);

    return m1.equals(m2);
}

private Map<Object, Integer> toMap(List<?> list) {
    //Effective size, not to resize in the future.
    int mapSize = (int) (list.size() / 0.75 + 1);
    Map<Object, Integer> map = new HashMap<>(mapSize);

    for (Object o : list) {
        Integer count = map.get(o);
        if (count == null) {
            map.put(o, 1);
        } else {
            map.put(o, ++count);
        }
    }

    System.out.println(map);
    return map;
}

Harap dicatat, metode yang sama harus didefinisikan dengan benar untuk objek-objek ini. https://stackoverflow.com/a/24814634/4587961

Itu tergantung pada kelas Daftar konkret apa yang Anda gunakan. Kelas abstrak AbstractCollection memiliki metode yang disebut berisiAll (Koleksi) yang mengambil koleksi lain (Daftar adalah koleksi) dan:

Mengembalikan nilai true jika koleksi ini mengandung semua elemen dalam koleksi yang ditentukan.

Jadi jika ArrayList dilewatkan, Anda dapat memanggil metode ini untuk melihat apakah mereka persis sama.

       List foo = new ArrayList();
    List bar = new ArrayList();
    String str = "foobar";

    foo.add(str);
    bar.add(str);

    foo.containsAll(bar);

Alasan untuk containAll () adalah karena iterasi melalui daftar pertama mencari kecocokan di daftar kedua. Jadi jika mereka salah urutan sama dengan () tidak akan mengambilnya.

EDIT: Saya hanya ingin memberikan komentar di sini tentang waktu berjalan diamortisasi melakukan berbagai opsi yang ditawarkan. Apakah waktu berjalan itu penting? Tentu. Apakah itu satu-satunya hal yang harus Anda pertimbangkan? Tidak.

Biaya menyalin SETIAP elemen tunggal dari daftar Anda ke daftar lain membutuhkan waktu, dan itu juga memakan banyak memori (secara efektif menggandakan memori yang Anda gunakan).

Jadi jika memori di JVM Anda tidak menjadi masalah (yang seharusnya pada umumnya) maka Anda masih perlu mempertimbangkan waktu yang diperlukan untuk menyalin setiap elemen dari dua daftar menjadi dua TreeSets. Ingat itu menyortir setiap elemen saat memasuki mereka.

Saran terakhir saya? Anda perlu mempertimbangkan kumpulan data Anda dan berapa banyak elemen yang Anda miliki dalam kumpulan data Anda, dan juga seberapa besar setiap objek dalam kumpulan data Anda sebelum Anda dapat membuat keputusan yang baik di sini. Main-main dengan mereka, buat satu jalan sekali dan lihat mana yang berjalan lebih cepat. Ini latihan yang bagus.