Coś w stylu „zawiera jakieś” dla zestawu Java?

307

Mam dwa zestawy A i B tego samego typu.

Muszę sprawdzić, czy A zawiera jakikolwiek element ze zbioru B.

Jaki byłby najlepszy sposób na zrobienie tego bez powtarzania zestawów? Biblioteka Set ma contains(object)i containsAll(collection), ale nie ma containsAny(collection).

java 
— Rahul Garg
źródło
4
Czy starasz się unikać iteracji ze względu na wydajność lub czystość kodu?
— yshavit

Odpowiedzi:

527

Nie Collections.disjoint(A, B)działałoby? Z dokumentacji:

Zwraca, truejeśli dwie określone kolekcje nie mają wspólnych elementów.

Zatem metoda zwraca, falsejeśli kolekcje zawierają jakieś wspólne elementy.

— Linia frontu
źródło
17
Preferuj to od innych rozwiązań, ponieważ nie modyfikuje ono żadnego z zestawów ani nie tworzy nowego.
— devconsole,
7
Jest standardowym środowiskiem JRE i działa z dowolnymi kolekcjami, a nie tylko z ustawionymi.
— Pierre Henry
4
Nie sądzę, że jest to najszybsze, nie spowoduje zwarcia, gdy zostanie znaleziony pierwszy element skrzyżowania.
— Ben Horner,
7
W rzeczywistości spowoduje zwarcie, gdy tylko znajdzie pierwszy wspólny element
— Xipo,
3
— Lluis Martinez
156

Stream::anyMatch

Od wersji Java 8 możesz używać Stream::anyMatch.

setA.stream().anyMatch(setB::contains)
— gpl
źródło
1
Właśnie tego szukałem! Dzięki :-) Nie wiedziałem też, że możesz używać zmiennych ze składnią ::!
— dantiston 15.04.16
1
@blevert, czy możesz wyjaśnić, co się dzieje w anyMatch?
— Cristiano
7
@Cristiano tutaj, anyMatchprzesyła strumieniowo wszystkie elementy setAi wzywa setB.contains()je wszystkie. Jeśli dla któregoś z elementów zostanie zwrócona wartość „prawda”, wyrażenie jako całość zostanie ocenione na wartość prawda. Mam nadzieję, że to pomogło.
— Alex Vulaj,
2
— Lluis Martinez
31

Dobrym sposobem na zaimplementowanie funkcji ZawieraDowolny dla zestawów jest użycie Guava Sets.intersection () .

containsAnyzwróci a boolean, więc połączenie wygląda następująco:

Sets.intersection(set1, set2).isEmpty()

Zwraca true, jeśli zestawy są rozłączne, w przeciwnym razie false. Złożoność czasowa tego jest prawdopodobnie nieco lepsza niż zachowanie All, ponieważ nie trzeba wykonywać żadnego klonowania, aby uniknąć modyfikacji oryginalnego zestawu.

— CaTalyst.X
źródło
3
Jedyną wadą korzystania z tego podejścia jest konieczność włączenia bibliotek guava. Myślę, że nie jest to niekorzystne, ponieważ interfejsy API kolekcji Google są bardzo silne.
— Mohammad Adnan
@DidierL większość funkcji narzędzia Guava Collections, w tym ta, zwraca widoki struktur danych. Dlatego w tym przypadku nie trzeba się „martwić o budowanie zestawu”. Wdrożenie jest interesujące do przeczytania tutaj i / lub zobacz javadoc: google.github.io/guava/releases/21.0/api/docs/com/google/common/…
— chut
@MohammadAdnan Kolejną wadą jest to, że oblicza pełne przecięcie - jeśli set1 i set2 są bardzo duże, byłoby to znacznie bardziej wymagające pod względem zasobów (zarówno pod względem procesora, jak i pamięci) niż tylko sprawdzenie, czy mają one jakikolwiek wspólny element.
— Marxama,
16

Używam org.apache.commons.collections.CollectionUtils

CollectionUtils.containsAny(someCollection1, someCollection2)

To wszystko! Zwraca wartość true, jeśli co najmniej jeden element znajduje się w obu kolekcjach.

Prosty w użyciu, a nazwa funkcji jest bardziej sugestywna.

— Adam111p
źródło
5

Użyj retainAll()w interfejsie Ustaw. Ta metoda zapewnia przecięcie elementów wspólnych w obu zestawach. Zobacz dokumentację API, aby uzyskać więcej informacji.

— Suresh Kumar
źródło
Jeśli celem uniknięcia iteracji jest wydajność, retainAllprawdopodobnie nie pomoże. Jego implementacja w AbstractCollectioniteracjach.
— yshavit
1
yshavit jest poprawny. Biorąc pod uwagę, że OP chce sprawdzić, czy jakiś element istnieje w obu zestawach, właściwy algorytm miałby O(1)w najlepszym przypadku czas działania, podczas gdy retainAllmiałby coś wzdłuż linii O(N)(zależałoby to od wielkości tylko 1 zestawu) najlepszy czas działania.
— Zéychin
3

Poleciłbym utworzenie HashMapzestawu A, a następnie iterowanie przez zestaw B i sprawdzenie, czy którykolwiek element B znajduje się w A. To działałoby w O(|A|+|B|)czasie (ponieważ nie byłoby kolizji), podczas gdy retainAll(Collection<?> c)musiało działać w O(|A|*|B|)czasie.

— Zéychin
źródło
3

Jest to nieco trudna metoda. Jeśli tylko zestaw A zawiera element B niż wywołanie

A.removeAll(B)

zmodyfikuje zestaw A. W tej sytuacji removeAll zwróci wartość true (jak stwierdzono w removeAll docs ). Ale prawdopodobnie nie chcesz modyfikować zestawu A, więc możesz pomyśleć o działaniu na kopię, w następujący sposób:

new HashSet(A).removeAll(B)

a zwracana wartość będzie prawdziwa, jeśli zbiory nie będą odrębne, to znaczy, że mają niepuste przecięcie.

Zobacz także Kolekcje Apache Commons

— Plap
źródło
2

Możesz użyć metody retainAll i uzyskać przecięcie dwóch zbiorów.

— Artem
źródło
W większości przypadków należy zachować oryginalny zestaw, więc aby go użyć retainAll, należy wykonać kopię oryginalnego zestawu. Następnie jest bardziej wydajny w użyciu, HashSetjak sugeruje Zéychin .
— Petr Pudlák,
To zmiana stanu, a nie kontrola stanu
— Ben
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.