¿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 compara 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 el número de registros en conjuntos será alto.

Gracias

Shekhar

firstSet.equals(secondSet)

Realmente depende de lo que quiera hacer en la lógica de comparación ... es decir, ¿qué sucede si encuentra un elemento en un conjunto y no en el otro? Su método tiene un voidtipo de retorno, 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 valor booleano, no un conjunto. Para usar removeAll (), tendrá que copiar el conjunto y luego usarlo.

Set one = new HashSet<>(firstSet);
Set two = new HashSet<>(secondSet);
one.removeAll(secondSet);
two.removeAll(firstSet);

Si los contenidos de oney twoestán vacíos, entonces sabrá que los dos conjuntos eran iguales. Si no es así, entonces tienes los elementos que hicieron que los conjuntos fueran desiguales.

Mencionaste que la cantidad de registros podría ser alta. Si la implementación subyacente es a, HashSetentonces la recuperación de cada registro se realiza a O(1)tiempo, por lo que realmente no puede ser mucho mejor que eso. TreeSetes O(log n).

Si simplemente desea saber si los conjuntos son iguales, el equalsmétodo AbstractSetse implementa aproximadamente 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 iguales
• el otro objeto no es un conjunto en absoluto, y
• Los tamaños de los dos conjuntos son diferentes.

Después de eso, containsAll(...)regresará falsetan 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, deberá probarlos todos.

Por tanto, el peor de los casos se produce cuando los dos conjuntos son iguales pero no los mismos objetos. Ese costo suele ser O(N)o O(NlogN)depende de la implementación de this.containsAll(c).

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

ACTUALIZAR

Si está dispuesto a invertir tiempo en la implementación de un conjunto personalizado, existe un enfoque que puede mejorar "casi el mismo" caso.

La idea es que necesita calcular previamente y almacenar en caché un hash para todo el conjunto para poder obtener el valor actual del código hash del conjunto O(1). Luego, puede comparar el código hash de los dos conjuntos como una aceleración.

¿Cómo podrías implementar un código hash como ese? Bueno, si el código hash establecido 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 código hash 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 establecido 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 distribución. Esto se debe a que cuando los dos códigos hash establecidos son iguales, aún debe recurrir a la O(N)comparación de todos los elementos.

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

ADVERTENCIA : esto es muy especulativo. Un "experimento mental" si quieres.

Suponga que su clase de elemento establecida tiene un método para devolver una suma de comprobación criptográfica para el elemento. Ahora implemente las sumas de verificación del conjunto haciendo XOR las sumas de verificación devueltas para los elementos.

¿Qué nos compra esto?

Bueno, si asumimos que no ocurre nada oculto, la probabilidad de que dos elementos de conjuntos desiguales tengan las mismas sumas de comprobación de N bits es 2 ^-N . Y la probabilidad de que 2 conjuntos desiguales tengan las mismas sumas de comprobación de N bits también es 2 ^-N . Entonces mi idea es que puedas implementar equalscomo:

    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);
    }

Bajo los supuestos anteriores, esto sólo le dará la respuesta equivocada una vez en 2 ^-N tiempo. Si hace que N sea lo suficientemente grande (por ejemplo, 512 bits), la probabilidad de una respuesta incorrecta se vuelve insignificante (por ejemplo, aproximadamente 10 ^-150 ).

La desventaja es que calcular las sumas de verificación criptográficas para elementos es muy costoso, especialmente a medida que aumenta la cantidad de bits. Por lo tanto, realmente necesita un mecanismo eficaz para memorizar las sumas de comprobación. Y eso podría ser problemático.

Y la otra desventaja es que una probabilidad de error distinta de cero puede ser inaceptable sin importar cuán pequeña sea la probabilidad. (Pero si ese es el caso ... ¿cómo maneja el caso en el que un rayo cósmico invierte un bit crítico? ¿O si simultáneamente invierte el mismo bit en dos instancias de un sistema redundante?)

Hay un método en Guayaba Setsque puede ayudar aquí:

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

Tiene la siguiente solución de https://www.mkyong.com/java/java-how-to-compare-two-sets/

public static boolean equals(Set<?> set1, Set<?> set2){

    if(set1 == null || set2 ==null){
        return false;
    }

    if(set1.size() != set2.size()){
        return false;
    }

    return set1.containsAll(set2);
}

O si prefiere utilizar una única declaración de devolución:

public static boolean equals(Set<?> set1, Set<?> set2){

  return set1 != null 
    && set2 != null 
    && set1.size() == set2.size() 
    && set1.containsAll(set2);
}

Existe una solución O (N) para casos muy específicos donde:

• los conjuntos están ordenados
• ambos ordenados en el mismo orden

El siguiente código asume que ambos conjuntos se basan en 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;
        }
    }

Si está utilizando la Guavabiblioteca, es posible hacer lo siguiente:

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

Y luego saque una conclusión basada en estos.

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 an (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
    }
}

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;
    }

Creo que se puede utilizar 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. Un ejemplo simple y llano 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