[JAVA] Envisagez d'implémenter une méthode qui renvoie la différence entre deux listes

introduction

Dans cet article, je vais présenter une petite histoire sur Java que j'utilise habituellement au travail.

Problème de réglage

Supposons que vous souhaitiez implémenter une méthode qui "supprime les éléments d'une liste 1 des éléments d'une autre liste 2". Il existe plusieurs situations dans lesquelles une telle fonctionnalité peut être utile. Par exemple, lors de l'implémentation d'une fonction pour recommander des utilisateurs dans un service Web, placez l'ID de l'utilisateur candidat à la recommandation dans la liste 1 et l'ID de l'utilisateur qui devrait être exclu des candidats à la recommandation dans la liste 2 pour une raison quelconque, et l'utilisateur final. Il est utilisé pour présenter les résultats des recommandations.

Par la suite, nous allons procéder à la discussion en supposant que les éléments de la liste sont de type Integer, mais ce n'est pas limité au type Integer en particulier, et il n'y a pas de problème même si c'est compliqué comme `List <String>` `. --Chaque liste ne doit pas contenir d'éléments en double. (D'un point de vue pratique, considérez qu'une telle duplication est éliminée avant l'appel de la méthode.)

Collection#removeAll La première implémentation de méthode que j'ai proposée était:

1st

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2) {
    list1.removeAll(list2);
    return list1;
}

C'est concis et facile à lire, mais c'est moins souhaitable car vous avez changé les arguments. Il est possible de copier la liste avec la méthode `` clone '', mais cette fois nous envisagerons une autre méthode.

Une autre direction: l'API Java 8 Stream

Considérez l'implémentation suivante à l'aide de l'API Stream introduite dans Java 8. list1À propos des éléments contenus danslist2Si non inclus dans, le résultatresultlistJe vais l'ajouter à.

2nd

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2){
    final List<List<Integer>> resultList = new ArrayList<>();
    list1.stream()
        .filter(p -> {
            return (! list2.contains(p));
        })
        .forEach(p -> {
            resultList.add(p);
        });
    return resultList;
}

Il y aura probablement également des améliorations dans cette implémentation.

-- `new ArrayList <> (); Vous pouvez passer le résultat de list1.stream () `à resultList``` tel quel sans créer une nouvelle instance avec` ``.

• L'appel de la méthode `.contains ()` sur une liste nécessite le traitement de ```O (n) `` `(Java 8 flux comment filtrer le contenu d'une liste introuvable dans un autre liste des tableaux? )

Concernant le deuxième point, dans l'implémentation ci-dessus, `list2.contains ()` est appelé pour chaque élément de `list1```, donc au total` `ʻO (n) ^ 2) Il faudra traiter ''. ([java / util / AbstractCollection.java](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractCollection.java#AbstractCollection.contains] Dans% 28java.lang.Object% 29), vous pouvez voir que `` .contains () '' suit chaque élément un par un.)

AbstractCollection.java

98     public boolean More ...contains(Object o) {
99         Iterator<E> e = iterator();
100        if (o==null) {
101            while (e.hasNext())
102                if (e.next()==null)
103                    return true;
104        } else {
105            while (e.hasNext())
106                if (o.equals(e.next()))
107                    return true;
108        }
109        return false;
110    }

Troisième honnêteté: .contains () pour Set

Considérez l'implémentation suivante, qui améliore les points ci-dessus. En utilisant `.contains ()` pour Set, le processus pour déterminer si l'élément de `list1``` est inclus dans` list2estO (1) J'ai pu le supprimer à ``.

3rd

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2) {
    final HashSet<Integer> list2Set = new HashSet<>(list2);
    final List<Integer> resultList = list1.stream()
            .filter(p -> {
                return (! list2Set.contains(p));
            })
            .collect(Collectors.toList());
    return resultList;
}

Au fait

Dans Apache Commons Collections, [ListUtils.java](https://commons.apache.org/proper/commons- Dans collections / apidocs / src-html / org / apache / commons / collections4 / ListUtils.html), la méthode `` soustract '' est définie comme suit.

python

110    /**
111     * Subtracts all elements in the second list from the first list,
112     * placing the results in a new list.
113     * <p>
114     * This differs from {@link List#removeAll(Collection)} in that
115     * cardinality is respected; if <Code>list1</Code> contains two
116     * occurrences of <Code>null</Code> and <Code>list2</Code> only
117     * contains one occurrence, then the returned list will still contain
118     * one occurrence.
119     *
120     * @param <E> the element type
121     * @param list1  the list to subtract from
122     * @param list2  the list to subtract
123     * @return a new list containing the results
124     * @throws NullPointerException if either list is null
125     */
126    public static <E> List<E> subtract(final List<E> list1, final List<? extends E> list2) {
127        final ArrayList<E> result = new ArrayList<E>();
128        final HashBag<E> bag = new HashBag<E>(list2);
129        for (final E e : list1) {
130            if (!bag.remove(e, 1)) {
131                result.add(e);
132            }
133        }
134        return result;
135    }