Calculer efficacement l'intersection de deux ensembles en Java ?

Question

Quel est le moyen le plus efficace de trouver la taille de l'intersection de deux ensembles non épars en Java ? Il s'agit d'une opération que je vais appeler sur de grands ensembles un très grand nombre de fois, l'optimisation est donc importante. Je ne peux pas modifier les ensembles originaux.

J'ai examiné Apache Commons CollectionUtils.intersection qui semble être assez lent. Mon approche actuelle consiste à prendre le plus petit des deux ensembles, à le cloner, puis à appeler .retainAll sur le plus grand des deux ensembles.

public static int getIntersection(Set<Long> set1, Set<Long> set2) {
    boolean set1IsLarger = set1.size() > set2.size();
    Set<Long> cloneSet = new HashSet<Long>(set1IsLarger ? set2 : set1);
    cloneSet.retainAll(set1IsLarger ? set1 : set2);
    return cloneSet.size();
}

Answer 1

Si les deux ensembles peuvent être triés, comme TreeSet L'exécution des deux itérateurs pourrait être un moyen plus rapide de compter le nombre d'objets partagés.

Si vous effectuez cette opération souvent, cela pourrait vous apporter beaucoup si vous pouviez envelopper les ensembles de manière à pouvoir mettre en cache le résultat de l'opération d'intersection en conservant un fichier de type dirty pour vérifier la validité du résultat de la mise en cache, en calculant à nouveau si nécessaire.

Answer 2

Si vous calculez l'intersection dans le seul but de compter le nombre d'éléments dans l'ensemble, je suggère que vous ayez besoin de compter l'intersection directement au lieu de construire l'ensemble et d'appeler ensuite size() .

Ma fonction pour compter :

/**
 * Computes the size of intersection of two sets
 * @param small first set. preferably smaller than the second argument
 * @param large second set;
 * @param <T> the type
 * @return size of intersection of sets
 */
public <T> int countIntersection(Set<T> small, Set<T> large){
    //assuming first argument to be smaller than the later;
    //however double checking to be sure
    if (small.size() > large.size()) {
        //swap the references;
        Set<T> tmp = small;
        small = large;
        large = tmp;
    }
    int result = 0;
    for (T item : small) {
        if (large.contains(item)){
            //item found in both the sets
            result++;
        }
    }
    return result;
}

Answer 3

C'est une bonne approche. Vous devriez obtenir des performances O(n) avec votre solution actuelle.

Answer 4

Pour information, si une collection d'ensembles sont tous triés en utilisant la même relation de comparaison, alors vous pouvez itérer leur intersection en un temps N * M, où N est la taille de l'ensemble des ensembles. le plus petit et M est le nombre d'ensembles.

La mise en œuvre est laissée à l'appréciation du lecteur. . Voici un exemple .

Answer 5

Comptage des intersections par streams/reduce (cela suppose que vous déterminez quel ensemble est le plus grand avant de l'appeler) :

public int countIntersect(Set<Integer> largerSet, Set<Integer> smallerSet){
    return smallerSet.stream().reduce(0, (a,b) ->  largerSet.contains(b)?a+1:a);
}

Cependant, j'ai lu ailleurs qu'aucun code java ne peut être plus rapide que les méthodes Set pour les opérations Set, car elles sont implémentées en code natif et non en code java. Je soutiens donc la suggestion d'essayer BitSet pour obtenir des résultats plus rapides.