¿Cuál es la forma más rápida de comparar dos conjuntos en Java?

Estoy tratando de optimizar un fragmento de código que compare elementos de la lista.

P.ej.

public void compare(Set firstSet, Set secondSet){ for(Record firstRecord : firstSet){ for(Record secondRecord : secondSet){ // comparing logic } } } 

Tenga en cuenta que la cantidad de registros en los conjuntos será alta.

Gracias

Shekhar

 firstSet.equals(secondSet) 

Realmente depende de lo que quieras hacer en la lógica de comparación … es decir, ¿qué sucede si encuentras un elemento en un conjunto no en el otro? Su método tiene un tipo de devolución de void así que supongo que hará el trabajo necesario en este método.

Control más detallado si lo necesita:

 if (!firstSet.containsAll(secondSet)) { // do something if needs be } if (!secondSet.containsAll(firstSet)) { // do something if needs be } 

Si necesita obtener los elementos que están en un conjunto y no en el otro.
EDITAR: set.removeAll(otherSet) devuelve un booleano, no un conjunto. Para usar removeAll (), tendrá que copiar el conjunto y luego usarlo.

 Set one = firstSet; Set two = secondSet one.removeAll(secondSet); two.removeAll(firstSet); 

Si los contenidos de one y two están vacíos, entonces sabrá que los dos conjuntos son iguales. Si no, entonces tienes los elementos que hicieron que los sets sean desiguales.

Usted mencionó que la cantidad de registros podría ser alta. Si la implementación subyacente es un HashSet entonces la HashSet de cada registro se realiza en O(1) tiempo, por lo que realmente no puede obtener mucho más que eso. TreeSet es O(log n) .

Si simplemente desea saber si los conjuntos son iguales, el método equals en AbstractSet se implementa más o menos como se muestra a continuación:

  public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Collection c = (Collection) o; if (c.size() != size()) return false; return containsAll(c); } 

Tenga en cuenta cómo optimiza los casos comunes en los que:

  • los dos objetos son lo mismo
  • el otro objeto no es un conjunto en absoluto, y
  • los tamaños de los dos juegos son diferentes.

Después de eso, containsAll(...) devolverá false tan pronto como encuentre un elemento en el otro conjunto que no esté también en este conjunto. Pero si todos los elementos están presentes en ambos conjuntos, tendrá que probarlos todos.

Por lo tanto, el peor de los casos ocurre cuando los dos conjuntos son iguales pero no son los mismos objetos. Ese costo es típicamente O(N) u O(NlogN) dependiendo de la implementación de este. this.containsAll(c) .

Y obtiene un rendimiento de caso cercano al peor si los conjuntos son grandes y solo difieren en un pequeño porcentaje de los elementos.


ACTUALIZAR

Si está dispuesto a invertir tiempo en una implementación de conjunto personalizado, existe un enfoque que puede mejorar el caso “casi igual”.

La idea es que debe precalcular y guardar en caché un hash para todo el conjunto, de modo que pueda obtener el valor de código hash actual del conjunto en O(1) . Entonces puedes comparar el código hash de los dos conjuntos como una aceleración.

¿Cómo podría implementar un código hash como ese? Bueno, si el conjunto hashcode fuera:

  • cero para un conjunto vacío, y
  • el XOR de todos los códigos hash de elementos para un conjunto no vacío,

entonces podría actualizar de forma económica el hashcode en caché del conjunto cada vez que agregue o elimine un elemento. En ambos casos, simplemente XOR el código hash del elemento con el código hash actual.

Por supuesto, esto supone que los códigos hash de elementos son estables mientras que los elementos son miembros de conjuntos. También asume que la función de código hash de clases de elementos ofrece una buena dispersión. Esto se debe a que cuando los dos códigos hash establecidos son los mismos, aún debe recurrir a la comparación O(N) de todos los elementos.


Podrías llevar esta idea un poco más allá … al menos en teoría.

Supongamos que su clase de elemento set tiene un método para devolver una sum de comprobación crypto para el elemento. Ahora implemente las sums de comprobación del conjunto mediante XORing las sums de comprobación devueltas para los elementos.

¿Qué nos compra esto?

Bien, si suponemos que no ocurre nada clandestino, la probabilidad de que dos elementos de conjunto desiguales tengan las mismas sums de comprobación de N bits es 2 -N . Y los conjuntos desiguales de probabilidad 2 tienen las mismas sums de comprobación de N bits y también 2 -N . Entonces mi idea es que puedes implementar equals como:

  public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Collection c = (Collection) o; if (c.size() != size()) return false; return checksums.equals(c.checksums); } 

Según las suposiciones anteriores, esto solo le dará la respuesta incorrecta una vez en 2 -N tiempo. Si haces N lo suficientemente grande (por ejemplo, 512 bits), la probabilidad de una respuesta incorrecta es insignificante (por ejemplo, aproximadamente 10 -150 ).

El inconveniente es que calcular las sums de comprobación de criptografía para los elementos es muy costoso, especialmente a medida que aumenta el número de bits. Entonces realmente necesitas un mecanismo efectivo para memorizar las sums de comprobación. Y eso podría ser problemático.

Hay un método en Guava Sets que puede ayudar aquí:

 public static  boolean equals(Set< ? extends E> set1, Set< ? extends E> set2){ return Sets.symmetricDifference(set1,set2).isEmpty(); } 

Si está utilizando la biblioteca de Guava es posible hacer:

  SetView added = Sets.difference(secondSet, firstSet); SetView removed = Sets.difference(firstSet, secondSet); 

Y luego haz una conclusión basada en esto.

Hay una solución O (N) para casos muy específicos en los que:

  • los conjuntos son ambos ordenados
  • ambos clasificados en el mismo orden

El siguiente código asume que ambos conjuntos se basan en los registros comparables. Un método similar podría basarse en un Comparador.

  public class SortedSetComparitor > implements Comparator> { @Override public int compare( SortedSet arg0, SortedSet arg1 ) { Iterator otherRecords = arg1.iterator(); for (Foo thisRecord : arg0) { // Shorter sets sort first. if (!otherRecords.hasNext()) return 1; int comparison = thisRecord.compareTo(otherRecords.next()); if (comparison != 0) return comparison; } // Shorter sets sort first if (otherRecords.hasNext()) return -1; else return 0; } } 
 public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Set a = this; Set b = o; Set thedifference_a_b = new HashSet(a); thedifference_a_b.removeAll(b); if(thedifference_a_b.isEmpty() == false) return false; Set thedifference_b_a = new HashSet(b); thedifference_b_a.removeAll(a); if(thedifference_b_a.isEmpty() == false) return false; return true; } 

Pondría el secondSet en un HashMap antes de la comparación. De esta forma, reducirá el tiempo de búsqueda de la segunda lista a n (1). Me gusta esto:

 HashMap hm = new HashMap(secondSet.size()); int i = 0; for(Record secondRecord : secondSet){ hm.put(i,secondRecord); i++; } for(Record firstRecord : firstSet){ for(int i=0; i 

Creo que se puede usar la referencia de método con el método igual. Suponemos que el tipo de objeto sin sombra de duda tiene su propio método de comparación. El ejemplo sencillo y simple está aquí,

 Set set = new HashSet<>(); set.addAll(Arrays.asList("leo","bale","hanks")); Set set2 = new HashSet<>(); set2.addAll(Arrays.asList("hanks","leo","bale")); Predicate pred = set::equals; boolean result = pred.test(set2); System.out.println(result); // true