Pytanie Sprawdź, czy jedna lista zawiera element z drugiej


Mam dwie listy z różnymi obiektami.

List<Object1> list1;
List<Object2> list2;

Chcę sprawdzić, czy element z listy1 istnieje na liście2, na podstawie określonego atrybutu (Obiekty1 i Obiekt2 mają (między innymi) jeden wspólny atrybut (z typem Długi), o nazwie atrybutnazwa).

teraz, robię to tak:

boolean found = false;
for(Object1 object1 : list1){
   for(Object2 object2: list2){
       if(object1.getAttributeSame() == object2.getAttributeSame()){
           found = true;
           //also do something
       }
    }
    if(!found){
        //do something
    }
    found = false;
}

Ale myślę, że jest lepszy i szybszy sposób na zrobienie tego :) Czy ktoś może to zaproponować?

Dzięki!


76
2017-08-03 13:08


pochodzenie


po pierwsze, gdy ustawisz found = true; następnie po prostu przełamaj; lub wyjść z pętli - Shubhansh
stackoverflow.com/questions/5187888/.... Co więcej, aby przyspieszyć wyszukiwanie, spróbuj użyć Binary Search i zmień swoje DS, aby dopasować sytuację ... - Shubhansh
czy dzielą wspólnego rodzica poza Object? - Woot4Moo
@ Woot4Moo nie, nie robią tego - Ned


Odpowiedzi:


Można to zrobić za pomocą podstawowego JDK bez modyfikowania list wejściowych w jednym wierszu

!Collections.disjoint(list1, list2);

160
2017-08-03 15:59



Czy to nie zawsze zwróci fałsz, ponieważ oba są 2 różnymi obiektami? - Venki
Yyy ... nie? Rozłączne testy, jeśli nie ma żadnych obiektów równych () między sobą między dwiema kolekcjami. - Louis Wasserman
Zwróć też uwagę, że dla list będzie to O (n * m); jeśli chcesz skopiować list1 do a Set przed porównaniem otrzymasz O (n) + O (m), czyli O (n + m), kosztem dodatkowej pamięci RAM; to kwestia wyboru między szybkością a pamięcią. - Haroldo_OK
Łał! wydaje się działać na razie - delive
Ta odpowiedź nie ma sensu. W jaki sposób bierze się pod uwagę fakt, że OP chce porównać pojedynczą, określoną wartość w dwóch przedmiotach? - Zephyr


Możesz użyć Apache Commons CollectionUtils:

if(CollectionUtils.containsAny(list1,list2)) {  
    // do whatever you want
} else { 
    // do other thing 
}  

Zakłada to, że prawidłowo przeciąłeś funkcję równości dla swoich obiektów niestandardowych.


31
2017-08-03 13:19



Martwe, kolego. - alexander
minęły 4 lata, a ja wyraźnie nazywam pakiet i funkcję. - Woot4Moo
Zgłaszaj się na apache commons, gdy istnieje rozwiązanie tylko jdk - ohcibi
@ohcibi Java ma również wbudowany program rejestrujący, powinieneś pójść w dół do osób sugerujących używanie Log4j i Log4j2, gdy jesteś na tym. - Woot4Moo
@ Woot4Moo to zależy. Nie ma powodu do odrzucenia, jeśli istnieje powód, aby użyć Log4j do rozwiązania problemu OP. W tym przypadku błonka Apache byłaby po prostu bezużyteczna, rozdęta jak w 99% odpowiedzi sugerujących wspólne apache. - ohcibi


Jest jedna metoda z Collection o imieniu retainAll ale mając trochę skutki uboczne dla Ciebie odniesienie

Zachowuje tylko te elementy z listy, które znajdują się w   określony zbiór (operacja opcjonalna). Innymi słowy, usuwa   z tej listy wszystkie jego elementy, które nie są zawarte w   określony zbiór.

true, jeśli lista zmieniła się w wyniku połączenia

To jest jak

boolean b = list1.retainAll(list2);

