Algo como 'contém qualquer' para o conjunto Java?

307

Eu tenho dois conjuntos, A e B, do mesmo tipo.

Eu tenho que descobrir se A contém algum elemento do conjunto B.

Qual seria a melhor maneira de fazer isso sem percorrer os sets? A biblioteca Set possui contains(object)e containsAll(collection), mas não containsAny(collection).

java Rahul garg
fonte
4
Você está tentando evitar a iteração por motivos de eficiência ou limpeza de código?
yshavit

Respostas:

527

Não Collections.disjoint(A, B)funcionaria? A partir da documentação:

Retorna truese as duas coleções especificadas não tiverem elementos em comum.

Portanto, o método retornará falsese as coleções contiverem elementos comuns.

Linha de frente
fonte
17
Prefira isso às outras soluções, pois não modifica nenhum dos conjuntos nem cria um novo.
devconsole
7
E é o JRE padrão e funciona com quaisquer coleções, não apenas com o conjunto.
Pierre Henry
4
Eu não acho que isso seja mais rápido, não entrará em curto-circuito quando o primeiro elemento do cruzamento for encontrado.
Ben Horner
7
Na verdade ele irá curto-circuito, logo que ele encontra o primeiro elemento comum
xipo
3
@Xipo está certo. Verifique grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/…
Lluis Martinez
156

Stream::anyMatch

Desde o Java 8 você pode usar Stream::anyMatch.

setA.stream().anyMatch(setB::contains)
gpl
fonte
1
Era exatamente isso que eu estava procurando! Obrigado :-) Eu também não sabia que você poderia usar variáveis ​​com a sintaxe ::!
precisa saber é o seguinte
1
@blevert, você poderia explicar o que acontece dentro do anyMatch?
Cristiano
8
@ Cristiano aqui, anyMatchtransmitirá todos os elementos setAe os chamará setB.contains(). Se "true" for retornado para qualquer um dos elementos, a expressão como um todo será avaliada como true. Espero que isso tenha ajudado.
Alex Vulaj
2
@Cristiano docs.oracle.com/javase/8/docs/api/java/util/stream/…
Lluis Martinez
31

Uma boa maneira de implementar o containsAny para conjuntos é usar o Guava Sets.intersection () .

containsAnyretornaria um boolean, para que a chamada se pareça com:

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

Isso retorna true se os conjuntos forem disjuntos, caso contrário, false. A complexidade de tempo disso é provavelmente um pouco melhor que reterAll, porque você não precisa fazer nenhuma clonagem para evitar modificar seu conjunto original.

CaTalyst.X
fonte
3
A única desvantagem de usar essa abordagem é que você deve incluir bibliotecas de goiaba. O que eu acho que não é uma desvantagem, porque as APIs de coleta do Google são muito fortes.
Mohammad Adnan
@DidierL A maioria das funções do utilitário Guava Collections, incluindo esta, retornam visualizações das estruturas de dados. Portanto, não há como "construir o conjunto" nesse caso. É interessante ler a implementação aqui e / ou ver o javadoc: google.github.io/guava/releases/21.0/api/docs/com/google/common/…
chut
@MohammadAdnan Outra desvantagem é que ele calcula a interseção completa - se o conjunto1 e o conjunto2 forem muito grandes, isso seria muito mais intensivo em recursos (CPU e memória) do que apenas verificar se eles têm algum item em comum.
Marxama
16

Eu uso org.apache.commons.collections.CollectionUtils

CollectionUtils.containsAny(someCollection1, someCollection2)

Isso é tudo! Retorna true se pelo menos um elemento estiver nas duas coleções.

Simples de usar, e o nome da função é mais sugestivo.

Adam111p
fonte
5

Use retainAll()na interface Set. Este método fornece uma interseção de elementos comuns nos dois conjuntos. Consulte os documentos da API para obter mais informações.

Suresh Kumar
fonte
Se o objetivo de evitar a iteração for de eficiência, retainAllprovavelmente não ajudará. Sua implementação AbstractCollectionitera.
yshavit
1
O yshavit está correto. Dado que o OP está olhando para ver se existe algum elemento nos dois conjuntos, um algoritmo adequado teria um O(1)tempo de execução no melhor dos casos, enquanto retainAllteria algo ao longo das linhas de um O(N)(isso dependeria do tamanho de apenas 1 conjunto) melhor tempo de execução.
Zéychin
3

Eu recomendaria criar um a HashMappartir do conjunto A e, em seguida, percorrer o conjunto B e verificar se algum elemento de B está em A. Isso seria executado no O(|A|+|B|)tempo (como não haveria colisões), enquanto retainAll(Collection<?> c)deve ser executado no O(|A|*|B|)tempo.

Zéychin
fonte
3

Existe um método um pouco difícil de fazer isso. Se e somente se o conjunto A contiver algum elemento de B, a chamada

A.removeAll(B)

irá modificar o conjunto A. Nesta situação, removeAll retornará true (conforme indicado em removeAll docs ). Mas provavelmente você não deseja modificar o conjunto A para pensar em agir em uma cópia, assim:

new HashSet(A).removeAll(B)

e o valor retornado será verdadeiro se os conjuntos não forem distintos, ou seja, com interseção não vazia.

Veja também as coleções do Apache Commons

Plap
fonte
2

Você pode usar o método reterAll e obter a interseção de seus dois conjuntos.

Artem
fonte
Na maioria dos casos, é necessário manter o conjunto original, portanto, para usá- retainAlllo, é necessário fazer uma cópia do conjunto original. Então é mais eficiente usar HashSetcomo sugerido por Zéychin .
Petr Pudlák
Isso é uma mudança de estado, não verificação de condição
Ben