La forma más rápida de hacer una resta de colección

Question

Tengo dos juegos. Set b es el subconjunto de Set a. ambos son conjuntos muy grandes. Quiero restar b de a, ¿cuál es la mejor práctica para hacer esta operación común? He escrito muchos códigos como este y no creo que sea eficiente. Cuál es tu idea ?

pseudo código: (esto no es API de Java).

for(int i = 0 ; i < a.size(); i++) { 
      for (int j=0 ; j < b.size() ;j++) { 
       // do comparison , if found equals ,remove from a 
       break; 
      } 
} 

Y quiero encontrar un algoritmo, no solo se aplica a Conjuntos, también funciona para Array.

EDITAR: El conjunto aquí no es API JAVA, es una estructura de datos. así que no me importa si Java API tiene un método removeAll(), quiero encontrar una solución común para este problema, he encontrado muchos problemas como este cuando uso Javascript y Actionscript.

Answer 1

No creo que lo obtenga mucho más rápido, pero su código se verá más simple y no se volverá más lento en a.removeAll(b);. removeAll() es parte de la API de Java.

Para análisis de eficiencia: el ejemplo del código que proporcionamos es O (n^2), que no es muy bueno, pero tampoco es lo más horrible del mundo (la complejidad exponencial es lo que no desea). Siempre que no conozca la organización interna de los datos en la Colección, no obtendrá un mejor rendimiento. removeAll() es implementado por la clase misma y conoce la organización interna. Por lo tanto, si los datos están organizados en un Hash, puede obtener mejores resultados, si los datos están organizados en una matriz no ordenada, la complejidad será la misma. Un conjunto debe buscar eficientemente si un nuevo elemento ya está en el conjunto, entonces sospecho que algún tipo de Hash es una representación interna, especialmente si la implementación se llama HashSet. :-)

EDIT: El OP cambió su pregunta para mencionar que no es solo para Java. removeAll() es una API Java, por lo que esta (o algo similar) puede no estar disponible en otros idiomas. Como se dijo anteriormente, si las colecciones son arreglos sin clasificar sin otras restricciones, los dos for-loops ya son la solución más rápida. Pero si los datos están organizados de manera diferente, tienes opciones más rápidas. Si las dos colecciones se ordenan los datos (en mi ejemplo es el elemento más pequeño primero), se puede hacer lo siguiente (la reducción de la complejidad de O (n)):

int bIndex = 0; 
for(int i = 0 ; i < a.size(); i++) { 
      while (a[i] < b[bIndex]) {bIndex++;} 
      if (a[i] == b[bIndex]) {markForRemoval(a[i]);} // I mark this only for removal, as the actual removal would make your index incorrect 
} 

Si los datos se organiza como un hash en Ambas colecciones también necesitan solo un for-loop, accediendo directamente al elemento en b. Otras posibles organizaciones de datos son posibles.

Answer 2

Has visto el método removeAll en la interfaz Set?

También echa un vistazo a this stack overflow question.

Answer 3

Creo que encontrará java.util.HashSet.removeAll(Collection toRemove) para un buen rendimiento. Por otro lado, si no tiene establece pero ordena las colecciones, es posible que pueda hacerlo mucho mejor.

Answer 4

Al final, no hay mucho más que una opción para comparar uno por uno los elementos y eliminar los que están en ambos. Para hacerlo de otra manera, tendría que hacer algo como darle a todos los miembros un índice de valor único, y construir una gran variedad de booleanos que representen cada conjunto, y luego podría hacer operaciones de bits para restar B de A.No tengo idea si eso sería más rápido, dada la sobrecarga de crear índices de valor únicos y manipular las más grandes máscaras de bits.

Sé que no te importa una solución Java, pero como otras personas me han recomendado removeAll(), me gustaría señalar que todavía se está haciendo esencialmente lo mismo bajo las sábanas. Compruebe la fuente de HashSet.

Answer 5

Si los conjuntos se mantienen de manera que los elementos estén disponibles en un momento dado en orden ordenado, entonces puede realizar un solo pase lineal sobre ambos conjuntos y crear la diferencia en O (n) tiempo. Ahora, de nuevo, eso es si puede obtener en la lista ordenada de elementos gratis —, lo que quiere decir que el mantenimiento (es decir, agregar elemento y eliminar elementos) de los conjuntos paga el costo de mantener el elementos disponibles en orden ordenado.

Cualquier tipo de operación "removeAll" que se base en realizar búsquedas necesariamente será peor que O (n).

(Se me ocurre que la construcción de la diferencia de conjuntos — es decir, la respuesta construida a partir del pase lineal en las dos listas — podría ser O (n log n) si usted no es extremadamente cuidadoso.)

Answer 6

Bueno, la idea correcta ya fue señalada: el conjunto debe implementarse usando un hash. hashes idealmente tienen O(1) costo de acceso, por lo que puede obtener O(min(m,n)) costo para la operación general suponiendo que puede determinar qué conjunto es más grande (como mantener un contador durante las operaciones de inserción/eliminación).

en actionscript 3, utilizaría un Dictionary. solo usa elementos como claves y valores.

eliminación es similar al siguiente:

for each (var key:* in set2) {//a simple for-in loop will also do the trick, since keys and values are equal, but for-each-in loops perform faster 
    delete set1[key]; 
} 

en JavaScript, tendrá que dar los identificadores de entradas al insertar, para que pueda usar esos identificadores de como claves en un mapa. simplemente mapee los identificadores a los valores originales.

eliminación es similar al siguiente:

for (var key in set2) { 
    delete set1[key]; 
} 

Answer 7

Dado que b es un subconjunto de un no estoy seguro de por qué su pseudo-código tiene 2 bucles. El mío sería simplemente:

foreach b in B 
    remove b from A 

En la práctica cómo el tiempo de ejecución de esto se compara con el tiempo de ejecución de los suyos depende, entre otras cosas, cómo se ha implantado el conjunto como una estructura de datos.

Answer 8

La operación mientras la escribe es O (N^2), pero si los conjuntos son grandes, es posible que desee utilizar un hash.

// A is some kind of array, O(1) iteration 
// B is a hash containing elements to remove, O(1) contains(elt) 
List<T> removeAll(List<T> A, Set<T> B) { 
    List<T> result; // empty, could preallocate at |A| 
    for (elt : A) { // for each 'elt' belonging to A, hence O(|A|) 
    if (! B.contains(elt)) { // O(1) thanks to hash 
     C.add(elt) ; // ensure this is O(1) with preallocation or linked list 
    } 
    } 
    return result; 
} 

Esto requiere indexar el conjunto B, por lo que necesita una función hash. En Java, puede usar Set<T> Bh = new HashSet<T>(B); que es O (| B |) en tiempo y memoria. Así que en general obtenemos O (| A | + | B |) en el tiempo y aproximadamente O (2 | A | +2 | B |)) en la memoria. Claramente supera la cuadrática de eliminarTodo, notará la diferencia (TM).

Probablemente sea mejor copiar elementos en una nueva matriz (como se hace en el pseudo código), ya que eliminar elementos de A directamente podría llevar a la sobrecarga si mantiene los elementos en orden (los elementos de desplazamiento izquierdo en A son costosos).