Java ArrayList-comment savoir si deux listes sont égales, l'ordre ne compte pas?
j'ai deux tableaux de type Answer(self-made class).
j'aimerais comparer les deux listes pour voir si elles contiennent le même contenu, mais sans ordre et sans compter.
exemple:
//These should be equal.
ArrayList<String> listA = {"a", "b", "c"}
ArrayList<String> listB = {"b", "c", "a"}
List.equals déclare que deux listes sont égales si elles contiennent la même taille, le même contenu et le même ordre d'éléments. Je veux la même chose, mais sans ordre.
est-il une façon simple de faire cette? Ou vais-je devoir faire une boucle emboîtée, et vérifier manuellement chaque index des deux listes?
Note: Je ne peux pas les changer d'ArrayList à un autre type de liste, ils doivent le rester.
16 réponses
vous pouvez trier les deux listes en utilisant Collections.sort()
et ensuite utiliser la méthode égal. Une solution légèrement meilleure est de vérifier d'abord si elles sont de la même longueur Avant de commander, si elles ne le sont pas, alors elles ne sont pas égales, puis de trier, puis d'utiliser des égaux. Par exemple, si vous aviez deux listes de Chaînes, ce serait quelque chose comme:
public boolean equalLists(List<String> one, List<String> two){
if (one == null && two == null){
return true;
}
if((one == null && two != null)
|| one != null && two == null
|| one.size() != two.size()){
return false;
}
//to avoid messing the order of the lists we will use a copy
//as noted in comments by A. R. S.
one = new ArrayList<String>(one);
two = new ArrayList<String>(two);
Collections.sort(one);
Collections.sort(two);
return one.equals(two);
}
Apache Commons Collections à la rescousse une fois de plus:
List<String> listA = Arrays.asList("a", "b", "b", "c");
List<String> listB = Arrays.asList("b", "c", "a", "b");
System.out.println(CollectionUtils.isEqualCollection(listA, listB)); // true
List<String> listC = Arrays.asList("a", "b", "c");
List<String> listD = Arrays.asList("a", "b", "c", "c");
System.out.println(CollectionUtils.isEqualCollection(listC, listD)); // false
Docs:
org.apache.commons.collections4.CollectionUtils
public static boolean isEqualCollection(java.util.Collection a, java.util.Collection b)
Les retours
true
iff le donnéCollection
s contiennent exactement le même éléments avec exactement le même cardinalités.C'est-à-dire, iff le la cardinalité de e dans un est égal à la cardinalité de e dans b , pour chaque l'élément e dans un ou b .
paramètres:
a
- la première collection, ne doit pas êtrenull
b
- la seconde collection, ne doit pas êtrenull
Renvoie:
true
iff les collections contiennent les mêmes éléments avec le même cardinalités.
// helper class, so we don't have to do a whole lot of autoboxing
private static class Count {
public int count = 0;
}
public boolean haveSameElements(final List<String> list1, final List<String> list2) {
// (list1, list1) is always true
if (list1 == list2) return true;
// If either list is null, or the lengths are not equal, they can't possibly match
if (list1 == null || list2 == null || list1.size() != list2.size())
return false;
// (switch the two checks above if (null, null) should return false)
Map<String, Count> counts = new HashMap<>();
// Count the items in list1
for (String item : list1) {
if (!counts.containsKey(item)) counts.put(item, new Count());
counts.get(item).count += 1;
}
// Subtract the count of items in list2
for (String item : list2) {
// If the map doesn't contain the item here, then this item wasn't in list1
if (!counts.containsKey(item)) return false;
counts.get(item).count -= 1;
}
// If any count is nonzero at this point, then the two lists don't match
for (Map.Entry<String, Count> entry : counts.entrySet()) {
if (entry.getValue().count != 0) return false;
}
return true;
}
c'est basé sur la solution @cHao. J'ai inclus plusieurs corrections et améliorations de performances. Cela va environ deux fois plus vite que la solution égale-commandé-copie. Fonctionne pour tout type de collection. Les collections vides et nulles sont considérées comme égales. Utilisez à votre avantage ;)
/**
* Returns if both {@link Collection Collections} contains the same elements, in the same quantities, regardless of order and collection type.
* <p>
* Empty collections and {@code null} are regarded as equal.
*/
public static <T> boolean haveSameElements(Collection<T> col1, Collection<T> col2) {
if (col1 == col2)
return true;
// If either list is null, return whether the other is empty
if (col1 == null)
return col2.isEmpty();
if (col2 == null)
return col1.isEmpty();
// If lengths are not equal, they can't possibly match
if (col1.size() != col2.size())
return false;
// Helper class, so we don't have to do a whole lot of autoboxing
class Count
{
// Initialize as 1, as we would increment it anyway
public int count = 1;
}
final Map<T, Count> counts = new HashMap<>();
// Count the items in list1
for (final T item : col1) {
final Count count = counts.get(item);
if (count != null)
count.count++;
else
// If the map doesn't contain the item, put a new count
counts.put(item, new Count());
}
// Subtract the count of items in list2
for (final T item : col2) {
final Count count = counts.get(item);
// If the map doesn't contain the item, or the count is already reduced to 0, the lists are unequal
if (count == null || count.count == 0)
return false;
count.count--;
}
// If any count is nonzero at this point, then the two lists don't match
for (final Count count : counts.values())
if (count.count != 0)
return false;
return true;
}
si la cardinalité des éléments n'a pas d'importance (c'est-à-dire que les éléments répétés sont considérés comme un seul), alors il y a un moyen de le faire sans avoir à trier:
boolean result = new HashSet<>(listA).equals(new HashSet<>(listB));
cela créera un Set
de chaque List
, et puis utiliser HashSet
's equals
méthode qui (bien sûr) ne tient pas compte de la commande.
si la cardinalité est importante, alors vous devez vous limiter aux installations fournies par List
; la réponse de @jschoen serait plus appropriée dans ce cas.
pensez à la façon dont vous le feriez vous-même, en l'absence d'un ordinateur ou d'un langage de programmation. Je vous donne deux listes d'éléments, et vous avez à me dire s'ils contiennent les mêmes éléments. Comment le feriez-vous?
l'une des approches, mentionnée ci-dessus, consiste à trier les listes puis à aller élément par élément pour voir si elles sont égales (ce que fait List.equals
). Cela signifie que soit vous êtes autorisé à modifier les listes ou vous êtes autorisé à les copier-et sans connaître les affectation, Je ne peux pas savoir si l'un ou l'autre / les deux sont autorisés.
une autre approche serait de passer en revue chaque liste, en comptant combien de fois chaque élément apparaît. Si deux listes ont le même compte à la fin, ils ont les mêmes éléments. Le code pour ce qui serait de traduire chaque liste à une carte de elem -> (# of times the elem appears in the list)
et ensuite appeler equals
sur les deux cartes. Si les cartes sont HashMap
, chacune de ces traductions est une opération O(N), comme l'est la comparaison. Qui va pour vous donner une jolie algorithme efficace en termes de temps, au prix d'un peu plus de mémoire.
j'ai eu ce même problème et est venu avec une solution différente. Celui-ci fonctionne aussi lorsque des doublons sont impliqués:
public static boolean equalsWithoutOrder(List<?> fst, List<?> snd){
if(fst != null && snd != null){
if(fst.size() == snd.size()){
// create copied lists so the original list is not modified
List<?> cfst = new ArrayList<Object>(fst);
List<?> csnd = new ArrayList<Object>(snd);
Iterator<?> ifst = cfst.iterator();
boolean foundEqualObject;
while( ifst.hasNext() ){
Iterator<?> isnd = csnd.iterator();
foundEqualObject = false;
while( isnd.hasNext() ){
if( ifst.next().equals(isnd.next()) ){
ifst.remove();
isnd.remove();
foundEqualObject = true;
break;
}
}
if( !foundEqualObject ){
// fail early
break;
}
}
if(cfst.isEmpty()){ //both temporary lists have the same size
return true;
}
}
}else if( fst == null && snd == null ){
return true;
}
return false;
}
avantages par rapport à d'autres solutions:
- moins de O(N2) complexité (bien que je n'ai pas testé c'est de la vraie performance en comparaison des solutions dans d'autres réponses ici);
- sort tôt;
- vérifie null;
- fonctionne même lorsque les doublons sont impliqués: si vous avez un tableau
[1,2,3,3]
et un autre tableau[1,2,2,3]
la plupart des solutions ici vous disent qu'elles sont les mêmes lorsque vous ne considérez pas l'ordre. Cette solution permet d'éviter cela en retirant des éléments égaux des listes temporaires; - utilise l'égalité sémantique (
equals
) et non l'égalité de référence (==
); - ne fait pas de tri, de sorte qu'ils n'ont pas besoin d'être sortable (par
implement Comparable
) pour cette solution travailler.
je dirais que ces réponses manquent une astuce.
Bloch, dans son essentiel, merveilleux, concis Java efficace , dit, dans le point 47, titre "connaître et utiliser les bibliothèques", "pour résumer, ne pas réinventer la roue". Et il donne plusieurs raisons très claires pour ne pas le faire.
il y a quelques réponses ici qui suggèrent des méthodes de CollectionUtils
dans la bibliothèque des collections communes Apache mais aucune n'a repéré le plus belle, élégante façon de répondre à cette question :
Collection<Object> culprits = CollectionUtils.disjunction( list1, list2 );
if( ! culprits.isEmpty() ){
// ... then in most cases you will ardently wish to do something to these culprits:
// at the very least, name-and-shame them.
}
coupables : c'est-à-dire les éléments qui ne sont pas communs aux deux Lists
. Il est relativement simple de déterminer quels sont les coupables de list1
et de list2
en utilisant les Termes CollectionUtils.intersection( list1, culprits )
et CollectionUtils.intersection( list2, culprits )
.
Cependant, il a tendance à tomber en morceaux dans des cas comme { "a", "a", "b" } disjunction
avec { "a", "b", "b" } ... sauf ce n'est pas un défaut du logiciel, mais inhérente à la nature de l'subtilités/ambiguïtés de la tâche souhaitée.
NB j'ai d'abord été déçu qu'aucune des méthodes CollectionUtils
ne fournisse une version surchargée vous permettant d'imposer votre propre Comparator
(pour que vous puissiez redéfinir equals
en fonction de vos besoins).
mais à partir de collections4 4.0 il y a une nouvelle classe, Equator
qui " détermine égalité entre les objets de type T". Sur l'examen du code source de collections4 CollectionUtils.java ils semblent l'utiliser avec certaines méthodes, mais pour autant que je puisse en juger, ce n'est pas applicable aux méthodes en haut du fichier, en utilisant la classe CardinalityHelper
... qui comprennent disjunction
et intersection
.
je suppose que le peuple Apache n'a pas encore eu le temps de le faire parce que c'est non-trivial: il faudrait créer quelque chose comme Classe " AbstractEquatingCollection "qui, au lieu d'utiliser ses éléments" inhérents equals
et hashCode
méthodes devrait plutôt utiliser ceux de Equator
pour toutes les méthodes de base, tels que add
, contains
, etc. NB en fait, lorsque vous regardez le code source, AbstractCollection
n'implémente pas add
, ni ses sous-classes abstraites telles que AbstractSet
... vous devez attendre jusqu'à ce que les classes concrètes telles que HashSet
et ArrayList
avant add
est mis en œuvre. Un véritable casse-tête.
dans le temps, regardez cet espace, je suppose. La solution provisoire évidente serait d'envelopper tous vos éléments dans une classe d'emballage sur mesure qui utilise equals
et hashCode
pour mettre en œuvre le genre d'Égalité que vous voulez... puis manipulez Collections
de ces objets d'emballage.
convertissant les listes en Multiset de Guava fonctionne très bien. Ils sont comparés indépendamment de leur ordre et les éléments dupliqués sont également pris en compte.
static <T> boolean equalsIgnoreOrder(List<T> a, List<T> b) {
return ImmutableMultiset.copyOf(a).equals(ImmutableMultiset.copyOf(b));
}
assert equalsIgnoreOrder(ImmutableList.of(3, 1, 2), ImmutableList.of(2, 1, 3));
assert !equalsIgnoreOrder(ImmutableList.of(1), ImmutableList.of(1, 1));
Solution qui utilise la méthode de soustraction des collectes:
import static org.apache.commons.collections15.CollectionUtils.subtract;
public class CollectionUtils {
static public <T> boolean equals(Collection<? extends T> a, Collection<? extends T> b) {
if (a == null && b == null)
return true;
if (a == null || b == null || a.size() != b.size())
return false;
return subtract(a, b).size() == 0 && subtract(a, b).size() == 0;
}
}
si vous n'espérez pas trier les collections et vous avez besoin du résultat que ["A" "B" "C"] n'est pas égal à ["B" "B" A" C"],
l1.containsAll(l2)&&l2.containsAll(l1)
n'est pas suffisant, vous devez probablement vérifier la taille aussi:
List<String> l1 =Arrays.asList("A","A","B","C");
List<String> l2 =Arrays.asList("A","B","C");
List<String> l3 =Arrays.asList("A","B","C");
System.out.println(l1.containsAll(l2)&&l2.containsAll(l1));//cautions, this will be true
System.out.println(isListEqualsWithoutOrder(l1,l2));//false as expected
System.out.println(l3.containsAll(l2)&&l2.containsAll(l3));//true as expected
System.out.println(isListEqualsWithoutOrder(l2,l3));//true as expected
public static boolean isListEqualsWithoutOrder(List<String> l1, List<String> l2) {
return l1.size()==l2.size() && l1.containsAll(l2)&&l2.containsAll(l1);
}
Le Meilleur des deux mondes [@DiddiZ, @Chalkos]: celui-ci s'appuie principalement sur la méthode @Chalkos, mais corrige un bug (ifst.next()), et améliore les contrôles initiaux (pris de @DiddiZ) ainsi que supprime la nécessité de copier la première collection (supprime simplement les éléments d'une copie de la deuxième collection).
ne nécessitant pas une fonction de hachage ou de tri, et permettant une existence précoce sur un-égalité, il s'agit de la mise en œuvre la plus efficace à ce jour. Sauf si vous avez une collection longueur dans les milliers ou plus, et une fonction de hachage très simple.
public static <T> boolean isCollectionMatch(Collection<T> one, Collection<T> two) {
if (one == two)
return true;
// If either list is null, return whether the other is empty
if (one == null)
return two.isEmpty();
if (two == null)
return one.isEmpty();
// If lengths are not equal, they can't possibly match
if (one.size() != two.size())
return false;
// copy the second list, so it can be modified
final List<T> ctwo = new ArrayList<>(two);
for (T itm : one) {
Iterator<T> it = ctwo.iterator();
boolean gotEq = false;
while (it.hasNext()) {
if (itm.equals(it.next())) {
it.remove();
gotEq = true;
break;
}
}
if (!gotEq) return false;
}
// All elements in one were found in two, and they're the same size.
return true;
}
c'est une alternative pour vérifier l'égalité des listes de tableaux qui peuvent contenir des valeurs nulles:
List listA = Arrays.asList(null, "b", "c");
List listB = Arrays.asList("b", "c", null);
System.out.println(checkEquality(listA, listB)); // will return TRUE
private List<String> getSortedArrayList(List<String> arrayList)
{
String[] array = arrayList.toArray(new String[arrayList.size()]);
Arrays.sort(array, new Comparator<String>()
{
@Override
public int compare(String o1, String o2)
{
if (o1 == null && o2 == null)
{
return 0;
}
if (o1 == null)
{
return 1;
}
if (o2 == null)
{
return -1;
}
return o1.compareTo(o2);
}
});
return new ArrayList(Arrays.asList(array));
}
private Boolean checkEquality(List<String> listA, List<String> listB)
{
listA = getSortedArrayList(listA);
listB = getSortedArrayList(listB);
String[] arrayA = listA.toArray(new String[listA.size()]);
String[] arrayB = listB.toArray(new String[listB.size()]);
return Arrays.deepEquals(arrayA, arrayB);
}
si vous vous souciez de l'ordre, alors utilisez juste la méthode égale:
list1.equals(list2)
Dans ce cas, les listes {"a", "b"} et {"b",""} sont égaux. Et {"a", "b"} et {"b","a","c"} ne sont pas égaux. Si vous utilisez la liste des objets complexes, n'oubliez pas de remplacer égale "méthode 151930920", comme containsAll l'utilise à l'intérieur.
if (oneList.size() == secondList.size() && oneList.containsAll(secondList)){
areEqual = true;
}