Pregunta ¿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<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


73
2017-07-27 06:30


origen


Respuestas:


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? Tu método tiene un void tipo de devolución así que supongo que harás 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 el contenido de one y two ambos están vacíos, entonces sabes que los dos conjuntos eran 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 una HashSet a continuación, la obtención de cada registro se realiza en O(1) tiempo, entonces realmente no puedes estar mucho mejor que eso. TreeSet es O(log n).


122
2017-07-27 06:31



Si simplemente quiere saber si los conjuntos son iguales, el equals método en AbstractSet se implementa más o menos de la siguiente manera:

    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 esto, containsAll(...) regresará 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) o O(NlogN) dependiendo de la implementación de 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, usted todavía tiene que recurrir a la O(N)comparació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?

Bueno, si asumimos 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-NORTE. Y los conjuntos desiguales de probabilidad 2 tienen las mismas sumas de comprobación de N bits también 2-NORTE. 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);
    }

Bajo las suposiciones anteriores, esto solo le dará la respuesta incorrecta una vez en 2-NORTE hora. Si haces que N sea 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.


53
2017-07-27 06:44



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

13
2017-12-17 01:31



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

2
2017-12-24 15:43



Si estás usando Guava biblioteca 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.


2
2017-10-13 22:38



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

1
2017-11-29 15:37



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

1
2018-03-31 15:14



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

-1
2018-06-07 10:56