Intersection efficace de deux List<String> en Java ?

Question

La question est simple :

J'ai deux listes

List<String> columnsOld = DBUtils.GetColumns(db, TableName);
List<String> columnsNew = DBUtils.GetColumns(db, TableName);

Et j'ai besoin d'obtenir l'intersection de ceux-ci. Existe-t-il un moyen rapide d'y parvenir ?

Answer 1

Vous pouvez utiliser [retainAll](http://docs.oracle.com/javase/7/docs/api/java/util/List.html#retainAll(java.util.Collection) méthode :

columnsOld.retainAll (columnsNew);

Answer 2

En utilisant l'application Google Goyave bibliothèque :

Sets.intersection(Sets.newHashSet(setA), Sets.newHashSet(setB))

Note : C'est beaucoup plus efficace que de faire naïvement l'intersection avec deux listes : c'est O(n+m), contre O(n×m) pour la méthode de l'intersection. version liste . Avec deux listes de millions d'articles, c'est la différence entre millions des opérations et trillions des opérations.

Answer 3

Puisque retainAll ne touche pas à la collection d'arguments, cela serait plus rapide :

List<String> columnsOld = DBUtils.GetColumns(db, TableName); 
List<String> columnsNew = DBUtils.GetColumns(db, TableName); 

for(int i = columnsNew.size() - 1; i > -1; --i){
    String str = columnsNew.get(i);
    if(!columnsOld.remove(str))
        columnsNew.remove(str);
}

L'intersection sera les valeurs laissées dans les colonnesNew. L'élimination des valeurs déjà comparées de columnsOld réduira le nombre de comparaisons nécessaires.

Answer 4

Et si

private List<String> intersect(List<String> A, List<String> B) {
    List<String> rtnList = new LinkedList<>();
    for(String dto : A) {
        if(B.contains(dto)) {
            rtnList.add(dto);
        }
    }
    return rtnList;
}

Answer 5

Il existe une méthode intéressante avec les flux qui permet de faire cela en une ligne de code et vous pouvez avoir deux listes qui ne sont pas du même type, ce qui n'est pas possible avec la méthode containsAll :

columnsOld.stream().filter(c -> columnsNew.contains(c)).collect(Collectors.toList());

Un exemple pour les listes de différents types. Si vous avez une relation entre foo et bar et que vous pouvez obtenir un objet bar à partir de foo, vous pouvez modifier votre flux :

List<foo> fooList = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<bar> barList = new ArrayList<>(Arrays.asList(new bar(), new bar()));

fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList());