conjuntos - interseccion de dos arreglos en java
Encontrar de manera eficiente la intersección de un número variable de conjuntos de cadenas (7)
La mejor opción sería usar HashSet para almacenar el contenido de estas listas en lugar de ArrayList. Si puede hacerlo, puede crear un HashSet temporal al que agregue los elementos que se intersectarán (use el método putAll (..)). Do tempSet.retainAll (storedSet) y tempSet contendrán la intersección.
Tengo una cantidad variable de ArrayList de la que necesito encontrar la intersección de. Un límite realista en el número de conjuntos de cadenas probablemente sea alrededor de 35, pero podría ser más. No quiero ningún código, solo ideas sobre lo que podría ser eficiente. Tengo una implementación que estoy a punto de comenzar a codificar pero quiero escuchar algunas otras ideas.
Actualmente, solo pensando en mi solución, parece que debería tener un tiempo de ejecución asintótico de Θ (n 2 ).
¡Gracias por cualquier ayuda!
tshred
Editar: para aclarar, realmente solo quiero saber si hay una forma más rápida de hacerlo. Más rápido que Θ (n 2 ).
La respuesta aceptada está bien; como una actualización: desde Java 8 hay una forma un poco más eficiente de encontrar la intersección de dos Set s.
Set<String> intersection = set1.stream()
.filter(set2::contains)
.collect(Collectors.toSet());
La razón por la que es un poco más eficiente es porque el enfoque original tuvo que agregar elementos de set1 y luego tuvo que eliminar nuevamente si no estaban en set2 . Este enfoque solo agrega al conjunto de resultados lo que necesita estar allí.
Estrictamente hablando, también se puede hacer este pre Java 8, pero sin Stream el código hubiera sido bastante más laborioso.
Si ambos conjuntos difieren considerablemente en tamaño, preferiría transmitir por encima del más pequeño.
Ordénelos (n lg n) y luego realice búsquedas binarias (lg n).
Puede usar un solo HashSet. Su método add () devuelve falso cuando el objeto ya está en el conjunto. agregar objetos de las listas y marcar conteos de valores de retorno falsos le dará unión en el set + datos para el histograma (y los objetos que tienen un recuento + 1 igual al recuento de la lista son su intersección). Si arrojas los conteos a TreeSet, puedes detectar la intersección vacía temprano.
También está el método estático Sets.intersection(set1, set2) en Google Guava que devuelve una vista inmodificable de la intersección de dos conjuntos.
Una idea más: si sus matrices / conjuntos son de diferentes tamaños, tiene sentido comenzar con los más pequeños.
Set.retainAll() es cómo se encuentra la intersección de dos conjuntos. Si usa HashSet , entonces convertir sus ArrayList a Set sy usar retainAll() en un bucle sobre todos ellos es en realidad O (n).