¿Algo como 'contiene alguno' para el conjunto de Java?

307

Tengo dos conjuntos, A y B, del mismo tipo.

Tengo que encontrar si A contiene algún elemento del conjunto B.

¿Cuál sería la mejor manera de hacerlo sin iterar sobre los conjuntos? La biblioteca Set tiene contains(object)y containsAll(collection), pero no containsAny(collection).

java Rahul garg
fuente
44
¿Está tratando de evitar iterar por razones de eficiencia o por la limpieza del código?
yshavit

Respuestas:

527

No Collections.disjoint(A, B)funcionaria? De la documentación:

Devuelve truesi las dos colecciones especificadas no tienen elementos en común.

Por lo tanto, el método devuelve falsesi las colecciones contienen elementos comunes.

Primera línea
fuente
17
Prefiera esto a las otras soluciones porque no modifica ninguno de los conjuntos ni crea uno nuevo.
devconsole
77
Y es JRE estándar, y funciona con cualquier Colección, no solo configurada.
Pierre Henry
44
No creo que sea más rápido, no se cortocircuitará cuando se encuentre el primer elemento de la intersección.
Ben Horner
77
En realidad, hará un cortocircuito tan pronto como encuentre el primer elemento común
Xipo
3
@Xipo tiene razón. Consulte grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/…
Lluis Martinez
156

Stream::anyMatch

Desde Java 8 podrías usar Stream::anyMatch.

setA.stream().anyMatch(setB::contains)
gpl
fuente
1
¡Esto es exactamente lo que estaba buscando! Gracias :-) ¡Tampoco sabía que podía usar variables con la sintaxis ::!
dantiston
1
@blevert, ¿podría explicar qué sucede dentro de anyMatch?
Cristiano
8
@Cristiano aquí, anyMatchtransmitirá todos los elementos setAy los llamará setB.contains()a todos. Si se devuelve "verdadero" para cualquiera de los elementos, la expresión como un todo se evaluará como verdadera. Espero que esto haya ayudado.
Alex Vulaj
2
@Cristiano docs.oracle.com/javase/8/docs/api/java/util/stream/…
Lluis Martinez
31

Una buena forma de implementar contieneAny para conjuntos es usar Guava Sets.intersection () .

containsAnydevolvería un boolean, por lo que la llamada se ve así:

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

Esto devuelve verdadero si los conjuntos son disjuntos, de lo contrario falso. La complejidad temporal de esto es probablemente un poco mejor que retener todo porque no tiene que hacer ninguna clonación para evitar modificar su conjunto original.

CaTalyst.X
fuente
3
La única desventaja de usar este enfoque es que debe incluir bibliotecas de guayaba. Lo que creo que no es una desventaja porque las API de la colección de Google son muy fuertes.
Mohammad Adnan
@DidierL la mayoría de las funciones de la utilidad Guava Collections, incluida esta, devuelven vistas de las estructuras de datos. Por lo tanto, no hay "construcción del conjunto" de qué preocuparse en este caso. La implementación es interesante para leer aquí, y / o ver el javadoc: google.github.io/guava/releases/21.0/api/docs/com/google/common/…
chut
@MohammadAdnan Otra desventaja es que calcula la intersección completa: si set1 y set2 son muy grandes, esto requeriría muchos más recursos (tanto de CPU como de memoria) que solo verificar si tienen algún elemento en común.
Marxama
16

Yo uso org.apache.commons.collections.CollectionUtils

CollectionUtils.containsAny(someCollection1, someCollection2)

¡Eso es todo! Devuelve verdadero si al menos un elemento está en ambas colecciones.

Simple de usar, y el nombre de la función es más sugerente.

Adam111p
fuente
5

Úselo retainAll()en la interfaz Set. Este método proporciona una intersección de elementos comunes en ambos conjuntos. Consulte los documentos de la API para obtener más información.

Suresh Kumar
fuente
Si el punto de evitar la iteración es por eficiencia, retainAllprobablemente no ayudará. Su implementación en AbstractCollectioniteraciones.
yshavit
1
yshavit es correcto. Dado que el OP está buscando ver si existe algún elemento en ambos conjuntos, un algoritmo adecuado tendría un O(1)tiempo de ejecución en el mejor de los casos, mientras retainAllque tendría algo similar a un O(N)(dependería del tamaño de solo 1 conjunto) mejor tiempo de ejecución.
Zéychin
3

Recomendaría crear un HashMapconjunto A y luego iterar a través del conjunto B y verificar si algún elemento de B está en A. Esto se ejecutaría a O(|A|+|B|)tiempo (ya que no habría colisiones), mientras que retainAll(Collection<?> c)debe ejecutarse a O(|A|*|B|)tiempo.

Zéychin
fuente
3

Hay un método un poco difícil para hacer eso. Si y solo si el conjunto A contiene algún elemento de B que la llamada

A.removeAll(B)

modificará el conjunto A. En esta situación, removeAll devolverá true (como se indica en removeAll docs ). Pero probablemente no desee modificar el conjunto A, por lo que puede pensar en actuar en una copia, de esta manera:

new HashSet(A).removeAll(B)

y el valor de retorno será verdadero si los conjuntos no son distintos, es decir, tienen una intersección no vacía.

Ver también Colecciones de Apache Commons

Plap
fuente
2

Puede usar el método retiene todos y obtener la intersección de sus dos conjuntos.

Artem
fuente
En la mayoría de los casos, es necesario mantener el conjunto original, por lo que para usarlo retainAlles necesario hacer una copia del conjunto original. Entonces es más eficiente de usar HashSetcomo lo sugiere Zéychin .
Petr Pudlák
Eso es un cambio de estado, no un control de condición
Ben