8
2017-08-03 13:23





Odpowiedź Loius jest poprawna, chcę tylko dodać przykład:

listOne.add("A");
listOne.add("B");
listOne.add("C");

listTwo.add("D");
listTwo.add("E");
listTwo.add("F");      

boolean noElementsInCommon = Collections.disjoint(listOne, listTwo); // true

3
2018-02-19 16:57



Myślę, że jeśli dodasz element "A" do drugiej listy listTwo.add ("A"); mimo że Collections.disjoint (listOne, listTwo); zwraca true. - Sairam Kukadala


szybszy sposób będzie wymagał dodatkowej przestrzeni.

Na przykład:

  1. umieść wszystkie elementy w jednej liście w HashSet (musisz zaimplementować funkcję mieszającą samodzielnie, aby użyć obiektu object.getAttributeSame ())

  2. Przejdź przez drugą listę i sprawdź, czy jakikolwiek element znajduje się w HashSet.

W ten sposób każdy obiekt jest odwiedzany co najwyżej raz. i HashSet jest wystarczająco szybki, aby sprawdzić lub wstawić dowolny obiekt w O (1).


2
2017-08-03 13:20





Zgodnie z JavaDoc dla .contains(Object obj):

Zwraca wartość true, jeśli ta lista zawiera określony element. Jeszcze   formalnie zwraca wartość true wtedy i tylko wtedy, gdy ta lista zawiera co najmniej jeden   element e taki, że (o == null? e == null: o.equals (e)).

Więc jeśli przesłonisz swoje .equals() metoda dla danego obiektu, powinieneś być w stanie: if(list1.contains(object2))...

Jeśli elementy będą unikatowe (tj. Mają różne atrybuty), możesz zastąpić je .equals() i .hashcode() i przechowuj wszystko w HashSets. Pozwoli to sprawdzić, czy jeden zawiera inny element w stałym czasie.


2
2017-08-03 13:13





aby przyspieszyć, możesz dodać przerwę; w ten sposób pętla zatrzyma się, jeśli zostanie ustawiona na true:

boolean found = false;
for(Object1 object1 : list1){
   for(Object2 object2: list2){
       if(object1.getAttributeSame() == object2.getAttributeSame()){
           found = true;
           //also do something  
           break;
       }
    }
    if(!found){
        //do something
    }
    found = false;
}

Jeśli zamiast mapy miałbyś posiadać mapy z kluczami attributeSame, możesz szybciej sprawdzić wartość w jednej mapie, jeśli na drugiej mapie znajduje się odpowiednia wartość.


1
2017-08-03 13:10



Cześć Tom, dzięki za uwagę! Tak, zapomniałem "zepsuć się" podczas pisania. Ale myślałem, że może jest jakiś algorytm, albo powinienem zmienić te listy w inne kolekcje. - Ned
Zrobiłem edycję, aby odpowiedzieć na twój komentarz - Tom
czy nie ma nic lepszego niż O (n * m)? - Woot4Moo
.getAttributeSame ()? - Manish
Implementacja metody getAttributeSame () z Object1 i Object2 nie została podana, ale także nie ma znaczenia dla pytania i odpowiedzi; po prostu zwraca atrybut (attributeSame, a Long), który mają obie klasy. - Tom


Czy potrafisz zdefiniować rodzaj przechowywanych danych? czy to duże dane? czy to jest sortowane? Uważam, że należy wziąć pod uwagę różne podejścia do efektywności w zależności od danych.

Na przykład, jeśli twoje dane są duże i nieposortowane, możesz spróbować iterować dwie listy według indeksu i przechowywać każdy atrybut listy w innym pomocniku listy. wtedy możesz sprawdzić krzyżyk według bieżących atrybutów na listach pomocników.

powodzenia

edytowane: i nie polecam przeciążania równych. jej niebezpieczny i prawdopodobnie przeciwko waszemu obiektowi znaczenie.


0
2017-08-03 13:27