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
@Xipo ma rację. Sprawdź grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/...
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
@Cristiano docs.oracle.com/javase/8/docs/api/java/util/stream/…
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