Encontrar de manera eficiente la intersección de un número variable de conjuntos de cadenas

Question

Tengo un número variable de ArrayList que necesito para 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, con solo pensar en mi solución, parece que debería tener un tiempo de ejecución asintótico de Θ (n).

¡Gracias por cualquier ayuda!

tshred

Editar: Para aclarar, que en realidad sólo quiero saber es que hay una manera más rápida de hacerlo. Más rápido que Θ (n).

Answer 1

Set.retainAll() es cómo se encuentra la intersección de dos conjuntos. Si usa HashSet, entonces convertir su ArrayList a Set sy usar retainAll() en un bucle sobre todos ellos es en realidad O (n).

Answer 2

Ordene (n lg n) y luego realice búsquedas binarias (lg n).

Answer 3

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.

Answer 4

Una idea más: si sus matrices/conjuntos son de diferentes tamaños, tiene sentido comenzar con los más pequeños.

Answer 5

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.

Answer 6

También existe el método estático Sets.intersection(set1, set2) en Google Guava que devuelve una vista no modificable de la intersección de dos conjuntos.

Answer 7

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 es ligeramente más eficiente es debido a que el enfoque original tuvo que añadir elementos de set1 que luego tuvo que retirar de nuevo si no estaban en set2. Este enfoque solo agrega al conjunto de resultados lo que necesita estar allí.

Estrictamente hablando, usted podría hacer esto también antes de Java 8, pero sin Stream s el código hubiera sido bastante más laborioso.

Si ambos conjuntos difieren considerablemente en tamaño, preferiría la transmisión por sobre la más pequeña.