Prosty sposób na sprawdzenie, czy dwie różne listy zawierają dokładnie te same elementy?

Jaki jest najprostszy sposób na sprawdzenie, czy dwie listy zawierają dokładnie takie same elementy w standardowych bibliotekach Java?

Nie powinno mieć znaczenia, czy dwie listy są tym samym wystąpieniem, czy nie, i nie powinno mieć znaczenia, czy parametr typu list jest inny.

na przykład

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

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

Prawdopodobnie coś wpatruje się we mnie w twarz, którą znam :-)

EDYCJA: Aby wyjaśnić, szukałem DOKŁADNIE tych samych elementów i ich liczby, w kolejności.

Jeśli zależy Ci na porządku, skorzystaj z metody równości:

list1.equals(list2)

Z javadoc:

Porównuje określony obiekt z tą listą pod kątem równości. Zwraca wartość true tylko wtedy, gdy określony obiekt jest również listą, obie listy mają ten sam rozmiar, a wszystkie odpowiadające pary elementów na dwóch listach są równe. (Dwa elementy e1 i e2 są równe, jeśli (e1 == null? E2 == null: e1.equals (e2)).) Innymi słowy, dwie listy są zdefiniowane jako równe, jeśli zawierają te same elementy w tej samej kolejności . Ta definicja zapewnia, że ​​metoda równości działa poprawnie w różnych implementacjach interfejsu List.

Jeśli chcesz sprawdzić niezależnie od kolejności, możesz skopiować wszystkie elementy do zestawów i użyć równości w wynikowych zestawach:

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

Ograniczeniem tego podejścia jest to, że nie tylko ignoruje porządek, ale także częstotliwość zduplikowanych elementów. Na przykład, jeśli list1było [„A”, „B”, „A”] i list2było [„A”, „B”, „B”], Setpodejście uznałoby je za równe.

Jeśli chcesz być niewrażliwy na zamówienie, ale wrażliwy na częstotliwość duplikatów, możesz:

• posortuj obie listy (lub kopie) przed ich porównaniem, tak jak w tej odpowiedzi na inne pytanie
• lub skopiuj wszystkie elementy do Multiset

W komentarzach zamieściłem wiele rzeczy, które, jak sądzę, wymagają własnej odpowiedzi.

Jak wszyscy tu mówią, użycie equals () zależy od kolejności. Jeśli nie zależy ci na porządku, masz 3 opcje.

opcja 1

Zastosowanie containsAll(). Moim zdaniem ta opcja nie jest idealna, ponieważ oferuje najgorszą wydajność, O (n ^ 2).

Opcja 2

Istnieją dwie wersje:

2a) Jeśli nie zależy ci na utrzymaniu porządku na twoich listach ... użyj Collections.sort()na obu listach. Następnie użyj equals(). To jest O (nlogn), ponieważ robisz dwa rodzaje, a następnie porównujesz O (n).

2b) Jeśli chcesz zachować porządek list, możesz najpierw skopiować obie listy. NASTĘPNIE możesz użyć rozwiązania 2a na obu skopiowanych listach. Jednak może to być nieatrakcyjne, jeśli kopiowanie jest bardzo drogie.

To prowadzi do:

Opcja 3

Jeśli twoje wymagania są takie same jak w części 2b , ale kopiowanie jest zbyt drogie. Możesz użyć TreeSet, aby wykonać sortowanie. Zrzuć każdą listę do własnego TreeSet. Zostanie on posortowany w zestawie, a oryginalne listy pozostaną nienaruszone. Następnie wykonaj equals()porównanie obu TreeSets. Do TreeSetsS może być zbudowany w O (nlogn) czas, a equals()O (n).

Wybierz :-).

EDYCJA: Prawie zapomniałem tego samego zastrzeżenia, na którewskazuje Laurence Gonsalves . Implementacja TreeSet wyeliminuje duplikaty. Jeśli zależy Ci na duplikatach, będziesz potrzebować sortowanego multiset.

Jeśli używasz (lub z przyjemnością używasz) kolekcji Apache Commons, możesz użyć CollectionUtils.isEqualCollection, która „zwraca wartość prawdy, jeśli podane kolekcje zawierają dokładnie te same elementy o dokładnie takich samych licznościach”.

Bardzo późno na imprezę, ale chciałem dodać tę zerową kontrolę bezpieczeństwa:

Objects.equals(list1, list2)

Wiem, że to stary wątek, ale żadna z pozostałych odpowiedzi nie rozwiązała w pełni mojego przypadku użycia (wydaje mi się, że Guava Multiset może zrobić to samo, ale nie ma tutaj żadnego przykładu). Przepraszam za moje formatowanie. Nadal jestem nowy w publikowaniu na stosie wymiany. Dodatkowo daj mi znać, jeśli są jakieś błędy

