Quel est le moyen le plus rapide de comparer deux ensembles en Java?

J'essaye d'optimiser un morceau de code qui compare des éléments de liste.

Par exemple.

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

Veuillez prendre en compte que le nombre d'enregistrements dans les ensembles sera élevé.

Merci

Shekhar

firstSet.equals(secondSet)

Cela dépend vraiment de ce que vous voulez faire dans la logique de comparaison ... c'est-à-dire que se passe-t-il si vous trouvez un élément dans un ensemble et non dans l'autre? Votre méthode a un voidtype de retour, donc je suppose que vous ferez le travail nécessaire dans cette méthode.

Un contrôle plus fin si vous en avez besoin:

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

Si vous avez besoin d'obtenir les éléments qui sont dans un ensemble et pas dans l'autre.
EDIT: set.removeAll(otherSet)renvoie un booléen, pas un ensemble. Pour utiliser removeAll (), vous devrez copier l'ensemble puis l'utiliser.

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

Si les contenus de oneet twosont tous deux vides, vous savez que les deux ensembles étaient égaux. Sinon, vous avez les éléments qui ont rendu les ensembles inégaux.

Vous avez mentionné que le nombre d'enregistrements pourrait être élevé. Si l'implémentation sous-jacente est a, HashSetla récupération de chaque enregistrement est effectuée à O(1)temps, vous ne pouvez donc pas vraiment faire mieux que cela. TreeSetest O(log n).

Si vous voulez simplement savoir si les ensembles sont égaux, la equalsméthode on AbstractSetest implémentée à peu près comme ci-dessous:

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

Notez comment il optimise les cas courants où:

• les deux objets sont les mêmes
• l'autre objet n'est pas du tout un ensemble, et
• les tailles des deux ensembles sont différentes.

Après cela, containsAll(...)reviendra falsedès qu'il trouvera un élément dans l'autre ensemble qui n'est pas également dans cet ensemble. Mais si tous les éléments sont présents dans les deux ensembles, il devra tous les tester.

La pire des performances se produit donc lorsque les deux ensembles sont égaux mais pas les mêmes objets. Ce coût est généralement O(N)ou O(NlogN)dépend de la mise en œuvre de this.containsAll(c).

Et vous obtenez des performances proches du pire des cas si les ensembles sont grands et ne diffèrent que par un petit pourcentage des éléments.

METTRE À JOUR

Si vous êtes prêt à investir du temps dans une implémentation personnalisée, il existe une approche qui peut améliorer le cas «presque identique».

L'idée est que vous devez pré-calculer et mettre en cache un hachage pour l'ensemble complet afin de pouvoir obtenir la valeur de hachage actuelle de l'ensemble O(1). Ensuite, vous pouvez comparer le hashcode pour les deux ensembles comme une accélération.

Comment pourriez-vous implémenter un hashcode comme ça? Eh bien, si le hashcode défini était:

• zéro pour un ensemble vide, et
• le XOR de tous les hashcodes des éléments pour un ensemble non vide,

alors vous pouvez mettre à jour à moindre coût le hashcode mis en cache de l'ensemble chaque fois que vous avez ajouté ou supprimé un élément. Dans les deux cas, il vous suffit de XOR le hashcode de l'élément avec le hashcode actuel défini.

Bien sûr, cela suppose que les codes de hachage des éléments sont stables tandis que les éléments sont membres d'ensembles. Il suppose également que la fonction de hashcode des classes d'éléments donne une bonne répartition. En effet, lorsque les deux codes de hachage définis sont identiques, vous devez toujours revenir à la O(N)comparaison de tous les éléments.

Vous pourriez pousser cette idée un peu plus loin ... du moins en théorie.

AVERTISSEMENT - Ceci est hautement spéculatif. Une "expérience de pensée" si vous le souhaitez.

Supposons que votre classe d'élément set ait une méthode pour renvoyer une somme de contrôle cryptographique pour l'élément. Maintenant, implémentez les sommes de contrôle de l'ensemble en XORing les sommes de contrôle retournées pour les éléments.

Qu'est-ce que cela nous achète?

Eh bien, si nous supposons qu'il ne se passe rien par dessous, la probabilité que deux éléments d'ensemble inégaux aient les mêmes sommes de contrôle de N bits est de 2 ^-N . Et la probabilité que 2 ensembles inégaux aient les mêmes sommes de contrôle de N bits est également de 2 ^-N . Donc, mon idée est que vous pouvez mettre equalsen œuvre comme:

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

Selon les hypothèses ci-dessus, cela ne vous donnera la mauvaise réponse qu'une fois toutes les 2 ^-N . Si vous rendez N suffisamment grand (par exemple 512 bits), la probabilité d'une mauvaise réponse devient négligeable (par exemple environ 10 ^-150 ).

L'inconvénient est que le calcul des sommes de contrôle cryptographiques pour les éléments est très coûteux, d'autant plus que le nombre de bits augmente. Vous avez donc vraiment besoin d'un mécanisme efficace pour mémoriser les sommes de contrôle. Et cela pourrait être problématique.

Et l'autre inconvénient est qu'une probabilité d'erreur non nulle peut être inacceptable, quelle que soit la faible probabilité. (Mais si tel est le cas ... comment gérez-vous le cas où un rayon cosmique retourne un bit critique? Ou s'il retourne simultanément le même bit dans deux instances d'un système redondant?)

Il existe une méthode dans Guava Setsqui peut aider ici:

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

Vous avez la solution suivante sur 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);
}

Ou si vous préférez utiliser une seule déclaration de retour:

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

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

Il existe une solution O (N) pour des cas très spécifiques où:

• les ensembles sont tous les deux triés
• tous deux triés dans le même ordre

Le code suivant suppose que les deux ensembles sont basés sur les enregistrements comparables. Une méthode similaire pourrait être basée sur un comparateur.

    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 vous utilisez la Guavabibliothèque, il est possible de faire:

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

Et puis faites une conclusion basée sur ceux-ci.

Je mettrais le secondSet dans un HashMap avant la comparaison. De cette façon, vous réduirez le temps de recherche de la deuxième liste à n (1). Comme ça:

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

Je pense que la référence de méthode avec la méthode égale peut être utilisée. Nous supposons que le type d'objet a sans l'ombre d'un doute sa propre méthode de comparaison. Un exemple clair et simple est ici,

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