Le meilleur moyen de supprimer les répétitions dans une collection en Java?

Question

Ceci est une question en deux parties:

D'abord, je suis intéressé de savoir quelle est la meilleure façon de supprimer des éléments récurrents d'une collection. La façon dont je l'ai fait jusqu'à présent est de simplement convertir la collection en un ensemble. Je sais que les ensembles ne peuvent pas avoir d'éléments répétitifs, alors ça me sert juste.

Est-ce une solution efficace? Serait-il préférable/plus idiomatique/plus rapide de boucler et de supprimer les répétitions? Est-ce que ça importe?

Ma deuxième question (connexe) est: Quelle est la meilleure façon de convertir un tableau en Set? En supposant un tableau arr La façon dont je l'ai fait est la suivante:

Set x = new HashSet(Arrays.asList(arr));

Ce convertit le tableau dans une liste, puis dans un ensemble. Semble être un rond-point. Y a-t-il un moyen meilleur/plus idiomatique/plus efficace de faire cela que la méthode de la double conversion?

Merci!

Answer 1

1. Avez-vous des informations sur la collection, comme disent qu'il est déjà triée, ou contient principalement des doublons ou des éléments uniques pour la plupart? Avec juste une collection arbitraire, je pense que la conversion en un Set est bien.

2. Arrays.asList() ne crée pas une nouvelle liste. En fait, il retourne juste un List qui utilise le tableau comme son backing store, donc c'est une opération bon marché. Donc, votre façon de faire un Set à partir d'un tableau est la façon dont je le ferais aussi.

Answer 2

En supposant que vous voulez vraiment la sémantique ensemble, la création d'une nouvelle Set de la collection contenant en double est une excellente approche. L'intention est très claire, elle est plus compacte que la boucle elle-même et laisse la collection source intacte.

Pour créer un Set à partir d'un tableau, la création d'un List intermédiaire est une approche courante. L'emballage renvoyé par Arrays.asList() est léger et efficace. Malheureusement, il n'y a pas d'API plus directe dans Java.

Answer 3

Utilisez la norme HashSetCollectionconversion constructor. Selon The Java Tutorials:

Voici un idiome Set simple mais utile. Supposons que vous ayez une collection, c, et vous voulez créer une autre collection contenant les mêmes éléments mais avec tous les doublons éliminés. Le suivant one-liner fait l'affaire.

Collection<Type> noDups = new HashSet<Type>(c); 

Il fonctionne en créant un ensemble (qui, par définition , ne peut pas contenir un double ), contenant initialement tous les éléments c. Il utilise le constructeur de conversion standard décrit dans la section The Collection Interface.

Voici une variante mineure de cet idiome qui préserve l'ordre de la collection originale tout en retirant élément en double.

Collection<Type> noDups = new LinkedHashSet<Type>(c); 

Ce qui suit est une méthode générique qui encapsule l'idiome précédentes, renvoyant un ensemble du même type générique que celui adopté.

public static <E> Set<E> removeDups(Collection<E> c) { 
    return new LinkedHashSet<E>(c); 
} 

Answer 4

Je pense que votre approche de mettre des éléments dans un ensemble pour produire la collection d'objets uniques est le meilleur. C'est clair, efficace et correct.

Si vous n'êtes pas à l'aise avec Arrays.asList() sur le chemin de l'ensemble, vous pouvez simplement lancer une boucle foreach sur le tableau pour ajouter des éléments à l'ensemble, mais je ne vois aucun mal (pour les non -primitive arrays) dans votre approche. Arrays.asList() renvoie une liste qui est "sauvegardée par" le tableau source, de sorte qu'il n'a pas de coût significatif dans le temps ou l'espace.

Answer 5

1. Doublons

autres réponses: concordants L'utilisation Set devrait être le moyen le plus efficace pour supprimer les doublons. HashSet devrait fonctionner en O(n) fois en moyenne. Boucler et supprimer des répétitions fonctionnerait dans l'ordre de O(n^2). Donc, en utilisant Set est recommandé dans la plupart des cas. Dans certains cas (par exemple, la mémoire limitée), l'itération peut avoir un sens.

2. Arrays.asList() est une opération bon marché qui ne copie pas le tableau, avec un minimum de mémoire. Vous pouvez ajouter manuellement des éléments en itérant dans le tableau.

public static Set arrayToSet(T[] array) { 
    Set set = new HashSet(array.length/2); 
    for (T item : array) 
    set.add(item); 
    return set; 
} 

Answer 6

À moins de goulots d'étranglement spécifiques que vous connaissez (par exemple une collection de dizaines de milliers d'articles) la conversion d'un ensemble est une solution et doit être (OMI), la première façon, vous résoudre ce problème tout à fait raisonnable, et cherchez seulement quelque chose de fantaisiste s'il y a un problème spécifique à résoudre.