java - siguiente - union e interseccion de conjuntos en c++
¿Cuál es la forma más rápida de comparar dos conjuntos en Java? (8)
Estoy tratando de optimizar un fragmento de código que compare elementos de la lista.
P.ej.
public void compare(Set<Record> firstSet, Set<Record> 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
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<String> set = new HashSet<>();
set.addAll(Arrays.asList("leo","bale","hanks"));
Set<String> set2 = new HashSet<>();
set2.addAll(Arrays.asList("hanks","leo","bale"));
Predicate<Set> pred = set::equals;
boolean result = pred.test(set2);
System.out.println(result); // true
Hay un método en Guava Sets que puede ayudar aquí:
public static <E> boolean equals(Set<? extends E> set1, Set<? extends E> set2){
return Sets.symmetricDifference(set1,set2).isEmpty();
}
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 <Foo extends Comparable<Foo>>
implements Comparator<SortedSet<Foo>> {
@Override
public int compare( SortedSet<Foo> arg0, SortedSet<Foo> arg1 ) {
Iterator<Foo> 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;
}
}
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<Integer,Record> hm = new HashMap<Integer,Record>(secondSet.size());
int i = 0;
for(Record secondRecord : secondSet){
hm.put(i,secondRecord);
i++;
}
for(Record firstRecord : firstSet){
for(int i=0; i<secondSet.size(); i++){
//use hm for comparison
}
}
Si está utilizando la biblioteca de Guava es posible hacer:
SetView<Record> added = Sets.difference(secondSet, firstSet);
SetView<Record> removed = Sets.difference(firstSet, secondSet);
Y luego haz una conclusión basada en esto.
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 suma de comprobación crypto para el elemento. Ahora implemente las sumas de comprobación del conjunto mediante XORing las sumas 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 sumas de comprobación de N bits es 2 -N . Y los conjuntos desiguales de probabilidad 2 tienen las mismas sumas 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 sumas 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 sumas de comprobación. Y eso podría ser problemático.
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) .
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Set<String> a = this;
Set<String> b = o;
Set<String> thedifference_a_b = new HashSet<String>(a);
thedifference_a_b.removeAll(b);
if(thedifference_a_b.isEmpty() == false) return false;
Set<String> thedifference_b_a = new HashSet<String>(b);
thedifference_b_a.removeAll(a);
if(thedifference_b_a.isEmpty() == false) return false;
return true;
}