Powiedzmy, że masz List<T>a i List<T>b i chcesz sprawdzić, czy są one równe z następujących warunków:

1) O (n) oczekiwany czas działania
2) Równość jest zdefiniowana jako: Dla wszystkich elementów w a lub b liczba wystąpień elementu w a jest równa liczbie wystąpień elementu w b. Równość elementów jest zdefiniowana jako 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;
}

Czas działania to O (n), ponieważ wykonujemy wstawiania O (2 * n) do mapy skrótów i zaznaczanie mapy skrótów O (3 * n) wybiera. Nie w pełni przetestowałem ten kod, więc uważaj :)

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

Wypróbuj tę wersję, która nie wymaga, aby kolejność była taka sama, ale obsługuje wielokrotność tej samej wartości. Pasują tylko wtedy, gdy każdy ma taką samą ilość dowolnej wartości.

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

Metoda równości na liście to zrobi, listy są uporządkowane, więc aby były równe, dwie listy muszą mieć te same elementy w tej samej kolejności.

return list1.equals(list2);

Rozwiązanie na wypadek, gdy dwie listy mają te same elementy, ale w innej kolejności:

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

Odpowiedź Toma jest doskonała. W pełni zgadzam się z jego odpowiedziami!

Ciekawym aspektem tego pytania jest to, czy potrzebujesz samego Listtypu i jego właściwego uporządkowania.

Jeśli nie, możesz zdegradować Iterablelub Collectiondać ci pewną elastyczność w przekazywaniu struktur danych sortowanych według czasu wstawiania, a nie w czasie, gdy chcesz to sprawdzić.

Jeśli kolejność nigdy nie ma znaczenia (a nie masz zduplikowanych elementów), rozważ użycie Set.

Jeśli kolejność ma znaczenie, ale jest zdefiniowana przez czas wstawiania (i nie masz duplikatów), rozważ taki, LinkedHashSetktóry jest podobny do TreeSet, ale jest uporządkowany według czasu wstawienia (duplikaty nie są liczone). Daje to również O(1)dostęp amortyzowany O(log n).

Przykładowy kod:

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

Oprócz odpowiedzi Laurence'a, jeśli chcesz również uczynić ją bezpieczną:

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

Jeśli twoja lista zawiera niestandardową klasę MyClass, ta klasa musi zastąpić equalsfunkcję.

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

Uwaga: jeśli chcesz testować na java.util.Set zamiast na a java.util.List, twój obiekt musi zastąpić hashCode funkcję.

List.equals ()

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

Możesz użyć biblioteki org.apache.commons.collections Apache: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html

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

Sprawdź, czy obie listy nie są zerami. Jeśli ich rozmiary są różne, listy te nie są równe. Twórz mapy składające się z elementów list jako kluczy i ich powtórzeń jako wartości i porównuj mapy.

Założenia, jeśli obie listy są zerowe, uważam je za równe.

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

Uwaga: metoda równa powinna być poprawnie zdefiniowana dla tych obiektów. https://stackoverflow.com/a/24814634/4587961

To zależy od tego, jakiej konkretnej klasy List używasz. Klasa abstrakcyjna AbstractCollection ma metodę o nazwie zawieraAll (kolekcja), która pobiera inną kolekcję (lista to kolekcja) i:

Zwraca wartość true, jeśli ta kolekcja zawiera wszystkie elementy w określonej kolekcji.

Więc jeśli przekazywana jest ArrayList, możesz wywołać tę metodę, aby zobaczyć, czy są one dokładnie takie same.

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

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

    foo.containsAll(bar);

Powodem funkcji zawieraAll () jest to, że iteruje pierwszą listę szukając dopasowania na drugiej liście. Więc jeśli nie działają, równy () nie odbierze.

EDYCJA: Chcę tylko skomentować tutaj o zamortyzowanym czasie wykonywania różnych oferowanych opcji. Czy czas pracy jest ważny? Pewnie. Czy to jedyna rzecz, którą powinieneś rozważyć? Nie.

Koszt skopiowania KAŻDEGO pojedynczego elementu z twoich list na inne listy zajmuje dużo czasu, a także zajmuje sporą część pamięci (skutecznie podwajając pamięć, której używasz).

Więc jeśli pamięć w JVM nie stanowi problemu (co powinno być w zasadzie), to nadal musisz wziąć pod uwagę czas potrzebny do skopiowania każdego elementu z dwóch list do dwóch TreeSets. Pamiętaj, że sortuje każdy element, gdy wchodzi do nich.

Moja ostatnia rada? Musisz rozważyć swój zestaw danych i liczbę elementów, które masz w zestawie danych, a także jak duży jest każdy obiekt w zestawie danych, zanim podejmiesz tutaj dobrą decyzję. Baw się z nimi, stwórz je w jedną stronę i zobacz, która z nich działa szybciej. To dobre ćwiczenie.