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

Zamieściłem kilka rzeczy w komentarzach, myślę, że zasługuje na własną odpowiedź.

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

Opcja 1

Użyj containsAll(). Ta opcja nie jest idealna, moim zdaniem, ponieważ oferuje najgorszą wydajność, O (N^2).

Opcja 2

Istnieją dwie odmiany tego:

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

2b) Jeśli chcesz zachować kolejność 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.

Prowadzi to do:

Opcja 3

Jeśli Twoje wymagania są takie same jak część 2b , ale kopiowanie jest zbyt drogie. Możesz użyć zestawu drzew do sortowania za Ciebie. Zrzuć każdą listę do własnego zestawu drzew. Zostanie on posortowany w zestawie, a oryginalne listy pozostaną nienaruszone. Następnie wykonaj equals() Porównanie na obu TreeSet s. TreeSets s może być zbudowany w czasie O (nlogn), a equals() Jest O (n).

Wybierz: -).

edytuj: prawie zapomniałem o tym samym zastrzeżeniu, na które zwraca uwagę Laurence Gonsalves. Wdrożenie TreeSet wyeliminuje duplikaty. Jeśli zależy ci na duplikatach, będziesz potrzebował jakiegoś posortowanego multisetu.

Jeśli używasz (lub chętnie używasz) kolekcji Apache Commons, możesz użyć CollectionUtils.isEqualCollection, która " zwraca true iff dane zbiory zawierają dokładnie te same elementy o dokładnie tych samych cechach kardynalnych."

Wiem, że to stary wątek, ale żadna z innych odpowiedzi nie rozwiązała w pełni mojego przypadku użycia(myślę, że Guava Multiset może zrobić to samo, ale nie ma tutaj przykładu). Proszę wybaczyć moje formatowanie. Nadal jestem nowy w publikowaniu na stack exchange. 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 następującym warunkom:

1) O(n) oczekiwany czas pracy
2) równość definiowana jest jako: dla wszystkich elementy w a lub b, Liczba wystąpień elementu w a jest równa liczbie wystąpień elementu w b. równość elementu 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 pracy wynosi O(n), ponieważ wykonujemy o(2*n) wstawianie do hashmapy i O (3*N) wybór hashmapy. Nie do końca 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();
}

Bardzo późno na imprezę, ale chciałem dodać ten null safe check:

Objects.equals(list1, list2)

Rozwiązanie dla przypadku, gdy dwie listy mają te same elementy, ale różną kolejność:

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 zgadzam się w pełni z jego odpowiedziami!

Interesującym aspektem tego pytania jest to, czy potrzebny jest sam typ List i jego nieodłączna kolejność.

Jeśli nie, możesz zdegradować do Iterable lub Collection, co daje Ci pewną elastyczność w przekazywaniu struktur danych, które są sortowane w czasie wstawiania, a nie w czasie, w którym chcesz to sprawdzić.

Jeśli kolejność nie ma znaczenia (i nie masz duplikatów elementów) rozważ użycie Set.

Jeśli kolejność ma znaczenie, ale jest określona przez czas wstawiania (a nie masz duplikatów) rozważ LinkedHashSet, który jest podobny do zbioru drzew, ale jest uporządkowany według czasu wstawiania (duplikaty nie są liczone). To również daje O(1) amortyzowany dostęp do O(log n).

Metoda equals na liście zrobi to, 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);

list1.equals(list2);

Jeśli Twoja lista zawiera niestandardową klasę MyClass, ta klasa musi nadpisać funkcję equals.

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

Uwaga: Jeśli chcesz przetestować equals na Javie.util.Ustaw zamiast java.util.List, wtedy twój obiekt musi nadpisać funkcję hashCode.

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, aby była bezpieczna dla null:

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

Lista.equals ()

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

Możesz użyć org Apache ' a.Apacz.commons.biblioteka zbiorów: 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ą null. Jeśli ich rozmiary są różne, to listy te nie są sobie 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ą nullami, 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;
}

Proszę zauważyć, że 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 listy używasz. Klasa abstrakcyjna AbstractCollection ma metodę o nazwie containsAll (Collection), która pobiera inny zbiór ( lista jest zbiorem) i:

Zwraca true, jeśli ta kolekcja zawiera wszystkie elementy w podanej kolekcji.

Więc jeśli ArrayList jest przekazywana w można wywołać tę metodę, aby sprawdzić, 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 containsAll() jest to, że przechodzi przez pierwszą listę szukając dopasowania na drugiej liście. Więc jeśli są one nie w porządku, equals() nie odbierze go.

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

Koszt kopiowania każdego pojedynczego elementu z listy do innych list wymaga 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 jest problemem (co powinno być ogólnie), nadal musisz wziąć pod uwagę czas potrzebny na skopiowanie każdego elementu z dwóch list do dwóch zestawów drzew. Pamiętaj, że sortuje każdy element, gdy wchodzi do nich.