Quel est le moyen le plus rapide pour comparer les deux jeux en Java?

Si vous voulez simplement savoir si les jeux sont l'égalité, la equals méthode sur AbstractSet est mis en œuvre à 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);
    }

Remarque comment il optimise la commune les cas où:

• les deux objets sont les mêmes
• l'autre objet n'est pas un jeu à tous, et
• les deux ensembles de tailles différentes.

Après, containsAll(...) sera de retour false dès qu'il trouve un élément dans l'autre jeu qui n'est pas dans cet ensemble. Mais si tous les éléments sont présents dans les deux ensembles, il aura besoin de tous les tester.

Le pire des cas de la performance, par conséquent, se produit lorsque les deux ensembles sont égaux, mais pas les mêmes objets. Ce coût est généralement O(N) ou O(NlogN) en fonction de la mise en œuvre de this.containsAll(c).

Et vous vous en approchez-à-pire des cas, la performance si les jeux sont grands et ne diffèrent que dans un petit pourcentage des éléments.

---

Mise à JOUR

Si vous êtes prêt à investir du temps dans un ensemble personnalisé de mise en œuvre, il y a une approche qui peut améliorer la "presque le même cas".

L'idée est que vous avez besoin pour pré-calculer et de mettre en cache une table de hachage pour l'ensemble de sorte que vous pouvez obtenir le jeu actuel de hashcode de la valeur dans O(1). Ensuite, vous pouvez comparer le hashcode pour les deux ensembles comme une accélération.

Comment pourriez-vous mettre en œuvre un hashcode comme ça? Ainsi, si l'ensemble hashcode était:

• zéro pour un ensemble vide, et
• le XOR de tous les élément hashcodes pour un non-vide de sens,

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

Bien sûr, cela suppose que l'élément hashcodes sont stables tandis que les éléments sont membres d'ensembles. Il suppose également que les classes d'éléments hashcode fonction donne une bonne répartition. C'est parce que quand les deux hashcodes sont les mêmes, vous avez encore de revenir à la O(N) comparaison de tous les éléments.

---

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

AVERTISSEMENT - Ce n'est que spéculation. Une "expérience de pensée" si vous le souhaitez.

Supposons que votre élément de la classe possède une méthode de retour d'un crypto sommes de contrôle pour l'élément. Mettre en œuvre l'ensemble de la somme de contrôle par XORing sommes retournés pour les éléments.

Qu'est-ce nous acheter?

Bien, si nous supposons que rien sournoise qui se passe, la probabilité que deux inégalité de définir les éléments ont le même N bits de sommes est de 2^N. Et la probabilité 2 inégale ensembles ont le même N bits de sommes de contrôle est également 2^N. Donc, mon idée est que vous pouvez mettre en œuvre equals 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);
    }

Sous les hypothèses ci-dessus, cela ne fera que vous donner la mauvaise réponse une fois dans 2^N de temps. Si vous faites N assez 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 de la crypto sommes de contrôle pour les éléments est très cher, surtout que le nombre de bits augmente. Si vous avez vraiment besoin d'un mécanisme efficace pour memoizing les sommes de contrôle. Et qui pourrait être problématique.

Et l'autre inconvénient, c'est qu'une probabilité non nulle d'erreur peut être inacceptable, peu importe comment petit la probabilité est. (Mais si c'est le cas ... comment voulez-vous traiter le cas où un rayon cosmique retourne une critique peu? Ou si c'simultanément retourne les mêmes bits dans les deux cas d'un système redondant?)

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

Ou si vous préférez utiliser une seule instruction return:

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

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

Si vous utilisez Guava bibliothèque, il est possible de faire:

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

Et ensuite faire une conclusion sur la base de ces.

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